美团2020算法题——黑客入侵点定位

题目描述如下：

集团内部有一核心机密项目，共由150个代码模块按顺序串行执行组成（示例：模块1->模块2->…模块N…->模块149->模块150)。偶然一天，某一个模块突然被黑客入侵（当前模块也称入侵点）。因为内部已经有预防措施，现存两款从不同角度设计的反入侵检测程序，但同时也有一定检测限制：
1.输入：顺序代码段，必须以模块1开始（比如：模块1->模块2->…模块39）
2:输出：True-输入包含入侵点，False-输入不包含入侵点
3.每款检测程序可以运行多次：可多次返回False,但仅能返回一次True（由于入侵的对抗性存在，一旦输出True即报废，后续检测功能失效）
4.同一时刻只能有一款检测程序运行，每检测一次耗时10分钟
现在希望仅利用现有的两款反入侵检测程序，在最短的时间内确保可以快速定位入侵点。具体需要如何设计检测流程，时间是多久。

思路

前期思路

这道题其实与另外一道经典题目“楼层扔鸡蛋”的本质是一样的，我自己在大二参加蓝桥杯的时候遇到过这道题，当时不会做，跟这道题一样，第一反应就是二分法，但其实这里面有个问题，二分法对于尝试的次数是没有限制的，而这两道题不一样，一旦失败一次，剩下那次唯一的机会就得从头一个一个枚举，所以二分法在这里是行不通的。

介绍一个数据结构——块状链表。我们都知道，数组的优点在于可以使用索引随机访问，而链表的优点在于O（1）复杂度的插入删除，块状链表就是将这两个数据结构结合了起来。比如有n个元素，将其分为√n份，每份就有√n个元素，这样我们在查找某一个元素时就可以在√n的时间内定位到某一块，并且在块内寻找的时候复杂度也是√n，总共的复杂度就是2√n。

受此次发，我们可以将楼层分为√n份，这样只需在O（2√n）的时间内就可以找到答案。例如有25层楼，分成5楼一份，最坏的情况是再最高一层楼，也就是第5份里面的第5小份，总次数就等于5+4=9次，也就是2√n-1次。

但仔细想想，这是最优的答案了吗？按照前面分析的，这个方法最坏尝试9次，那么我们第一次不在第5层扔，而是在第9层扔，这样并不会破坏最坏结果，假设扔完之后鸡蛋没碎，那么剩下16层，再在16层楼中按照此方法尝试，很明显是不需要8次的。（或根据归纳法也可知道25层的答案不是9）

归纳法

先讲一种通用的方法：归纳法。从一层楼开始，需要尝试的次数是1次；如果是两层楼，那么需要尝试2次，三层楼同样需要尝试两次；如果是四、五、六层楼，则需尝试3次；如果是七、八、九、十层楼，则尝试四次。。。我们可以发现规律：一个1，两个2，三个3，四个4。。。我们可以按照规律列举出每一层需要的次数直到求解的那一层。

归纳法对于这道题是有用的，但是对于这道题的推广问题：m层楼n个鸡蛋的情况就无能为力，所以我们还要学习动态规划法。

动态规划

令f [i][j] 为 i 层楼 j 个鸡蛋时的最少尝试次数，那么规划方程为
f [i][j] = min(max( f [i-1][j-1], f [m-i][j] ) + 1)
f [i-1][j-1] 表示在第i层鸡蛋摔碎了，那么就要从这一层下面的那些楼层去试，所以楼层减一鸡蛋数减一。也有可能鸡蛋没碎，由 f [m-i][j] 表示。这两种情况要考虑最差的情况，所以取max，再加上这一次的1。遍历所有层数取最小值。这种解法的时间复杂度为O（n^2*m）。

可以看到这种动态规划的时间复杂度非常高，其实还有更快的解法，我们需要结合归纳法的思路，反过来看i个鸡蛋扔j次最多可以测出多少层，然后与题目要求的楼层数进行比较。令f [i][j] 代表一共i个鸡蛋，扔j次最多可以测出来的楼层的高度。方程为
f [i][j] = f [i-1][j-1] + 1 + f [i][j-1]
f [i-1][j-1] 表示鸡蛋破了，f [i][j-1] 表示鸡蛋没破。找到最小的f [i][j] 使得j >= n，时间复杂度为O（m*Answer）。

最后

以上就是如意未来为你收集整理的算法题——黑客入侵点定位美团2020算法题——黑客入侵点定位题目描述如下：思路的全部内容，希望文章能够帮你解决算法题——黑客入侵点定位美团2020算法题——黑客入侵点定位题目描述如下：思路所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。