20190503-汉明距离

2023-01-31 00:01:34

难度分类

简单

题目描述

两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。给出两个整数 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]

 

相关文章