今天我刷题了

1. 二分图
这个题就是bfs。需要注意的是，图不一定是联通的。只要每个连通分量可以二分，整体上就是可以二分的。
loop所有节点，没有访问过的，都可以作为初始节点进行bfs

2. serialize deserialize 二叉树
今天想了个新点子，先把树整到map里面，在dump成json串。
deserialize的时候，把json整成map，再整成树。
一来一回都是递归。



补充内容 (2021-04-29 13:44 +8:00):
今天重刷二分图，竟然忘记visited过的节点不可以再放入queue了。不能再出这种小错误了。别人还以为你不会呢。

1. 判断是不是二叉树
leftChile[], rightChild[]

第一步，建立parent 数组，把各个元素的parent找出来。
如果parent 为-1，则可能是根节点。
如果没有发现根节点，或者根节点多于一个，怎false
如果发现只有一个根节点，则从这个根节点出发，bfs，能够访问所有节点则是二叉树，否则不是。
反例为： 0 -> 1 -> 2 -> 0. 3 -> 4
0, 1, 2 构成了一个环，3和4是树。整体上看，不是树

1. combination sum:
根据模版，套一下就行了
不理解的时候，画一下递归路径图
注意去重的条件

2. 二叉树右试图
简单bfs level遍历。采用牛逼写法，一次pop出整个level的节点

3. random pick with weight
这个题有意思。presum求和，然后从【1, presum[-1]】中选一个随机数，找出来大于这个随机数的最小presum坐标即可。
可以计算下概率，确实就是根weight相关。

1. 朋友request
这个题，需要按年龄把人分组，然后分别计算组内的request，和发到组外的request。
因为年龄是有限多个的，所以会快很多。
注意，<15岁的组，不会发任何request

2. 二叉树垂直遍历
这里，主要要求是，如果列相同，则depth浅的排前边。如果行列都相同，按value排序。
推荐用dfs。遍历的时候，把排序的key社为depth和value，这样后面整理结果就会容易很多。

1. remove invalid parentheses
利用bfs。
先把原字符串入列。对于队列中pop出来的每个字符串，检查是否已经valid，如果valid，则更新最大长度。以后的valid字符串也必须符合这个最大长度。
如果不valid，需要尝试删除每一个（ 或者 ）， 然后进入队列，等待验证。

这个方法能work，根本原因在于bfs可以求最短路径。
下次遇到类似隐藏图的极值问题，可以考虑bfs。包括换外汇问题，求的是最大值，也可以用这个方法做。
还有很多类似的问题。只要可以从一个状态转化为另外的状态，需要求出具体的极小/极大方案，都可以考虑bfs。

昨天今天刷了一道题， trie
trie 跟 memory file system 很像。trie还简单一些
trienode的children都存到一个map里面，这样很方便检索。

search的时候，如果有‘.‘， 只需要使用dfs即可。非常方便。bfs则不适合。


今天复习了trapping water 和merge interval。
没有解决atoi，留给明天

1. 两数和最接近target
跟原始的两数和一样的，左右指针，走法一样。只要记录跟target的最小差值即可

2. 两数差等于target
这个也是双指针，只不过是同向双指针。模版一套，3分钟搞定。
注意，跟target比较的时候，是nums[j] - nums < abs(target), 因为target可能是负数。

3. 今天的难题，max holiday
这个可以dfs，也可以dp。
dp[i][j]: 第j周，在第i个城市，最多的假期天数
dp[i][j] = max(dp[k][j-1]) + days[i][j], k是第j-1周可以到达的城市，并且从k到i有航班 或者 k == i (赖在某个城市不走)。
这道dp的难点在于，如何判断第j-1周，哪些城市是可以到达的。需要维护一个can_fly_to的集合，不断更新可以到达的城市。

还要注意，循环的时候，j （哪周）是最外层循环，不然会出现数据不准确。
还有一个gotya，就是给的days数组，days[i][j]表示第i个city第j周可以休假的天数。所以，总共有len(days[0])周，而不是len(days)周

[/i][/i][/i][/i]

补充内容 (2021-05-02 12:18 +8:00):
4. zuma
这个题要消除相邻的重复字符。用一个stack搞定。
挺有意思的题目

1. serialize/deserialize binary tree
第三次做这个题了。今天学习了递归的方式做这个题，代码比level 遍历要简单很多。
主要是deserialize的时候，需要把左边的token pop出来，这样接下来的递归才能顺利进行。

今天复习了罗马，数字，英文字母的几个题。都是细节题
罗马字母变int，只要左边的字符比右边小，就减去那个字符代表的数字。否则，加上。很简单

int变罗马字母，需要从大到小罗列出所有的edge case， 比如M 1000, CM 900, D 500, CD 400.
然后拿int挨个去除，商就是这个字符出现的次数，余数再继续跟剩下的比较。

int变英文：细节题。四年前考过了，应该不会再考了吧？

今天复习了：
1. 滑动窗口最大值：
简单的一个decreasing monotonic queue。记住，单调栈或者单调队列，当前元素必须入栈/队列，由此才可能引出pop比它小/大的元素的问题。
理解了，就好简单

2. 同向双指针：
最多k个unique元素，不能出现重复数字，等等。。。
这些解法都是一样的，参考同向双指针，需要使用cache的template

3. 满足阈值最小除数
二分法。注意min，max取值

4. order backlog
coinbase的一道题。
本质上就是两个heap，一个最大heap，一个最小heap
因为一个没有对齐的问题，耗费了好久调试时间。用python刷题，这点要注意。