班级网站建设图片手机个人简历模板下载
我回忆起六七年前的一道题鸡蛋掉落问题，有幸在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
我要表达的事什么呢？一个优秀的跳表，绝对不是均匀的跳表，也不是二分查询跳表(实现二分查询，那跳表高度会很高)，这是我用代码实现的跳表结构