【LeetCode 461】汉明距离-蒲公英云

【LeetCode 461】汉明距离

题目描述

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

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

注意：
0 ≤ x, y < 231.

示例:

输入: x = 1, y = 4
输出: 2
解释:
1   (0 0 0 1)
4   (0 1 0 0)
       ↑   ↑
上面的箭头指出了对应二进制位不同的位置。

解题思路

最直接的思路就是将两个数都转化为二进制数，这里使用的是toString()方法，该方法有一个可选的参数，表示转为的字符串的进制数。

转化成的二进制数如果位数不相等，在前面要用0补齐。最后比较对应的每一位即可。

该方法的时间复杂度为O(n)，空间复杂度为O(n)。

还有一种的方法就是使用异或操作，两个数的异或就是不同的位数，使用正则表达式进行匹配即可。

该方法的时间复杂度为O(1)，空间复杂度为O(1)。

代码实现

/** * @param {number} x * @param {number} y * @return {number} */
var hammingDistance = function(x, y) { 
    let xStr = Number(x).toString(2)
    let yStr = Number(y).toString(2)
    const xLen = xStr.length
    const yLen = yStr.length
    let res = 0
    // 将两者的位数补齐
    if(xLen > yLen){ 
        yStr = Array(xLen - yLen + 1).join('0') + yStr
    }else if(yLen > xLen){ 
        xStr = Array(yLen - xLen + 1).join('0') + xStr
    }
    for(let i = 0; i < xStr.length; i++){ 
        if(xStr[i] !== yStr[i]){ 
            res += 1
        }
    }
    return res
};

异或：

/** * @param {number} x * @param {number} y * @return {number} */
var hammingDistance = function(x, y) { 
    return ((x ^ y).toString(2).match(/[1]/g) || []).length
};