问题链接

问题描述

  我们有一个非负整数数组 A。对于每个（连续的）子数组 B = [A[i], A[i+1], ..., A[j]] （ i <= j），我们对 B 中的每个元素进行按位或操作，获得结果 A[i] | A[i+1] | ... | A[j]。返回可能结果的数量。多次出现的结果在最终答案中仅计算一次。）

• note:
  1 <= A.length <= 50000
  0 <= A[i] <= 10^9

问题示例

• 示例 1：
  输入：[0]
  输出：1
  解释：
  只有一个可能的结果 0 。
• 示例 2：
  输入：[1,1,2]
  输出：3
  解释：
  可能的子数组为 [1]，[1]，[2]，[1, 1]，[1, 2]，[1, 1, 2]。
  产生的结果为 1，1，2，1，3，3 。
  有三个唯一值，所以答案是 3 。
• 示例 3：
  输入：[1,2,4]
  输出：6
  解释：
  可能的结果是 1，2，3，4，6，以及 7

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/bitwise-ors-of-subarrays
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题过程

传统dp方法（时间复杂度是O(n^2)是无法通过的）
  一共有n^2个子数组，挨个计算的话整体时间复杂度会达到O(n^3)，所以需要使用动态规划，传统动态规划思想：

dp[i][j] = A[i] | A[i + 1] | A[i + 2] | ... | A[j]
dp[i][j] = dp[i][j - 1] | A[j]

计算完成后，将dp数组中的数字放入set，计算set的长度即可。
代码：

    public int subarrayBitwiseORs(int[] A) {
        int n = A.length;
        List<List<Integer>> dp = new ArrayList<>();
        Set<Integer> set = new HashSet<>();
        for(int len = 1; len <= n; len++){
            for(int i = 0; i <= n - len; i++){
                int j = i + len - 1;
                if(len == 1){
                    dp.add(new ArrayList<>());
                    dp.get(i).add(A[i]);
                    set.add(A[i]);
                    continue;
                }
                List<Integer> temp = dp.get(i);
                temp.add(temp.get(temp.size() - 1) | A[j]);
                set.add(temp.get(temp.size() - 1));
            }
        }
        return set.size();
    }
}

  仔细想想会发现dp[i][j]只与dp[i][j-1]相关，可使用滚动数组降维，减少空间复杂度， 可以把dp设为长度为n的一维数组。

class Solution {
    public int subarrayBitwiseORs(int[] A) {
        int n = A.length;
        int[] dp = new int[n];
        Set<Integer> set = new HashSet<>();
        for(int len = 1; len <= n; len++){
            for(int i = 0; i <= n - len; i++){
                int j = i + len - 1;
                if(len == 1){
                    dp[i] = A[i];
                    set.add(A[i]);
                    continue;
                }
                dp[i] = dp[i] | A[j];
                set.add(dp[i]);
            }
        }
        return set.size();
    }
}

  这样做基本空间复杂度已经降下来了，上面的算法在leetcode上是无法通过的，还需要降低时间复杂度。接下来，介绍降低时间复杂度的基本思路：
  输入数组规模最大为50000，我们发现在dp数组中存在大量重复数据，可以进行状态压缩。用dp[i]存储以A[i]结尾的所有子集的位运算结果, 加上上面讲过的降维思想，只需要一个dp动态数组即可。这样做时间、空间复杂度都为O(32 * n)。

• dp_cur = {A[i], A[i] 分别与dp_pre中每个数字做或运算};

class Solution {
    public int subarrayBitwiseORs(int[] A) {
        Set<Integer> dp = new HashSet<>();
        Set<Integer> res = new HashSet<>();
        for(int i : A){
            Set<Integer> cur = new HashSet<>();
            cur.add(i);
            for(int num : dp)
                cur.add(num | i);
            res.addAll(dp = cur);
        }
        return res.size();
    }
}

做到这步，基本思路就已经完成了，接下来就是在此基础上进行进一步优化了，做不做这些优化都可以，不会因为这个就被卡掉。
我们使用一个set即可，记录上一轮的其实位置及结束位置，这样在上一轮中的数就是按从大到小排列的，之后在得到新的异或值的时候我们在当她大于当前的尾元素时才插入。

class Solution {
    public int subarrayBitwiseORs(int[] A) {
        ArrayList<Integer> res = new ArrayList<>();
        int le = 0, j = 0;
        for(int i : A){
            int len = res.size();
            res.add(i);
            for(int k = le; k < j; k++){
                int temp = res.get(k) | i;
                if(temp > res.get(res.size() - 1)) res.add(temp);
            }
            le = len;
            j = res.size();
        }
        return new HashSet(res).size();
    }
}

Runtime: 137 ms, faster than 100.00% of Java online submissions for Bitwise ORs of Subarrays.
Memory Usage: 92.7 MB, less than 33.33% of Java online submissions for Bitwise ORs of Subarrays.