【LeetCode 461】汉明距离

不念不忘少年蓝@ 2022-11-30 05:44 78阅读 0赞

#### 题目描述 ####

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

给出两个整数 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
    };

#### 提交结果 ####

![在这里插入图片描述][20200823225304392.png]

**异或：**  
![在这里插入图片描述][20200823231528887.png_pic_center]

[20200823225304392.png]: /images/20221124/0be176058c1a405481bddefc1f941325.png?
[20200823231528887.png_pic_center]: /images/20221124/5ddea0ba867545bbbc0a1a532ea83f86.png