数据结构算法 简单的面试思考题
目录
简单的面试思考题
思考题一
有64瓶疫苗, 其中一瓶不小心混入了有害物质, 现在要利用小白鼠找出那一瓶!
注意:小白鼠只要喝一点点混入有害物质的在30分钟就是死亡, 那么现在只剩下30分
钟了(只能进行一次实验), 问最少需要几只小白鼠可以找出那瓶混入有害物质的疫苗
使用二进制编码
1.将64瓶疫苗从0~63进行编号
2.将每一瓶疫苗的编号转为二进制表示
-
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
代码实现
-
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个球,
如果颜色相同就放回一个白球,
如果颜色不同就放回一个黑球,
问最后桶里剩下的一个球是什么颜色的球?
-
使用位运算异或^
-
相同为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);
-
}
-
}
-
文章来源: lansonli.blog.csdn.net，作者：Lansonli，版权归原作者所有，如需转载，请联系作者。
原文链接：lansonli.blog.csdn.net/article/details/116674300
- 点赞
- 收藏
- 关注作者
评论（0）