Code & Func
2019-03-11

第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
class Solution {
2
public:
3
int subarrayBitwiseORs(vector<int>& A) {
4
int len = A.size();
5
if (len == 0) return 0;
6
7
unordered_set<int> res, cur, cur2;
8
for(auto &i: A) {
9
cur2 = {i};
10
for(auto &j : cur) cur2.insert(i | j);
11
cur = cur2;
12
for(auto &j: cur) res.insert(j);
13
}
14
return res.size();
15
}
1 collapsed line
16
};
上一条动态