首页 > > 网络编程 > 其它 >

20190503-汉明距离

2019-05-04 09:41:43来源：博客园阅读 ()

难度分类

简单

题目描述

两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。给出两个整数 x 和 y，计算它们之间的汉明距离

注意：

0 ≤ x, y < 2³¹.

示例:

输入: x = 1, y = 4

输出: 2

解释:

1 (0 0 0 1)

4 (0 1 0 0)

↑ ↑

上面的箭头指出了对应二进制位不同的位置。

算法

1．获取x,y的二进制的字符串

2．使用zfill函数将x,y的二进制字符串中较短的字符串的长度用‘0’填充成与较长位字符串长度一样长

3．使用zip函数一一遍历对比

考点

十进制与二进制的转换bin函数
Zfill函数
zip函数

代码

def hammingDistance(self, x, y):
        #step1:转换二进制
        binary_x = bin(x)[2:]
        binary_y = bin(y)[2:]
        #step2:调整长度
        if len(binary_x)>len(binary_y):
            binary_y = binary_y.zfill(len(binary_x))
        else:
            binary_x = binary_x.zfill(len(binary_y))
        result=0
        #step3:按位对比，统计不同的位数
        for i,j in zip(binary_x,binary_y):
            if i!=j:
                result+=1

进阶算法

统计二进制位不同的可使用二进制异或运算，然后统计结果二进制的1的个数。异或运算即二进制下不进位加法，二进制的异或运算法则如下：

1． 0+0=0

2． 0+1=1

3． 1+0=1

4． 1+1=0

示例中0001^0100=0101,统计0101中1的个数即为二进制位不同的总数

进阶考点

异或运算
str.count()函数

进阶代码

def hammingDistance(self, x, y):
        """
        :type x: int
        :type y: int
        :rtype: int
        """
        return bin(x^y).count('1')

附-十进制转换二进制代码

 def binary_transfer(x):
            result = ''
            while x!=0:
                result+=str(x%2)
                x = x//2
            return result[::-1]

原文链接:https://www.cnblogs.com/hyj691001/p/10806160.html
如有疑问请与原作者联系

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有