一切要从一瓶有毒的水和一群可怜的老鼠说起

有 1000 个一模一样的瓶子,其中有 999 瓶是普通的水,有一瓶是毒药。任何喝下毒药的生物都会在一星期之后死亡。现在,你只有 10 只小白鼠和一星期的时间,如何检验出哪个瓶子里有毒药?(hint: 有毒的无论怎么稀释都有毒哦)

首先给瓶子编号,默认 1 - 1000,考虑到老鼠喝了水之后就是死或者不死的状态。因为老鼠的个数是有限的,所以肯定是要想办法通过混合的方法。具体怎么混合呢?想象一下,10 只老鼠按照死和不死的状态而言,能够表示出 Pow(2, 10) = 1024 种信息。现在的情况是 1000 个瓶子,如果说用二进制表示就是

1
2
3
4
5
6
7
8
9
1 1
2 10
3 11
4 110
5 111
6 1110
...
999 1111100111
1000 1111101000

最大的 1000 用二进制表示是 1111101000 总计 10 位。如果把 1 到 1000 的每个数都用 n = 1..10 位二进制表示就不难发现只要把第 n 位为 1 的数找出来,混在一起给编号也为 n 的小老鼠喝。那么小老鼠如果死了就说明毒药肯定在第 n 位为 1 的瓶子中。最后再确定一个 10 位二进制数转换为 10 进制就找到了。同理,如果这个题目告诉我们有两瓶毒药就把这 1000 瓶按照两两组合最后得到 C(1000,2) = 499500 个组合。再转换成上一种问题即可。

不用中间数交换两个数

是的没错,千万不能写成

1
2
3
int temp = a;
a = b;
b = temp;

这样做就大错特错了。所以怎么写呢?当然是位运算!

1
2
3
4
a = a ^ b;
b = a ^ b;
a = a ^ b;
`

单身数

一个整数数组,里面的数字都出现两次,只有一个数字出现了一次,我们管它叫单身数字,你要写代码找到这个单身数字。我们知道相同数字异或得到 0,0 和任何数字异或都是那个数字。说明只需要把数组中所有数异或即可。

1
2
3
4
5
public int findSingleNumber(int[] nums) {
int result = 0;
for (int num: nums) result ^= num;
return result;
}