先来了解一下汉明距离
在信息论中,两个等长字符串之间的汉明距离是两个字符串对应位置的不同字符的个数。换句话说,它就是将一个字符串变换成另外一个字符串所需要替换的字符个数。例如:
1011101 与 1001001 之间的汉明距离是 2。
2143896 与 2233796 之间的汉明距离是 3。
"toned" 与 "roses" 之间的汉明距离是 3。
应用
汉明距离更多的用于信号处理,表明一个信号变成另一个信号需要的最小操作(替换位),实际中就是比较两个比特串有多少个位不一样,简洁的操作时就是两个比特串进行异或之后包含1的个数。汉明距在图像处理领>域也有这广泛的应用,是比较二进制图像非常有效的手段。
科普完之后来看看Leecode上的题目:
两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。
给出两个整数x
和y
,计算它们之间的汉明距离。
注意:
0 ≤x
,y
< 231.
示例:
输入: x = 1, y = 4
输出: 2
解释:
1 (0 0 0 1)
4 (0 1 0 0)
↑ ↑
上面的箭头指出了对应二进制位不同的位置。
解答
这个问题首先要把十进制转换成二进制,在Python中有函数 bin()来解决,之后确定两个二进制之间相对位置有没有异同,这里用到了位操作
python的位操作:
描述符 | 描述 |
---|---|
& | 与操作 |
1 | 或操作 |
^ | 异或操作 |
>> | 左移位 |
<< | 右移位 |
这里要用到异或操作,用「0」也是可以计数的。代码如下:
class Solution(object):
def hammingDistance(self, x, y):
"""
:type x: int
:type y: int
:rtype: int
"""
return bin((x^y)).count('1')
本来想着用两层for循环来做,没有写出来,换一种思路,没想到一句就解决了。
看一下执行结果
还可以,看一下排名靠前的大佬代码也是这样,可能是我太菜了吧,继续努力。