Computer >> คอมพิวเตอร์ >  >> การเขียนโปรแกรม >> C++

สามเท่าด้วย Bitwise และเท่ากับศูนย์ใน C++


สมมติว่าเรามีอาร์เรย์ของจำนวนเต็ม A เราต้องหาจำนวนสามตัวของดัชนี (i, j, k) ให้ได้ −

  • 0 <=i <ขนาดของ A

  • 0 <=j <ขนาดของ A

  • 0 <=k <ขนาดของ A

A[i] AND A[j] AND A[k] คือ 0 โดยที่ AND แทนตัวดำเนินการ bitwise-AND

ดังนั้นหากอินพุตเป็น [3,1,2] ผลลัพธ์จะเป็น 12

  • เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

  • กำหนดหนึ่งแผนที่ m

  • ยกเลิก :=0

  • n :=ขนาดของ A

  • สำหรับการเริ่มต้น i :=0 เมื่อ i

    • สำหรับการเริ่มต้น j :=0 เมื่อ j

      • สำหรับการเริ่มต้น j :=0 เมื่อ j

  • สำหรับการเริ่มต้น i :=0 เมื่อ i

    • x :=A[i]

    • สำหรับคู่คีย์-ค่าทั้งหมด a ในหน่วย m

      • ถ้า (a.key AND x) เท่ากับ 0 แล้ว −

        • ret :=ret + a.value

  • รีเทิร์น

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int countTriplets(vector<int>& A){
      unordered_map<int, int> m;
      int ret = 0;
      int n = A.size();
      for (int i = 0; i < n; i++) {
         for (int j = 0; j < n; j++) {
            m[A[i] & A[j]]++;
         }
      }
      for (int i = 0; i < n; i++) {
         int x = A[i];
         for (auto& a : m) {
            if ((a.first & x) == 0) {
               ret += a.second;
            }
         }
      }
      return ret;
   }
};
main(){
   Solution ob;
   vector<int> v = {3,1,2};
   cout << (ob.countTriplets(v));
}

อินพุต

{3,1,2}

ผลลัพธ์

12