C ++中子数组的按位或
假设我们有一个非负整数的数组A。对于每个(连续)子数组,说B=[A[i],A[i+1],...,A[j]](其中i<=j),我们将对其中的所有元素进行按位或运算B,获得结果A[i]|A[i+1]|...|A[j]。我们必须找到可能的结果数量。(多次出现的结果只会在最终答案中计算一次。)
因此,如果输入类似于[1,1,2],则结果将为3,因为子数组为[1],[1],[2],[1,1],[1,2],[1,1,2],则结果将是1,1,2,1,3,3,然后有三个不同的结果。
为了解决这个问题,我们将遵循以下步骤-
创建两组ret和curr2
对于范围在0到数组大小的i
将e插入ret
在curr1中插入(eORA[i])
设置一个curr1,在其中插入A[i]
对于curr2中的每个元素e-
对于每个元素curr1
curr2:=curr1
ret的返回大小
示例
让我们看下面的实现以更好地理解-
#include <bits/stdc++.h> using namespace std; class Solution { public: int subarrayBitwiseORs(vector<int>& A) { unordered_set <int> ret; unordered_set <int> curr2; for(int i = 0; i < A.size(); i++){ unordered_set <int> curr1; curr1.insert(A[i]); unordered_set<int>::iterator it = curr2.begin(); while(it != curr2.end()){ curr1.insert(*it | A[i]); it++; } it = curr1.begin(); while(it != curr1.end()){ ret.insert(*it); it++; } curr2 = curr1; } return ret.size(); } }; main(){ vector<int> v = {1,1,2}; Solution ob; cout << (ob.subarrayBitwiseORs(v)); }
输入项
[1,1,2]
输出结果
3