leetcode-461-汉明距离

Spaceack

发布于 2020-11-04 14:48:40

3530

发布于 2020-11-04 14:48:40

文章被收录于专栏：编程使我快乐

题目描述

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

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

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

示例

示例 1: 来源：力扣（LeetCode）链接：

解题思路

题解1:

字符串计数法

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

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

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%的用户

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

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

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2020-09-27，如有侵权请联系 cloudcommunity@tencent.com 删除

python

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

python

登录后参与评论

0 条评论

热度