leetcode-461-汉明距离

题目描述

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

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

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

示例


  • 解题思路
  • 题解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
文章作者: Spaceack
文章链接: http://spaceack.com/2020/09/27/2020-09-27-leetcode-461-%E6%B1%89%E6%98%8E%E8%B7%9D%E7%A6%BB/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 丸子家的小云吞
支付宝打赏
微信打赏