สมมติว่าเรามีอาร์เรย์ของจำนวนเต็ม 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