共计 886 个字符，预计需要花费 3 分钟才能阅读完成。
这周 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 酱，谢谢～