Code & Fun

第11天,今天刷的是一道动态规划的题目。

今天的题目是Bitwise ORs of Subarrays:

这道题的时间复杂度很高,我们用个例子来解释解法:

首先输入是[1, 2, 4],我们先看下能不能用[1, 2]的答案来推出[1, 2, 4]的答案:

[1, 2]的答案是1, 2, 3如果都与4或一下的话,会得到的是[5, 6, 7],而[1, 2, 4]的答案中应该是没有5的,那么问题出在哪里了呢?如果仔细想一下的话,会发现这里要求的是连续子数组,而以4为结尾的连续子数组只有:[4], [2, 4], [1, 2, 4],对它们进行或也就是说其实1其实是不会和4进行或运算的。

那么要和4进行或运算的数组是什么呢?答案是一个空数组和所有以2结尾的连续子数组的或运算结果,而进行完或运算后得到的结果就是所有以4结尾的或运算结果。

这时候我们就很容易想到解法了:

用一个set保存所有以A[i-1]结尾的或运算结果,记为set[i-1],然后分别与A[i]进行或运算插入到另一个set中,并在最后插入一个A[i]就可以得到set[i]

故:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
int subarrayBitwiseORs(vector<int>& A) {
int len = A.size();
if (len == 0) return 0;

unordered_set<int> res, cur, cur2;
for(auto &i: A) {
cur2 = {i};
for(auto &j : cur) cur2.insert(i | j);
cur = cur2;
for(auto &j: cur) res.insert(j);
}
return res.size();
}
};

本文首发于Code & Fun