20190503-漢明距離

難度分類

簡單

題目描述

兩個整數之間的漢明距離指的是這兩個數字對應二進位位不同的位置的數目。給出兩個整數 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函數一一遍歷對比

考點

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]