龙熠的技术小站

Leetcode : 461 Hamming Distance

汉明距离 : 汉明距离是以理查德·卫斯里·汉明的名字命名的。在信息论中,两个等长字符串之间的汉明距离是两个字符串对应位置的不同字符的个数。
简而言之,对两个字符串进行异或运算,并统计结果为1的个数,那么这个数就是汉明距离


题目

1
2
3
4
描述
The Hamming distance between two integers is the number of positions at which the corresponding bits are different.
Given two integers x and y, calculate the Hamming distance.
1
2
3
4
5
6
7
8
9
10
11
例子:
Input: x = 1, y = 4
Output: 2
Explanation:
1 (0 0 0 1)
4 (0 1 0 0)
↑ ↑
The above arrows point to positions where the corresponding bits are different.

解题思路

要比较数字的汉明距离,实际上可以转换成二进制,进行按位与

按位与会将不相等的两位变成1,相等的变成0

从而把等于1的位数加起来即为汉明距离

解题

Language : swift

Runtime : 36ms

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
代码思路:
将数字循环进行余和除运算,则每次余数的结果即为,从右往左每位的数据
如果该位为1,则结果+1,最后得到汉明距离
class Solution {
func hammingDistance(_ x: Int, _ y: Int) -> Int {
var temp : Int = x ^ y
var length : Int = 0
var divisor : Int = 0
while true {
divisor = temp % 2
temp = temp / 2
if (divisor == 1) {
length = length + 1
}
if (temp == 0) {
break
}
}
return length
}
}

Top Solutions

Top 1

Java

运用基于XOR异或运算的按位统计函数: Integer.bitCount

1
2
3
4
5
public class Solution {
public int hammingDistance(int x, int y) {
return Integer.bitCount(x ^ y);
}
}

Top 2

Java

题目限制 x,y都是>=0 <= 2的31次方
即,该题数字的位数范围从0~31

将x和y异或之后,(xor >> i) & 1 即位移后判断该位是否等于1,如果等于,则(xor >> i) & 1的结果为1,否则为0

1
2
3
4
5
6
7
public int hammingDistance(int x, int y) {
int xor = x ^ y, count = 0;
for (int i=0;i<32;i++) count += (xor >> i) & 1;
return count;
}
Note : 个人觉得每次都要遍历一遍0~31位,是一种资源和效率浪费

Top 3

Python 49ms

bin函数表示将数字转换成二进制的字符串,例如bin(521) 结果是 ‘0b1000001001’
字符串.count(‘1’) 表示统计字符串中该子字符串的数量

1
2
3
4
5
6
7
8
class Solution(object):
def hammingDistance(self, x, y):
"""
:type x: int
:type y: int
:rtype: int
"""
return bin(x^y).count('1')

Top 4

Python

这个方案优点是,x或者y可以不等长,然后用%2的方式获取到当前位数,用/2的方式移动位指针到低一位的位置上

1
2
3
4
5
6
ans = 0
while x or y:
ans += (x % 2) ^ (y % 2)
x /= 2
y /= 2
return ans
分享