个人 备案 多个网站,wordpress增加内链,中国建设银行行网站,北京网站优化技术题记#xff1a;
两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。
给你两个整数 x 和 y#xff0c;计算并返回它们之间的汉明距离。
示例 1#xff1a; 输入#xff1a;x 1, y 4 输出#xff1a;2 解释#xff1a; 1 (0 0 0 1) 4 (0 1 0 0…题记
两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。
给你两个整数 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 2 ^ 31 - 1
题目来源 作者LeetCode 链接https://leetcode.cn/leetbook/read/top-interview-questions-easy/xnyode/ 来源力扣LeetCode
解题方法
x和y都转化为二进制的时候在相同的位置上如果值都一样他们的汉明距离就是0。如果在相同的位置上值不一样有多少个不一样的位置那么汉明距离就是多少。所以看到这道题我们应该最容易想到的就是先异或运算然后再计算这个异或运算的结果在二进制表示中1的个数。代码如下
public int hammingDistance(int x, int y) {return Integer.bitCount(x ^ y);
}一行代码搞定这题实际上没什么难度我们只需要计算x和y的异或结果然后再计算这个结果的二进制中1的个数即可。在之前我们分3个系列分别讲到了二进制中1的个数
《位1的个数系列一》 《位1的个数系列二》 《位1的个数系列三》
当然这题答案非常多下面我们再来看两种写法
一右移
public int hammingDistance(int x, int y) {int xor x ^ y;int res 0;while (xor ! 0) {res xor 1;xor xor 1;}return res;
}转换为PHP代码为
function hammingDistance($x, $y) {$xor $x ^ $y;$count 0;while($xor ! 0){$count $xor 1;$xor $xor 1;}return $count;
}二不通过移位计算
前面两种方式要么是移动原数字要么是移动1这次我们不移动任何数字来计算。在位运算中有这样一个操作就是n(n-1)可以把n最右边的1给消掉。举个例子当n12的时候我们来画个图看一下 明白了这个知识点代码就很容易写了我们通过循环计算不断的把n右边的1给一个个消掉直到n等于0为止
public int bitCount(int n) {int count 0;while (n ! 0) {n n - 1;count;}return count;
}我们还可以把它给为递归的写法直接一行代码搞定
public int bitCount(int n) {return n 0 ? 0 : 1 bitCount(n (n - 1));
}转换为PHP代码为
function hammingDistance($x, $y) {$xor $x ^ $y;$count 0;while($xor ! 0){$count 1;$xor $xor - 1;}return $count;
}方法来源 作者数据结构和算法 链接https://leetcode.cn/leetbook/read/top-interview-questions-easy/xnyode/?discussionTsikCY 来源力扣LeetCode
