数据结构
网络
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 次浏览
广告