Bitwise OR của các phân khu trong C ++

Giả sử chúng ta có một mảng A gồm các số nguyên không âm. Đối với mọi mảng con (liền kề) nói rằng B =[A [i], A [i + 1], ..., A [j]] (với i <=j), chúng ta sẽ thực hiện theo từng bit HOẶC của tất cả các phần tử trong B, thu được kết quả A [i] | A [i + 1] | ... | Một [j]. Chúng ta phải tìm số lượng các kết quả có thể xảy ra. (Các kết quả xuất hiện nhiều hơn một lần chỉ được tính một lần trong câu trả lời cuối cùng.)

Vì vậy, nếu đầu vào là [1,1,2], thì kết quả sẽ là 3 vì các mảng con là [1], [1], [2], [1,1], [1,2], [1, 1,2], sau đó kết quả sẽ là 1,1,2,1,3,3, sau đó có ba kết quả khác biệt.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Tạo hai bộ ret và curr2

• cho tôi trong phạm vi từ 0 đến kích thước của mảng

  • tạo một tập hợp curr1, chèn A [i] vào đó

  • cho mỗi phần tử e trong curr2 -

    • chèn (e HOẶC A [i]) vào curr1

  • cho mỗi phần tử e curr1

    • chèn e trong ret

  • curr2:=curr1

• kích thước trả về của ret

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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));
}

Đầu vào

[1,1,2]

Đầu ra

3