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.)
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
A:
首先思路是: 逐个 OR, 然后结果放到set里。 LTE了
class Solution { public: int subarrayBitwiseORs(vector<int>& A) { int n = A.size(); vector<int> V(A); unordered_set<int> S(A.begin(), A.end()); for(int len = 2;len<=n; len++){ for(int start = 0; start + len-1<n; start++){ V[start] |= A[start+len-1]; S.insert(V[start]); } } return S.size(); } };
试着 去重,依然不行。
考虑到最后可能很快都全 1 了,i.e. 2^32-1 弄个标志位,
思路像10块糖的一样. 然后做early stop check
class Solution { public: int subarrayBitwiseORs(vector<int>& A) { unordered_set<int> S(A.begin(),A.end()); vector<int> V; for(int end = 1;end<A.size();end++){ if(A[end] == A[end-1]) // skip duplicates continue; int v = A[end]; for(int j = end-1; j>=0;j--){ v |= A[j]; S.insert(v); if(v==INT_MAX) break; } } return S.size(); } };
可是 依然LTE
那么every time, 我们不是加到之前所有的数。我们是加到,之前左右数的 OR 的集合。
因此,不需要跟之前所有的数去比较。 只需要比较前一个,保护A[end -1]的就好。
class Solution { public: int subarrayBitwiseORs(vector<int>& A) { unordered_set<int> S; vector<int> V; unordered_set<int> preSet{ 0 }; // initial as 0, so can OR with anyvalue for (int end = 0; end < A.size(); end++) { if (end > 0 && A[end] == A[end - 1]) // skip duplicates continue; int v = A[end]; unordered_set<int> curSet{ 0 }; auto iter = preSet.begin(); while (iter != preSet.end()) { // at most 32 elements v += *iter; curSet.insert(v); S.insert(v); iter++; } preSet = curSet; } return S.size(); } };
NOTE: for above solution, result on VS is correct, while on leetcode, it is wrong.
No comments:
Post a Comment