简单的面试思考题
思考题一
有64瓶疫苗, 其中一瓶不小心混入了有害物质, 现在要利用小白鼠找出那一瓶!
注意:小白鼠只要喝一点点混入有害物质的在30分钟就是死亡, 那么现在只剩下30分
钟了(只能进行一次实验), 问最少需要几只小白鼠可以找出那瓶混入有害物质的疫苗
使用二进制编码
1.将64瓶疫苗从0~63进行编号
2.将每一瓶疫苗的编号转为二进制表示
代码语言：javascript复制package cn.itcast.test;
/**
* Author itcast
* Desc
*/
public class Test01 {
public static void main(String[] args){
for (int i = 0; i <= 63; i ) {
System.out.println(i ":" Integer.toBinaryString(i));
}
}
}00:000000
01:000001
02:000010
03:000011
04:000100
05:000101
06:000110
07:000111
08:000000
09:000001
10:000010
11:000011
12:000100
13:000101
14:000110
15:000111
16:010000
17:010001
18:010010
19:010011
20:010100
21:010101
22:010110
23:010111
24:011000
25:011001
26:011010
27:011011
28:011100
29:011101
30:011110
31:011111
32:100000
33:100001
34:100010
35:100011
36:100100
37:100101
38:100110
39:100111
40:101000
41:101001
42:101010
43:101011
44:101100
45:101101
46:101110
47:101111
48:110000
49:110001
50:110010
51:110011
52:110100
53:110101
54:110110
55:110111
56:111000
57:111001
58:111010
59:111011
60:111100
61:111101
62:111110
63:111111
-----------
******3.拿出6只小白鼠和上面的6个二进制位一一对应
4.然后这6只小白鼠喝对应的二进制位是1的疫苗(只喝一点点即可)
如左边第一只,喝32~63
如右边第一只,喝编号是奇数的
...其他的类似
5.30分钟后观察结果,看哪些小白鼠死了既可以推断出混入有害物质的疫苗
如: 都没死, 那么0号000000混入有害物质
如: 都死了, 那么63号111111混入有害物质
如: 从左边开始135死了,那么 42号101010混入有害物质
- 原理:
现代科学实验思想: 通过现象猜想本质 , 通过本质/原理,也可以推导可能发生的现象
- 如:
观察到先看见闪电, 后听到雷声, 我猜想: 光速比声速快
而事实也是确实是光速比声速快,所以先看见闪电, 后听到雷声
思考题二
有 1~ n, n个数字(n很大,但不一定有序),
但是不小心丢了其中一个,
让写代码找出丢的哪一个! 要求效率最高
- 可能的解法
1.排序 二分(效率太低,因为要排序)
2.先求1~n的和((1 n)*n/2)再减去n-1个数,最后的结果的数就是丢失的数(已经很快了,但是还是要进行加减法)
3.位运算比加减法还要快
&与
|或
!非
^异或
^异或的特点:
二进制:
1001
^1001
-----
0000
1001
^0110
------
1111
所以异或的特点是二进制位相同为0,不同为1
那么推广到1~n,相同的数据异或为0,不同的先不管
1010
^0000
-----
1010
一个数和0进行异或等于这个数本身
且异或满足交换律,异或顺序可以随便调
1 ^ 2 ^ 3 ....^n--这是有丢失的
^1 ^ 2 ^ 3 .x..^n--这是没有丢失的
-----------------
0^0^0....^x = x代码实现
代码语言：javascript复制package cn.itcast.test;
/**
* Author itcast
* Desc
*/
public class Test02 {
public static void main(String[] args) {
int result = 0;
int[] arr1 = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};//完整的
int[] arr2 = new int[]{1, 2, 3, 4, 0, 6, 7, 8, 9, 10};//丢失了一个数的
for (int i = 0; i < arr1.length; i ) {
if (i == 0) {
result = arr1[i] ^ arr2[i];
} else {
//result = result ^ (arr1[i] ^ arr2[i]);
result ^= (arr1[i] ^ arr2[i]);
}
}
System.out.println("丢失的数为:" result);
}
}思考题三
有1个桶里面有100个黑球,100个白球, 桶外还有足够的黑球白球
现在从桶里每次随机取出2个球,
如果颜色相同就放回一个白球,
如果颜色不同就放回一个黑球,
问最后桶里剩下的一个球是什么颜色的球?
代码语言：javascript复制使用位运算异或^
相同为0,不同为1
所以令白球为0,黑球为1
那么题目就变成了100个0和100个1进行^
0 ^ 0 ^ 0....^ 0 ==0
1 ^ 1 ^ 1....^ 1 == 0
------------------
0是白球package cn.itcast.test;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
/**
* Author itcast
* Desc
*/
public class Test03 {
public static void main(String[] args) {
List<Integer> list = new ArrayList<>();
for (int i = 1; i <= 100; i ) {
list.add(0);//白球
list.add(1);//黑球
}
Random random = new Random();
while (list.size() > 1) {
Integer i1 = list.get(random.nextInt(list.size()));
Integer i2 = list.get(random.nextInt(list.size()));
list.remove(i1);//移除该对象
list.remove(i2);//移除该对象
list.add(i1 ^ i2);
}
System.out.println(list);
}
}
