資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會研究
時尚研究
法律研究C++ 中使用位運算相等的零查詢三元組
假設我們有一個整數陣列 A。我們需要找出滿足以下條件的索引 (i, j, k) 三元組數量：
0 <= i < A 的大小
0 <= j < A 的大小
0 <= k < A 的大小
A[i] AND A[j] AND A[k] 為 0，其中 AND 表示按位 AND 運算子。
因此，如果輸入類似 [3,1,2]，則輸出將為 12
為了解決這個難題，我們將遵循以下步驟：
宣告一個對映 m
ret := 0
n := A 的大小
對於初始化 i := 0，當 i < n 時，更新 (將 i 增加 1)，執行以下操作：
對於初始化 j := 0，當 j < n 時，更新 (將 j 增加 1)，執行以下操作：
對於初始化 j := 0，當 j < n 時，更新 (將 j 增加 1)，執行以下操作：
對於初始化 i := 0，當 i < n 時，更新 (將 i 增加 1)，執行以下操作：
x := A[i]
對於對映 m 中的所有鍵值對 a
如果 (a.key AND x) 與 0 相同，則：
ret := ret + a.value
返回 ret
讓我們看看以下實現，以便更好地理解：
例子
#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
更新於： 04-6 月-2020
142 次瀏覽
廣告