数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究C++ 中的汉明距离总和
假设我们有一列数字。我们需要找到给定数字的所有对的汉明距离。我们知道两个整数之间的汉明距离是在相应位不同的位置的数量。
因此，如果输入类似于 [4, 14, 17, 2]，则输出将为 17。
为了解决这个问题，我们将遵循以下步骤：
m := 1^9 + 7
定义一个函数 add()，它将接收 a、b，
返回 ((a mod m) + (b mod m))
定义一个函数 mul()，它将接收 a、b，
返回 ((a mod m) * (b mod m))
定义一个函数 cntBits()，它将接收一个数组 a，
定义一个大小为 32 x 2 的二维数组 bits
ans := 0, n := a 的大小
对于初始化 i := 0，当 i < n 时，更新（i 增加 1），执行：
x := a[i]
对于初始化 j := 0，当 j < 32 时，更新（j 增加 1），执行：
b := (x / 2^j) AND 1
ans := add(ans, mul(1, bits[j, b 的逆]))
bits[j, b] := add(bits[j, b], 1)
返回 ans
从主方法执行以下操作：
返回 cntBits(nums)
让我们看看以下实现以获得更好的理解：
示例
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const int m = 1e9 + 7;
class Solution {
public:
lli add(lli a, lli b){
return ((a % m) + (b % m));
}
lli mul(lli a, lli b){
return ((a % m) * (b % m));
}
int cntBits(vector<int>& a){
vector<vector<lli> > bits(32, vector<lli>(2));
lli ans = 0;
int n = a.size();
for (int i = 0; i < n; i++) {
lli x = a[i];
for (lli j = 0; j < 32; j++) {
lli b = (x >> j) & 1;
ans = add(ans, mul((lli)1, bits[j][!b]));
bits[j][b] = add(bits[j][b], (lli)1);
}
}
return ans;
}
int totalHammingDistance(vector<int>& nums){
return cntBits(nums);
}
};
main(){
Solution ob;
vector<int> v = {4,14,17,2};
cout << (ob.totalHammingDistance(v));
}输入
{4,14,17,2}输出
17
更新于： 2020-06-05
640 次查看
广告