X

LEETCODE 461. Hamming Distance 解题思路分析

题目大意:

汉明距离

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

给你两个整数 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

解题思路分析:

这是一道简单题目,如果你没有思路的话你可以先把题目想像成我们熟悉的10进制,如果判断两个10进制数字每一位上是否相同,我们可以从低位向高位逐一判断,我们使用当前数字和10进行余运算,就能得到最低位上的数字,比如25%10=5, 167%10=7等等。之后将数字除以十取整数部分,这样就去掉了数字的最后一位,接下来重复上述操作即可。

二进制也一样,取得最低位数字时我们用当前数字和2取余数即可,比如25%2=1,18%2=0等等。接下来和十进制操作同理,我们将数字除以2并取整数部分,这样就去掉了10进制数字对应的二进制数字的最后一位。这里我们也可以使用位运算来做去掉最后一位的操作。比如 25 / 2 可以写成 25 >> 1。

实现代码:

class Solution {
    public int hammingDistance(int x, int y) {
        int res = 0; // 返回结果
        while(x>0 || y>0){ // 循环每一位上的数字
            if(x%2 != y%2) res++; // 如果两数字最低位不相同,返回结果加一
            x>>=1; // 将数字右移一位。等同于除2操作,二进制中除以2就相当于去掉了最后一位
            y>>=1; // 
        }
        return res;
    }
}

本题解法执行时间为0ms。

Runtime: 0 ms, faster than 100.00% of Java online submissions for Hamming Distance.Memory Usage: 35.9 MB, less than 60.28% of Java online submissions for Hamming Distance.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-461-hamming-distance-解题思路分析/
Categories: leetcode
kwantong: