首页 > 代码库 > 由2个鸡蛋从100层楼下落到HashMap的算法优化联想

由2个鸡蛋从100层楼下落到HashMap的算法优化联想

  题目:

有一栋楼共100层,一个鸡蛋从第N层及以上的楼层下落会摔破,在第N层以下的楼层不会摔破,给你两个鸡蛋,设计方案找出N,并且保证在最坏的情况下,最小化鸡蛋下落的次数。(鸡蛋没有摔破是可以重复利用的)

 

  在这里,熟悉HashMap的底层实现的同学可能会想到,这里给你两个鸡蛋其实是给你两次机会做测试,第一次机会可以联想到通过HashCode的值来作为数组的分组存储依据,第二个鸡蛋则是让你在LinkList中遍历用的。即两次的操作,一次分组,一次遍历,通过两次操作即能确保找出那个层数N。但是这里略有不同的是它让你计算的次数N其中包括了你第一个鸡蛋的测试次数,所以相较于HashMap的均等分法,这里或许要采取别的不同分组方式。

  首先要确定那个楼层,要么是从底层遍历上去(效率低次数多不采取),要么是在分段后从最高段的底层遍历上去。在这里,我假设X等于测试次数,第一次在Y层下落。

  1.第一个鸡蛋先从第Y层下落。

    如果碎了,就用第二个鸡蛋从底层开始遍历,此时找出N的最大次数X=1+(Y-1),也就是说第一次下落的层数Y和X是相等的

    如果没有碎,就找下一段

  2.第二个鸡蛋从X+(X-1)下落,因为如果你的这一次摔碎了,你就用了只剩X-2次机会来遍历那一段了,而从X层到X+(X-1)层中间正好有X-2的层数配合你的剩余次数。

    如果碎了,从X+1层开始遍历到X+(X-1),而此时的次数正好是2+(2X-1-(X+1))=X 吻合假设次数

    如果没碎,再找下一段

  3.剩余的工作就是继续重复,直至X+(X-1)+(X-2)+……+2+1>=100

        解得X=14

        也就是从第14层开始扔第一个蛋

由2个鸡蛋从100层楼下落到HashMap的算法优化联想