[LeetCode] 898. Bitwise ORs of Subarrays
原题链接： https://leetcode.com/problems/bitwise-ors-of-subarrays/
1. 题目介绍
We have an array A of non-negative integers.
For every (contiguous) subarray B = [A[i], A[i+1], …, A[j]] (with i <= j), we take the bitwise OR of all the elements in B, obtaining a result A[i] | A[i+1] | … | A[j].
Return the number of possible results. (Results that occur more than once are only counted once in the final answer.)
给出一个数组A，找出A的所有子列，对这些子列进行按位或运算，求所有子列按位或运算的不同结果有多少个。
Example 1:
Input: [0]
Output: 1
Explanation:
There is only one possible result: 0.
Example 2:
Input: [1,1,2]
Output: 3
Explanation:
The possible subarrays are [1], [1], [2], [1, 1], [1, 2], [1, 1, 2].
These yield the results 1, 1, 2, 1, 3, 3.
There are 3 unique values, so the answer is 3.
Example 3:
Input: [1,2,4]
Output: 6
Explanation:
The possible results are 1, 2, 3, 4, 6, and 7.
Note:
1 <= A.length <= 50000
0 <= A[i] <= 10^9
2. 解题思路
2.1 第一种动态规划-超时
根据题意，A[i] | A[i+1] | … | A[j] 的结果，是由 A[i] | A[i+1] | … | A[ j-1 ] 和A[ j ]进行或运算得到的。因此想到可以使用动态规划的思路，存储每一步的结果，然后求得最终结果。
设置一个二维数组dp。dp[ i ][ j ]的代表 A[ i ] | A[ i+1 ] | … | A[ j ]的结果是什么，同时设置一个集合set，当dp[ i ][ j ] 不在集合里时，就把dp[ i ][ j ]放进去，最后求set集合里面元素的个数。
这个方法的递推关系式为：
其中还可以进一步优化，抛弃二维数组dp[i][j] ，用int变量代替dp[i][j]
这个方法的时间复杂度为O(n^2)，但是由于n最大可以取到50000，因此就超时了。
超时的代码
class Solution {
public int subarrayBitwiseORs(int[] A) {
int length = A.length;
if(length ==0) {
return 0;
}
int a = 0;
Set<Integer> set = new HashSet<>();
for(int i = 0 ; i<length ; i++) {
a = 0;
for(int j = i ; j<length ; j++) {
a = a | A[j];
set.add(a);
}
}
return set.size();
}
}
过了80/83的样例，但是被一个数据量很大的样例拦下来了，超时。看来，如果想要成功过题，那就要想办法降低时间复杂度。
2.2 第二种动态规划-成功！
注：本方法参考了 https://zxi.mytechroad.com/blog/dynamic-programming/leetcode-898-bitwise-ors-of-subarrays/ 中的Solution 2: DP opted部分。
这个思路使用了对集合的动态规划。
假设有一个集合a[ i ]，集合a[ i ]中的元素是最后一位为A[ i ] 的元素的子列的或运算的结果。
集合a[ i ]：{A[i] , A[i] | A[i – 1] , A[i] | A[i – 1] | A[i – 2] , … , A[i] | A[i – 1] | … | A[0] }
举例来说，数组A = {1 ，2， 3， 4， 5}
那么对应的集合a[ i ] 分别是：
可以看到，对于a[ i ]集合来说，它里面的元素必定有一个是 A[ i ] 本身，其余元素都是a[ i -1 ]集合的所有元素与A[ i ]或运算的结果。
那么，这个a[ i ]集合里面，最多有多少个元素呢？答案不是 i+1个元素，而是32个！
为什么是这样呢？我来举个例子说明：
假设A数组为{ 0，1，2，3，4，8，16 }
我们把它写成二进制 { 00000，00001，00010，00011，00100，01000，10000 }
a[ 6 ] 集合里面的元素有：
然后我们对其进行或运算，因为是或运算，所以一旦某一位从0变成了1，就再也不会恢复为0零了，如果新的或运算的结果可让某一位从0变为1，那么set集合就多一个元素。
因此set集合里面的个数，就是0的位数，而int类型最多为32位，0最多为32个，所以a[ i ]集合里面，最多有32个元素。
在代码的实现中，我们可以使用集合now代替a[ i ]，使用集合before来代替a[ i -1 ]，通过这两个集合之间的互相转换来实现集合的动态规划。
同时还要使用一个总的集合ans保存所有或运算的结果，这个ans集合里元素的个数就是我们要求的答案了。
实现代码
class Solution {
public int subarrayBitwiseORs(int[] A) {
int length = A.length;
if(length == 0 ) {
return 0;
}
Set<Integer> ans = new HashSet<>();
Set<Integer> before = new HashSet<>();
for(int i = 0; i<length ;i++) {
Set<Integer> now = new HashSet<>();
//元素本身也是一个子串，需要先把元素本身加进去
now.add(A[i]);
//遍历before集合，将A[i]与before集合中的元素按位或
for (int j:before) {
now.add(A[i] | j);
}
//将now集合里面的结果都添加到总集合ans里面
ans.addAll(now);
before = now;
}
return ans.size();
}
}
3. 参考链接
https://zxi.mytechroad.com/blog/dynamic-programming/leetcode-898-bitwise-ors-of-subarrays/