以梦为马，重整出发——记录刷题 自我打气贴

最近准备在职跳，决定开贴记录一下每天做的题，以及其他方面的准备工作。之前leetcode也陆陆续续做了一些题，这里准备一边复习旧题，一边刷没做过的高频。路漫漫，各位加油！

翻出打卡贴，一看都是去年11月份的记录了，尴尬。。。中间有继续刷题，年底的时候复习了一些高频题目。12月初也面了狗家，挂之，刷题和系统设计都有待提高。最近又要开始面试了，所以继续刷题打卡，希望一切顺利。

9.18，只做了一题：
805. Split Array With Same Average。是个NP的题目，乐扣上的官方答案读不懂，感觉代码和讲解像是两个思路似的。后来找了别人的帖子来看，基本思路是先缩小范围：B,C中的较短的数组B的长度是1~(N/2-1)，然后剪枝（利用BSum 是整数，判断totalSum * i % N == 0），最后可以dfs或者DP（像背包问题）求各种组合的可能性。

9.17做了两题:
365. Water and Jug Problem ->在理解题意后，等效于实现gcd最大公约数
250. Count Univalue Subtrees -> 左右子树的递归函数注意不要一起写在if里，如果第一项没通过，第二项会被直接省略，会丢解。

linkedin上简历也update完。接下来刷题，准备behavior，System Design.

楼主加油！我最近也在准备，一起努力！

昨天一共做了7道题：
642. Design Search Autocomplete System

利用Trie记录已经出现的词条，27个子TrieNode(a-z+' '), 一个int参数记录的出现频率

157. Read N Characters Given Read4

通过read4函数实现read函数，读入的数据多长我们不知道，但是我们会最多读n个长度并写入buf，如果本身数据length就比n短，则读取length长度。
开个char[4]的空间以便使用read4多次读数据，并记录总数，确保总数小于n。【这个题一开始读题极费力，看了很多解题方法才明白，传入的buff更像描述一样，是个temp buff，我们需要做的是填满它，并返回，里面实际填写的元素个数】

158. Read N Characters Given Read4 II - Call multiple times

同157，但是read会被调用多次，所以上一次已经被写入到read4 buff的没有被读到的内容应该作为下次调用read时的返回，因此在全局范围开个char[4]的空间，以便read4 buff里的内容不会被清除，另设置两个全局参数，一个记录read4 buff里一共读入的char的个数total，一个记录read函数被调用时它在read4 buff里的读取位置index。

50. Pow(x, n)

常规递归解：log(n) log(n)
half = myPow(x, n/2), 如果n是奇数，返回half * half * x, 如果x是偶数,返回half * half.

迭代解:log(n) o(1)
x^n，n用二进制表示，b0 * 2^0 + b1 * 2^1 +...+ bi ^ 2^i, x^n = x^(b0 * 2^0) * x^(b1 * 2^1) *...* x^(bi ^ 2^i), 其中，x^(2^i) = [x^(2^(i-1))]^2. 所以我们可以从右到左遍历二进制n,所有结果应该等于每一个1所在位对应的x^(2^i)的连续相乘，而x^(2^i)可以通过上一位的x^(2^i)乘方求得。第一位就应该是x^(2^0) = x， 如此迭代

另外三道是contest里面的前三题，第三题time limit没过，后来看了别人的做法才过。分析题目很重要。

9.16做了3道题：
contest里的最后一题，superPalindrome. 和下面两道：
378. Kth Smallest Element in a Sorted Matrix -》 heap/二分
285. Inorder Successor in BST -》记录父节点，递归or迭代

终于改完简历了，拖了太久，接下来刷题同步筹备behavior question.

9.19
做了一题 556. Next Greater Element III. 利用了单调性，从右向左遍历，找到单调递减的第一个数，然后替换它和它后面最小的大于它的数，最后reverse这一位右边所有数字

复习了Next Greater Element I 和 II, 也都是利用了stack记录数组里的单调性，只要找到后面更大的元素，前面栈里小的元素即可弹出，压最新的大数进栈。II中，因为是circle，只需要将所有元素压入到stack里两次即可。

9.20
昨天加班做公司的活。。并木有刷题。。周末多刷几道，补起来吧。

9.24
周五继续做公司的活，没能刷题。
周末刷了contest的四道题，外加复习了几道旧题，做的新题有：
745. Prefix and Suffix Search - Trie的变型
692. Top K Frequent Words - PriorityQueue, Nlog(k)

在白板上梳理了几个BQ问题，这周整理成文档。567/859

9.28

咦，好几天都没记录了，距离上次做了：
621. Task Scheduler
- 数学解法：找到最高频的task补全它们之间的N个间隔，然后用其他task填间隔，最后返回剩余间隔数+task.length
- 模拟情景的解法：从高频到低频排序所有task，然后每次按续找N个task或task+间隔并更新数组，counter跟着累加N，数组重新排序再循环这个过程，直到当前最高频的task都被找完
398. Random Pick Index
-reservoir sampling问题。对当前i个元素取随机数，如果是0，则选中当前元素，如果不是，保持之前选中的元素。
855. Exam Room
-PriorityQueue保持到两边最大距离对应的端点值，一开始想用int[]，但发现边界处不好处理，于是参照答案创建了interval类，这样在构造函数里就处理了当前区间中到区间端点距离最大是多少。方便后面定义pq的排序。另外定义了-1和N两个拓展的边界，方便记录只有seat 0 或n-1的时候，怎么写interval。剩下的就是取最大折半再放入pq; 去除包含某个座位的两个interval，merge再放回pq。
819. Most Common Word
-这个之前觉得很简单，但是写的时候发现处理标点的细节还是挺重要的。hashmap + hashset