开篇记录面试第27天—贪心算法

21号下午去面的快看漫画，前面聊的都挺好，问什么项目啊，机器学习基础答的还算满意，面试官说那做个题吧，就一路跪了。一共三道题，我大概描述一下。

问题

1. 给定一组时间序列，格式是(m,n),记录的会议开始时间和结束时间，求要多少个会议室才能把所有会议都安排下。
2. 给定一个乱序数组，找出任意一个波峰，波峰的定义是大于与它相邻的两个值，对于边界值，只要大于相邻的那个即可，要求是时间复杂度尽可能低。
3. 一个房间里有100盏灯，每个灯有一个开关，现在有100个人，依次进入房间，每个人操作一次自己编号以及自己编号整数倍的灯，求最后所有人操作完还有哪些灯是亮着的。

思路

1. 第一题其实我当时已近描述的差不多了，只不过当时写代码可能有点吃力。这个没找到原题，一般都是给定了会议室数目，求能开几个会。在这篇知乎里https://zhuanlan.zhihu.com/p/21510179看到了一些说明，如果我们两两比较，看后开始的会议是否位于先开始的会议之间，算法复杂度。如果对会议室进行排序然后再插入，复杂度可以降低到。最快的应该是利用bitmap，把所有时间都标记在bitmap中，扫描一遍即可。不是很能理解，看了那些给定会议室数目的题目后，感觉我自己的思路好像也没什么问题，所以也记录一下吧。解题的过程是先按照起始时间排序，如果起始时间相同，就按结束时间排序，排好以后，从第一个开始，去找结束时间大于等于当前结束时间里最小的一个，然后合并，直到剩余的里面没有能合并的，再从开始时间第二个的开始，继续合并，最后剩下几个数组，就是需要几个会议室。
2. 当时我想不到别的办法，想说要不写个二分吧，但是我解释不出来为什么可以二分，面试官很不满意。从一篇博客里找到了这样的描述，"给定一个很长的数组 arr，已知数组的长度 length 且 length >= 3，已知数组的第一个元素不比第二个元素大，最后一个元素不比倒数第二个元素大。"我觉得应该是要加上这个条件的。那这样就跟我想的一样了，其实就是利用条件arr[mid]<arr[mid-1],且arr[mid]>arr[mid+1],认为这个已经凑成波峰的一半，arr[mid-1]有可能就是一个波峰，且新出现的数组arr[0:mid + 1]且满足最后一个元素不大于倒数第二个元素，所以从[0,mid]继续二分。感觉这个题还是有点扯，再悟一悟吧。
3. https://blog.csdn.net/shangzhihaohao/article/details/45011245
   这个博客里有详细的说明。总结一下就是所有的灯只有因子个数为奇数个时，灯是亮的，而奇数个的只有存在相等因子的才会出现，比如4=2*2，所以4的因子是1，2，4，所以最后是亮着的。答案就是100以内的所有平方数。我当时已经写到成对出现的问题了，没推出最后的结果有点遗憾。