題目

難度：★☆☆☆☆
類型：數(shù)學(xué)

兩個(gè)整數(shù)之間的漢明距離指的是這兩個(gè)數(shù)字對(duì)應(yīng)二進(jìn)制位不同的位置的數(shù)目。

給出兩個(gè)整數(shù) x 和 y，計(jì)算它們之間的漢明距離。

注意：
0 ≤ x, y < 231.

示例

輸入: x = 1, y = 4

輸出: 2

解釋:

1   (0 0 0 1)
4   (0 1 0 0)
       ↑   ↑

上面的箭頭指出了對(duì)應(yīng)二進(jìn)制位不同的位置。

解答

方案1：計(jì)數(shù)

這道題很簡單，最簡單的思路是將兩個(gè)字符轉(zhuǎn)為二進(jìn)制數(shù)，然后一一比較各位，統(tǒng)計(jì)不相等的個(gè)數(shù)。

class Solution:
    def hammingDistance(self, x: int, y: int) -> int:
        def dec2bin(x):
            """
            將十進(jìn)制數(shù)轉(zhuǎn)換為二進(jìn)制數(shù)，以從低到高位的列表形式
            例如輸入：6，輸出：[0, 1, 1]
            :param x: 輸入十進(jìn)制數(shù)
            :return: 逆序二進(jìn)制各位列表
            """
            res = []
            while x:
                r, x = x % 2, x // 2
                res.append(r)
            return res

        def hamming(a: list, b: list):
            """
            計(jì)算兩個(gè)二進(jìn)制數(shù)的漢明距離
            :param a: 輸入兩個(gè)二進(jìn)制各位逆序列表
            :param b: 
            :return: 
            """
            count = 0                                   # 初始化計(jì)數(shù)器
            for i in range(max(len(a), len(b))):
                a_bit = a[i] if i < len(a) else 0       # 提取a列表當(dāng)前位
                b_bit = b[i] if i < len(b) else 0       # 提取b列表當(dāng)前位
                count = count if a_bit == b_bit else count + 1  # 如果提取出的兩個(gè)數(shù)字不相等，計(jì)數(shù)器+1
            return count

        return hamming(dec2bin(x), dec2bin(y))

方案2：異或

漢明距離的本質(zhì)是兩個(gè)數(shù)異或后字符"1"的個(gè)數(shù)，可以直接使用異或?qū)崿F(xiàn)。

兩數(shù)異或后相同的位計(jì)算結(jié)果為零，不同的位計(jì)算結(jié)果為一。

class Solution:
    def hammingDistance(self, x: int, y: int) -> int:
        return bin(x^y).count('1')

如有疑問或建議，歡迎評(píng)論區(qū)留言~