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