LeetCode笔记:汉明距离

问题

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

给你两个整数 xy,计算并返回它们之间的汉明距离。

示例 1:

输入: x = 1, y = 4

输出: 2

解释:

1   (0  0  0  1)

4   (0  1  0  0)

        ▲     ▲

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

示例 2:

输入: x = 3, y = 1

输出: 1

提示:

  • 0 <= x, y <= 231 - 1

解法一

思路:

  1. 将十进制转化为二进制
  2. 较短的二进制数字,左边补 0,补成和第二个数字一样长的字符串,便于比较,因为左边的 0 不会影响原始值
  3. 遍历二进制字符串,统计不同字符的个数

代码:

/**
 * @param {number} x
 * @param {number} y
 * @return {number}
 */
var hammingDistance = function (x, y) {
  // 十进制转为二进制
  let xToBinary = x.toString(2);
  let yToBinary = y.toString(2);

  // 获取长度
  const xLength = xToBinary.length;
  const yLength = yToBinary.length;

  // 取两者最长
  const maxLength = Math.max(xLength, yLength);

  // 较短的数字左边补0,补成和第二个数字一样长的字符串
  if (xLength < maxLength) {
    xToBinary = "0".repeat(maxLength - xLength) + xToBinary;
  } else if (yLength < maxLength) {
    yToBinary = "0".repeat(maxLength - yLength) + yToBinary;
  }

  // 遍历字符串,统计不同字符的个数
  let count = 0;
  for (let i = 0; i < maxLength; i++) {
    if (xToBinary[i] !== yToBinary[i]) {
      count++;
    }
  }

  return count;
};

解法二

思路:

1. 用按位异或^来取得 x 和 y 中不同的数字的个数。

我们复习下按位异或的特性,相同为 0,不同为 1,如下:

aba XOR b
000
011
101
110

2. 统计得到的二进制数字中 1 的个数,就是结果值,我们使用按位与 &的特性。

我们复习下按位与的特性,两个数都是 1 结果为 1,否则为 0,如下:

aba AND b
000
010
100
111

num & (num - 1)可以将num二进制数字最右边的 1 转化为 0

转化的原理如下:

  • num = 3

3 最右边的 1 是倒数第一位的数字

3      (1  1)

2      (1  0)

3 & 2  (1  0)
  • num = 10

10 最右边的 1 是倒数第二位的数字

10      (1  0  1  0)

9       (1  0  0  1)

10 & 9  (1  0  0  0)

复制以下代码到控制台可以看到打印结果:

console.log((3).toString(2)); // 输出:11
console.log((2).toString(2)); // 输出:10
console.log((3 & 2).toString(2)); // 输出:10(最右边的1转化为了0)

console.log((10).toString(2)); // 输出:1010
console.log((9).toString(2)); // 输出:1001
console.log((10 & 9).toString(2)); // 输出:1000(最右边的1转化为了0)

每转化一次,计数一次,最后得到的结果就是num二进制数字中 1 的个数。

注意这里num总是为十进制的数字,转化效果会在二进制表示中进行。

代码:

/**
 * @param {number} x
 * @param {number} y
 * @return {number}
 */
var hammingDistance = function (x, y) {
  // 按位异或,使得所有不同的数字计为1
  let num = x ^ y;

  // 统计二进制中1的个数
  let count = 0;
  while (num) {
    // 将二进制数字最右边的1转化为0
    num = num & (num - 1);
    // 每转化一次1,计数一次
    count++;
  }
  return count;
};

或者我们抽离出一个通用方法来专门统计二进制中 1 的个数。

/**
 * @param {number} x
 * @param {number} y
 * @return {number}
 */
var hammingDistance = function (x, y) {
  // 按位异或,使得所有不同的数字计为1
  let num = x ^ y;

  // 统计二进制中1的个数
  return countBinaryOne(num);
};

/**
   统计二进制中1的个数
 * @param {number} num
 * @return {number}
 */
var countBinaryOne = function (num) {
  let count = 0;
  while (num) {
    // 将二进制数字最右边的1转化为0
    num = num & (num - 1);
    // 每转化一次1,计数一次
    count++;
  }
  return count;
};

解法三

思路:

1. 这是对解法二的升级,我们还是先用按位异或^来转化数字,统计数字 1 的个数,我们改造统计二进制中 1 的个数的函数

2. 执行num & 1,任意一个数字和数字 1 按位与,就能判断最右边的二进制数字是否为 1,为 1 就计数,不为 1 不计数

判断的原理如下:

  • num = 3

3 最右边的二进制数字为 1

3      (1  1)

1      (0  1)

3 & 1  (0  1)
  • num = 10

10 最右边的二进制数字为 0

10      (1  0  1  0)

1       (0  0  0  1)

10 & 1  (0  0  0  0)

复制以下代码到控制台可以看到打印结果:

console.log((3).toString(2)); // 输出:11
console.log((1).toString(2)); // 输出:1
console.log((3 & 1).toString(2)); // 输出:1(3的最右边为1)

console.log((10).toString(2)); // 输出:1010
console.log((1).toString(2)); // 输出:1010
console.log((10 & 1).toString(2)); // 输出:0(10的最右边为0)

3. 最右边的数字计数之后,我们用右移运算符>>将数字右移一位,移除最右边的二进制数字

注意:右移位赋值x >>= 1 是右移运算x = x >> 1结果的简写

执行右移运算符:

  • num = 3
3       (1  1)3 >> 1  (0  1)
  • num = 10
10       (1  0  1  0)

          ▲  ▲  ▲

10 >> 1  (0  1  0  1)

             ▲  ▲  ▲

复制以下代码到控制台可以看到打印结果:

console.log((3).toString(2)); // 输出:11
console.log((3 >> 1).toString(2)); // 输出:1

console.log((10).toString(2)); // 输出:1010
console.log((10 >> 1).toString(2)); // 输出:101

4. 然后接着循环对最右边的数字进行判断计数,直到数字变为 0 停止

代码:

/**
 * @param {number} x
 * @param {number} y
 * @return {number}
 */
var hammingDistance = function (x, y) {
  // 按位异或,使得所有不同的数字计为1
  let num = x ^ y;

  // 统计二进制中1的个数
  return countBinaryOne(num);
};

/**
   统计二进制中1的个数
 * @param {number} num
 * @return {number}
 */
var countBinaryOne = function (num) {
  let count = 0;
  while (num) {
    // 判断最右边数字是否为1,结果为1则加1,为0则加0
    count += num & 1;
    // 最右边的数字已经统计完毕,右移消除它
    num >>= 1;
  }
  return count;
};

参考

评论