乐趣区

汉明距离Python3

问题提出:两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。给出两个整数 x 和 y,计算它们之间的汉明距离。注意:0 ≤ x, y < 2^31。

解题思路:对两数进行二进制求解(使用递归算法),然后从两个二进制的末尾比较每一位是否相等,如果其中一个二进制数全部遍历,判断另一个二进制数是否遍历完,若未遍历完,遍历剩下位数,其中位数如果为 1,则汉明距离 +1。(因为之前遍历完的二进制数当前位必然为 0)
直接上代码 (~▽~):

class Solution:
    # 二进制转换
    def bina(self,num):
        b = ''
        if num:
            b = self.bina(num//2)
            return b + str(num%2)
        else:
            return b
        

    def hammingDistance(self, x: int, y: int) -> int:
        bin_x = self.bina(x)
        bin_y = self.bina(y)
        i = len(bin_x)-1
        j = len(bin_y)-1
        count = 0
        while i>=0 and j>=0:
            if bin_x[i]!=bin_y[j]:
                count+=1
            i-=1
            j-=1
        if j>=0:
            while j>=0:
                if bin_y[j]=='1':
                    count+=1
                j-=1
        if i>=0:
            while i>=0:
                if bin_x[i]=='1':
                    count+=1
                i-=1
        return count

时间和空间消耗:

原题链接:https://leetcode-cn.com/probl…

退出移动版