当前位置: 首页 > news >正文

从测试鸡蛋硬度到跳表的设计

我回忆起六七年前的一道题鸡蛋掉落问题,有幸在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个鸡蛋,当鸡蛋数量大于次数时,数据不标准

次数1234567891011121314151617181920
11234567891011121314151617181920
213610152128364555667891105120136153171190210
3141020355684120165220286364455560680816969114013301540
4151535701262103304957151001136518202380306038764845598573158855
5162156126252462792128720023003436861888568116281550420349263343364942504
61728842104629241716300350058008123761856427132387605426474613100947134596177100
718361203307921716343264351144019448318245038877520116280170544245157346104480700657800
8194516549512873003643512870243104375875582125970203490319770490314735471108157515622752220075
911055220715200250051144024310486209237816796029393049742081719013075042042975312455046868256906900

很容易从表里看出来,2个鸡蛋验证100层,至多14次

以上只是算法题的解答,这个和跳表有什么关系呢?
一个优秀的跳表,应该是前面跳跃更多,后面跳跃更少节点一样,第一次间隔10,第二次只能间隔9;三级的,第一次间隔55,第二次直接间隔45了

一个优秀的3层6次既能查所有的跳表如下:
总数据有83个,最长的查询step也是6
在这里插入图片描述
如果设计为均匀分布的跳表,在层级为3总数据为64(444)的跳表里,最长的长度达到9
在这里插入图片描述
我要表达的事什么呢?一个优秀的跳表,绝对不是均匀的跳表,也不是二分查询跳表(实现二分查询,那跳表高度会很高),这是我用代码实现的跳表结构

http://www.lryc.cn/news/27853.html

相关文章:

  • 3D立体视觉成像原理介绍【一 】
  • CEC2021:鱼鹰优化算法(Osprey optimization algorithm,OOA)求解CEC2021(提供MATLAB代码
  • 0301_对应的南京比特物联网
  • 钡铼技术BL302 ARM工控机QT图形化界面开发的实践
  • Python try except异常处理详解(入门必读)
  • 信息系统基本知识(三)软件工程
  • Linux下软件部署安装管理----rpmbuild打包rpm包部署安装
  • ThreadLocal学会了这些,你也能和面试官扯皮了!
  • 【存储】存储特性
  • Qt使用OpenGL进行多线程离屏渲染
  • Vue基础入门讲义(三)-指令
  • pod资源限制,探针(健康检查)
  • Python | 蓝桥杯进阶第一卷——字符串
  • 2023-03-03 mysql列存储-cpu占用100%-追踪思路
  • JVM—类加载子系统
  • 在codeIgniter3中session.php中的数组追加值
  • Windows环境下Gpu版本的Pytorch安装
  • 项目实战典型案例13——学情页面逻辑问题
  • 工作日志day02
  • C++Primer16.1.6节练习
  • 初尝并行编程
  • keepalived学习记录:对其vip漂移过程采用gdb跟踪
  • 51单片机串口通讯原理及程序源码-----day8
  • mongodb入门到使用(下)
  • 云HIS系统源码 医院his源码 云his源码
  • 朴素贝叶斯法学习笔记
  • vscode与C++安装与使用【不好用来骂我】
  • C++11使用多线程(线程池)计算相似度实现性能优化
  • 【测绘程序设计】——平面坐标转换
  • 五子棋的设计与实现