leetcode-461-汉明距离

2020-09-27 约 538 字预计阅读 2 分钟

题目描述

两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。

给出两个整数 x 和 y，计算它们之间的汉明距离。

注意： 0 ≤ x, y < 2^31.

示例

示例 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


输入: x = 1, y = 4

输出: 2

解释:
1   (0 0 0 1)
4   (0 1 0 0)
       ↑   ↑

上面的箭头指出了对应二进制位不同的位置。

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/hamming-distance/

解题思路

字符串计数法

题解1:

执行用时：40 ms, 在所有 Python3 提交中击败了69.61%的用户

内存消耗：13.4 MB, 在所有 Python3 提交中击败了28.26%的用户

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


class Solution:
    def hammingDistance(self, x: int, y: int) -> int:
        result = 0
        bx = bin(x)
        by = bin(y)

        max_len = max(len(bx), len(by))

        sbx = bx[2:].zfill(max_len)
        sby = by[2:].zfill(max_len)

        for _ in range(max_len):
            if sbx[_] != sby[_]:
                result = result + 1
        return result

题解2:

位运算

执行用时：36 ms, 在所有 Python3 提交中击败了87.61%的用户

内存消耗：13.4 MB, 在所有 Python3 提交中击败了21.26%的用户
1 2 3

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

题解3：

偶数位为0，奇数位为1 0x55555555 = 0b1010101010101010101010101010101
1和0每隔两位交替出现 0x33333333 = 0b110011001100110011001100110011

0x0f0f0f0f = 0b1111000011110000111100001111

0x00ff00ff = 0b111111110000000011111111

1和0每隔两位交替出现 0x0000ffff = 0b1111111111111111

1
2
3
4
5
6
7
8
9


class Solution:
def hammingDistance(self, x: int, y: int) -> int:
    z = x^y
    z = (z & 0x55555555) + ((z >> 1) & 0x55555555)
    z = (z & 0x33333333) + ((z >> 2) & 0x33333333)
    z = (z & 0x0f0f0f0f) + ((z >> 4) & 0x0f0f0f0f)
    z = (z & 0x00ff00ff) + ((z >> 8) & 0x00ff00ff)
    z = (z & 0x0000ffff) + ((z >> 16) & 0x0000ffff)
    return z

目录

leetcode-461-汉明距离

题目描述

示例