Voyz's Studio.

LeetCode算法笔记--汉明距离

算法题 热题HOT100
字数统计: 214阅读时长: 1 min
2021/02/19 Share

LeetCode算法笔记-Day68

461. Hamming Distance

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

Given two integers x and y, calculate the Hamming distance.

1
2
3
4
5
6
7
8
9
10
11
12
13
Example:

Input: x = 1, y = 4

Output: 2

Explanation:
1   (0 0 0 1)
4   (0 1 0 0)
       ↑   ↑

The above arrows point to positions where the corresponding bits are different.

方法一

Answer：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * @param {number} x
 * @param {number} y
 * @return {number}
 */
var hammingDistance = function(x, y) {
    let res = 0,
        x_bits = x.toString(2).split(""),
        y_bits = y.toString(2).split(""),
        x_p = x_bits.length - 1,
        y_p = y_bits.length - 1;
    
    while(x_p >= 0 || y_p >= 0){
        let x_bit = typeof(x_bits[x_p]) !== 'undefined' ? x_bits[x_p] : 0,
            y_bit = typeof(y_bits[y_p]) !== 'undefined' ? y_bits[y_p] : 0;
        if(x_bit != y_bit) res += 1;
        x_p -= 1;
        y_p -= 1;
    }
    
    return res;
};

方法二：异或

Answer：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * @param {number} x
 * @param {number} y
 * @return {number}
 */
var hammingDistance = function(x, y) {
    let res = 0,
        xor = (x^y).toString(2).split("");

    for(let i=0;i<xor.length;i++){
        if(xor[i] == 1) res += 1;
    }

    return res;
};
CATALOG
  1. 1. LeetCode算法笔记-Day68
    1. 1.1. 461. Hamming Distance
    2. 1.2. 方法一
      1. 1.2.1. Answer：
    3. 1.3. 方法二：异或
      1. 1.3.1. Answer：
Total : 137
2021
2020
2019
2018
技术贴 JavaScript Flutter 算法题 热题HOT100 哈希表 滑动窗口 回溯算法 链表 二分法 矩阵 动态规划 贪心算法 指针 快速排序 迭代 二叉树 数组 快慢指针 排序 背包问题 单调栈 栈 DFS 岛屿问题 React Native React 旅行记 效率工具 python 小程序 英语 生活 足球 算法 性能优化 ES6 TypeScript koa