資料結構
網路
關係資料庫管理系統
作業系統
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 次檢視
廣告