这周233酱和多年未见的老友聚了聚，除了变秃了点，大家都还是当初的模样儿～
我只好把从果壳看来的防秃指南通知她。尽管没有一招制胜的卵办法，但也打消了我写防秃水文的念头...
从知乎「有哪些令人赞不绝口的算法？」话题下看到一个简略乏味的答复，是原作者「时宇电」面试腾讯的一道算法题。233酱的思考路线和作者的差不多，这里整顿后分享给大家～
题目形容
有一种玻璃杯从一栋100层的大楼扔下，该种玻璃杯超过某一层楼会摔碎。
当初给你两个杯子，问确定最低摔碎的楼层须要摔多少次？
题目剖析
这道题的假如是：最低摔碎的楼层可能是每一层楼，且概率雷同。咱们须要找一种办法，使得定位到[1-100]之间的任意一个数都是疾速的。
解题思路
最简略的办法是用一个杯子从第一层开始，一直一层层的往上试。然而这样的工夫复杂度是O(n)。直觉也通知咱们想放大步子扔。
因为咱们有两个杯子，能够思考成一个杯子Cup1一直扔直到破碎，它用来确定最低摔碎的楼层在什么范畴，
另一个杯子Cup2再此基础上一层层的扔。用来精确确定最低摔碎的楼层是多少。
如果凭空想象，咱们可能会想到二分法，每次隔5个楼层扔，10个楼层扔...
可是咱们马上也应该会想到这么分的不妥之处在于：
确定最低摔碎的楼层所需次数是不均匀分布的。
咱们再来看：每次扔的楼层距离会带来什么影响？
确定最低摔碎的楼层：
总次数 = Cup1扔的次数 + Cup2扔的次数
楼层距离越大，Cup2须要扔的次数越多。
雷同楼层距离下：最低摔碎的楼层越高，Cup1须要扔的次数越多，Cup2须要扔的次数可认为雷同。
咱们的目标其实是须要尽可能保障：不论最低摔碎的楼层是第一层还是第99层，扔的总次数都尽可能统一且缩小。
如果小伙伴有看我上篇文章中LSMT分层步隆过滤器的实现，有没有受到启发？
这里咱们能够使Cup1须要扔的楼层距离递加，这样可改善高楼层所需Cup1/Cup2扔的次数。
假如第一次扔的楼层距离为X，尔后顺次递加1层，直到楼层距离为2.则：
x+(x-1)+(x-2)+...+2 >=100
求解出答案为14。
如果感觉有播种也请帮忙 四连【关注，点赞，再看，转发】 反对一下233酱，谢谢～