本文主要是介绍从测试鸡蛋硬度到跳表的设计,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
我回忆起六七年前的一道题鸡蛋掉落问题,有幸在leetCode上找到题目了
原题是2枚鸡蛋
leetCode有拓展,k枚鸡蛋
具体的思路是这样的。
以2枚鸡蛋验证100层为例
不能直接二分查找,因为你在50层测试时,如果直接鸡蛋碎了,那你只能从第一层慢慢测试,运气不好,49楼都不碎,需要测50次
也不能两层楼一测,万一在99楼碎,也需要测50次
那需要怎么设计呢?
比如,我第一次在k楼测试,下一次在哪一楼呢,k+k-1比较公平,为什么呢?
比如k楼碎了,极端情况,剩下k-1楼都要试验,总归k次
比如k楼没碎,k+k-1楼碎了,极端情况下,也是k次
那这里的k怎么设计呢
k+(k-1)+(k-2)+…+3+2+1 = 100,就能找到k了,就是100层下,第一次应该在哪一楼测试,发现是14楼
在理解2枚鸡蛋的基础上,我们理解3枚鸡蛋
在理解3枚鸡蛋前,我们先把问题换一下,换个问题,我们不是问100层,2个鸡蛋需要多少次
而是我有2个鸡蛋,可以做10次试验,最高可以验证的高度是多少
第一次肯定在10楼,第二次在19楼,第三次在19+8=27楼…,10次可以验证55层
现在有3枚鸡蛋,给11次试验机会,可以验证多少楼层啊?
我第一次肯定不是在11层,应该是哪一层?
应该是在第56层,因为哪怕你鸡蛋摔碎了,剩下2个鸡蛋,也可以在10次试验中完成使命
那如果没碎,第二次在哪一层呢?
56+(2枚鸡蛋9次可以验证的楼层)
理解了3枚鸡蛋,是不是可以理解4枚鸡蛋了,直至k枚鸡蛋
以上两道leetCode题不会在此解答,只提供思路
鸡蛋和试验次数,能够验证的楼层数如下
1-20次,1-10个鸡蛋,当鸡蛋数量大于次数时,数据不标准
次数 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
1 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 |
2 | 1 | 3 | 6 | 10 | 15 | 21 | 28 | 36 | 45 | 55 | 66 | 78 | 91 | 105 | 120 | 136 | 153 | 171 | 190 | 210 |
3 | 1 | 4 | 10 | 20 | 35 | 56 | 84 | 120 | 165 | 220 | 286 | 364 | 455 | 560 | 680 | 816 | 969 | 1140 | 1330 | 1540 |
4 | 1 | 5 | 15 | 35 | 70 | 126 | 210 | 330 | 495 | 715 | 1001 | 1365 | 1820 | 2380 | 3060 | 3876 | 4845 | 5985 | 7315 | 8855 |
5 | 1 | 6 | 21 | 56 | 126 | 252 | 462 | 792 | 1287 | 2002 | 3003 | 4368 | 6188 | 8568 | 11628 | 15504 | 20349 | 26334 | 33649 | 42504 |
6 | 1 | 7 | 28 | 84 | 210 | 462 | 924 | 1716 | 3003 | 5005 | 8008 | 12376 | 18564 | 27132 | 38760 | 54264 | 74613 | 100947 | 134596 | 177100 |
7 | 1 | 8 | 36 | 120 | 330 | 792 | 1716 | 3432 | 6435 | 11440 | 19448 | 31824 | 50388 | 77520 | 116280 | 170544 | 245157 | 346104 | 480700 | 657800 |
8 | 1 | 9 | 45 | 165 | 495 | 1287 | 3003 | 6435 | 12870 | 24310 | 43758 | 75582 | 125970 | 203490 | 319770 | 490314 | 735471 | 1081575 | 1562275 | 2220075 |
9 | 1 | 10 | 55 | 220 | 715 | 2002 | 5005 | 11440 | 24310 | 48620 | 92378 | 167960 | 293930 | 497420 | 817190 | 1307504 | 2042975 | 3124550 | 4686825 | 6906900 |
很容易从表里看出来,2个鸡蛋验证100层,至多14次
以上只是算法题的解答,这个和跳表有什么关系呢?
一个优秀的跳表,应该是前面跳跃更多,后面跳跃更少节点一样,第一次间隔10,第二次只能间隔9;三级的,第一次间隔55,第二次直接间隔45了
一个优秀的3层6次既能查所有的跳表如下:
总数据有83个,最长的查询step也是6
如果设计为均匀分布的跳表,在层级为3总数据为64(444)的跳表里,最长的长度达到9
我要表达的事什么呢?一个优秀的跳表,绝对不是均匀的跳表,也不是二分查询跳表(实现二分查询,那跳表高度会很高),这是我用代码实现的跳表结构
这篇关于从测试鸡蛋硬度到跳表的设计的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!