(leetcode)477. 汉明距离总和2021/5/28
477. 汉明距离总和 javascript
题目:
两个整数的 汉明距离 指的是这两个数字的二进制数对应位不同的数量。
计算一个数组中,任意两个数之间汉明距离的总和。
示例
输入: 4, 14, 2
输出: 6
解释: 在二进制表示中,4表示为0100,14表示为1110,2表示为0010。(这样表示是为了体现后四位之间关系)
所以答案为:
HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.
代码1
双重循环暴力破解
var totalHammingDistance = function(nums) {
var sum = 0
for(var i =0;i<nums.length;i++){
for(var j=i+1;j<nums.length;j++){
sum += hammingDistance(nums[i],nums[j])
}
}
return sum
};
// 计算汉明距离
var hammingDistance = function(x,y){
return (x^y).toString(2).replace(/0/g,'').length;
}
代码2
- 每一位只有可能是0或者1,00和11的汉明距离都是0,所以对任意一位的汉明距离和就是当前位置0的数量 * 1的数量
- 遍历32位,每次遍历开始时把当前的0和1的计数器清0
- 将每一位的结果累加到res,就能得到最终结果
var totalHammingDistance = function(nums) {
let res = 0;
for (let i = 0; i < 32; ++i) {
let zero = 0, one = 0;
for (let n of nums) {
let bit = (n >> i) & 1;
(bit === 1) ? one++ : zero++;
}
res += zero * one;
}
return res;
};
学艺不精,还需努力💪
版权声明:本文为FemaleHacker原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。