鉴于今天的这两题题解都特别的短,所以把两题写在一起了。分别是461题简单难度的汉明距离和319题中等难度的灯泡开关。
原题地址:https://leetcode-cn.com/problems/hamming-distance/ 和 https://leetcode-cn.com/problems/bulb-switcher/
题目描述:
汉明距离:
两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。
给出两个整数 x 和 y,计算它们之间的汉明距离。
注意:0 ≤ x, y < 231.
灯泡开关:
初始时有 n 个灯泡关闭。第 1 轮,你打开所有的灯泡。第 2 轮,每两个灯泡你关闭一次。第 3 轮,每三个灯泡切换一次开关(如果关闭则开启,如果开启则关闭)。第 i 轮,每 i 个灯泡切换一次开关。对于第 n 轮,你只切换最后一个灯泡的开关。找出 n 轮后有多少个亮着的灯泡。
来源:力扣(LeetCode)
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
解题思路:
汉明距离这题,其实很简单,两个不同数字的二进制位不同位置的数目,利用位运算的异或,可以得到位置不同的二进制位组成的数字N,利用Java的Integer.bitCount可以得到N的二进制中1的数量。
灯泡开关这题,也不难,就是有点玄学,每一轮都是将第i个切换开关。比如一共8个开关,第8个开关在第1/2/4/8轮会被切换状态,第7个只会在第1/7轮切换状态。如此就会发现,一共N个灯泡,切换N轮,只有sqrt(N)个数被实际的切换了状态。
中文官网题解:
https://leetcode-cn.com/problems/hamming-distance/solution/
https://leetcode-cn.com/problems/bulb-switcher/solution/
个人题解:
/**
* 汉明距离的题解
*/
public class Solution {
public int hammingDistance(int x, int y) {
return Integer.bitCount(x ^ y);
}
}
/**
* 灯泡开关的题解
*/
public class Solution {
public int bulbSwitch(int n) {
return (int)Math.floor(Math.sqrt(n));
}
}
结果:
汉明距离的结果:
灯泡开关的结果: