当前位置： 移动技术网 > IT编程>脚本编程>Python > 20190503-汉明距离

20190503-汉明距离

2019年05月04日  | 移动技术网IT编程  | 我要评论

东营经济,电压力锅好用吗,上海空姐门

难度分类

简单

题目描述

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

注意：

0 ≤ x, y < 231.

示例:

输入: 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函数一一遍历对比

考点

  1. 十进制与二进制的转换bin函数
  2. zfill函数
  3. 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的个数即为二进制位不同的总数

进阶考点

  1. 异或运算
  2. 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]

 

您可能感兴趣的文章:

如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网