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

2023-12-03 14:10

本文主要是介绍从测试鸡蛋硬度到跳表的设计,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

我回忆起六七年前的一道题鸡蛋掉落问题,有幸在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.chinasem.cn/article/449725

相关文章

如何测试计算机的内存是否存在问题? 判断电脑内存故障的多种方法

《如何测试计算机的内存是否存在问题?判断电脑内存故障的多种方法》内存是电脑中非常重要的组件之一,如果内存出现故障,可能会导致电脑出现各种问题,如蓝屏、死机、程序崩溃等,如何判断内存是否出现故障呢?下... 如果你的电脑是崩溃、冻结还是不稳定,那么它的内存可能有问题。要进行检查,你可以使用Windows 11

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

性能测试介绍

性能测试是一种测试方法,旨在评估系统、应用程序或组件在现实场景中的性能表现和可靠性。它通常用于衡量系统在不同负载条件下的响应时间、吞吐量、资源利用率、稳定性和可扩展性等关键指标。 为什么要进行性能测试 通过性能测试,可以确定系统是否能够满足预期的性能要求,找出性能瓶颈和潜在的问题,并进行优化和调整。 发现性能瓶颈:性能测试可以帮助发现系统的性能瓶颈,即系统在高负载或高并发情况下可能出现的问题

字节面试 | 如何测试RocketMQ、RocketMQ?

字节面试:RocketMQ是怎么测试的呢? 答: 首先保证消息的消费正确、设计逆向用例,在验证消息内容为空等情况时的消费正确性; 推送大批量MQ,通过Admin控制台查看MQ消费的情况,是否出现消费假死、TPS是否正常等等问题。(上述都是临场发挥,但是RocketMQ真正的测试点,还真的需要探讨) 01 先了解RocketMQ 作为测试也是要简单了解RocketMQ。简单来说,就是一个分

【测试】输入正确用户名和密码,点击登录没有响应的可能性原因

目录 一、前端问题 1. 界面交互问题 2. 输入数据校验问题 二、网络问题 1. 网络连接中断 2. 代理设置问题 三、后端问题 1. 服务器故障 2. 数据库问题 3. 权限问题: 四、其他问题 1. 缓存问题 2. 第三方服务问题 3. 配置问题 一、前端问题 1. 界面交互问题 登录按钮的点击事件未正确绑定,导致点击后无法触发登录操作。 页面可能存在

业务中14个需要进行A/B测试的时刻[信息图]

在本指南中,我们将全面了解有关 A/B测试 的所有内容。 我们将介绍不同类型的A/B测试,如何有效地规划和启动测试,如何评估测试是否成功,您应该关注哪些指标,多年来我们发现的常见错误等等。 什么是A/B测试? A/B测试(有时称为“分割测试”)是一种实验类型,其中您创建两种或多种内容变体——如登录页面、电子邮件或广告——并将它们显示给不同的受众群体,以查看哪一种效果最好。 本质上,A/B测

怎么让1台电脑共享给7人同时流畅设计

在当今的创意设计与数字内容生产领域,图形工作站以其强大的计算能力、专业的图形处理能力和稳定的系统性能,成为了众多设计师、动画师、视频编辑师等创意工作者的必备工具。 设计团队面临资源有限,比如只有一台高性能电脑时,如何高效地让七人同时流畅地进行设计工作,便成为了一个亟待解决的问题。 一、硬件升级与配置 1.高性能处理器(CPU):选择多核、高线程的处理器,例如Intel的至强系列或AMD的Ry

基于51单片机的自动转向修复系统的设计与实现

文章目录 前言资料获取设计介绍功能介绍设计清单具体实现截图参考文献设计获取 前言 💗博主介绍:✌全网粉丝10W+,CSDN特邀作者、博客专家、CSDN新星计划导师,一名热衷于单片机技术探索与分享的博主、专注于 精通51/STM32/MSP430/AVR等单片机设计 主要对象是咱们电子相关专业的大学生,希望您们都共创辉煌!✌💗 👇🏻 精彩专栏 推荐订阅👇🏻 单片机

SprinBoot+Vue网络商城海鲜市场的设计与实现

目录 1 项目介绍2 项目截图3 核心代码3.1 Controller3.2 Service3.3 Dao3.4 application.yml3.5 SpringbootApplication3.5 Vue 4 数据库表设计5 文档参考6 计算机毕设选题推荐7 源码获取 1 项目介绍 博主个人介绍:CSDN认证博客专家,CSDN平台Java领域优质创作者,全网30w+

单片机毕业设计基于单片机的智能门禁系统的设计与实现

文章目录 前言资料获取设计介绍功能介绍程序代码部分参考 设计清单具体实现截图参考文献设计获取 前言 💗博主介绍:✌全网粉丝10W+,CSDN特邀作者、博客专家、CSDN新星计划导师,一名热衷于单片机技术探索与分享的博主、专注于 精通51/STM32/MSP430/AVR等单片机设计 主要对象是咱们电子相关专业的大学生,希望您们都共创辉煌!✌💗 👇🏻 精彩专栏 推荐订