9月刷题/Mock interview接龙活动（缺米刷题的来）

做了四道题

399. Evaluate Division：非常好的题。建图+BFS或者DFS。可以follow up的点很多，比如说可以考cache
778. Swim in Rising Water： 很好的题。做法有MST，Djikstra和binary search on result
773. Sliding Puzzle：经典的bit mask记录状态+A star或者BFS
1601. Maximum Number of Achievable Transfer Requests： bit mask

9/27 苹果电面题4题

M  436. Finde Right Interval
M  528. Random Pick with Weight
M  398. Random Pick Index
M  300. Longest Increasing Subsequence
M  209. Minimum Subarray Sum

9/27
每天10题完成，晚上准备面试+学安卓开发

做了4道题，第一次在这个贴子下发，求米

Sep 27 打卡，今天主要是array

打卡

1. Reverse linked list
2. Reverse linked list II

复习几道

1. Merge Intervals
2. Meeting room
3. Meeting room II

打卡第三天
第一题（leetcode 793, hard）：注意到n阶乘尾部零的个数是单调递增的，所以可以通过二分找到阶乘尾部含k个零的n的区间，从而得出n的个数。
第二题（leetcode 436, medium）：基本算是个模拟题，维护一个ans[i]，用来表示第一个左端点>=i的区间的下标即可
第三题（leetcode 1488, medium）：贪心，每次抽水都抽当前有水的湖中最早会再次下雨的
第四题（leetode 1282, medium）：模拟题，把groupSize一样的人收集起来，然后把他们按groupSize为一组，一组组分出去
第五题（leetcode 1515, hard）：数值算法，我写了一个梯度下降，但是需要注意数值精度问题，以及如果发现新的解比旧的解更差的时候需要回滚到旧的解并减小learning rate。

刷题第27天
43. Multiply Strings 使用数组和string来实现大数乘法，其中的核心关键是因为是乘法，进位单靠一个变量是不够的，需要用数组来记录多位。

42. Trapping Rain Water 这又是一道hard题，关键思路是确定水位高度，用左右两个指针向中间移动，哪边低哪边移动，且决定水位线这样就不会miss，同时记录累计水量，两边在中间相遇时则停止。

41. First Missing Positive 这是一道hard题，关键是想明白部分排序的算法，通过数组变相对小于n的数字进行hash，放在合适的位置，并且对其他的数字进行标记，即可找出问题数字。