LeetCode笔记：汉明距离

#leetcode

问题

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

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

示例 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;
};

参考

评论