缺大米的请参加这个刷题/Mock interview活动

中间间断了两天lc 花时间看了看跟design相关的 今天继续
算是第11次大卡了吧

• Path With Maximum Minimum Value - 这道题是看了答案的 然后找了个视频系统学习了一下 感觉讲的挺明白的： https://youtu.be/pSqmAO-m7Lk 自我感觉理解到位了 实质就是找到最大路径 然后记住最小值 返回就行了 可能最简单的解法就是背下来Dijkstra 然后套模版吧 模版背好了这样的题是不是就变成送分题了 当然没记住就杯具了
• Unique Paths II - 这道题和minimum path sum都是DP 对于我来说先递归 brute force写出来 然后top down加mem优化比较简单 但是现在这个行情 不知道top down这种需要maintain stack的解法是不是都不受待见了
• Minimum Path Sum
  

好贴，明天也刷题

打卡第十天，做了三道题

• Allocate Mailboxes 动态规划+ top down 记忆化递归， 例外要存一个min cost 矩阵cost[i][j] is min cost of having one mailbox in the median of array[i:j]
• Number of Submatrices That Sum to Target 前缀和数组在vertical列得方向上，在Subarray Sum Equals K的问题上多加一个维度
• Search in a Binary Search Tree 递归查找，注意终止条件
  

06/16/2020, Day13
今天刷了3道题。

刚刷了三题，求大米！

2020年6月15日，第十四天发帖，今天刷了6道题，并且面了一轮谷歌电面：

周四要电面许愿家，以下题目全部是他们的近期面经：

528. Random Pick with Weight。原题是比较经典的presum + binary search。地里有个面经的变形是要能够update weight，自己想的办法是把weight改变之后的presum全部重新计算一遍。
252. Meeting Rooms。这算是interval系列中最简单的一道题了。直接排序之后记录当前会议结束的时间，如果下一个会议开始于其之前就不行。
125. Valid Palindrome。双指针扫描字符串就可以了。
680. Valid Palindrome II。同样可以双指针扫描字符串，不过需要一个helper function来记录那一个字符的差异是不是用掉了。
200. Number of Islands。这道题在各大公司都算是高频了。之前用BFS和DFS都做过了，于是这次用了封装的Union Find来做。还是因为一个typo的问题，debug了好久。
210. Course Schedule II。这个题目是典型的拓扑排序。用BFS从入度为0的点切入，去掉点之后更新与之相邻的点的入度。如不能遍历完全图，说明图中存在”首尾相接“的环，所以不能完成。随后用map记录了修完一门课程之后可以解锁的课程，将时间复杂度从O(VE) 更新到了O(V^2 + E)。

总结一下：

1. Union find 所需全局变量较多的时候可以封装起来，还可以完成计数的功能。
2. 基于拓扑排序的BFS可以查找有向图中的”首尾相接“的环，DFS可以用来判断一个图是否为一棵树（既可以找出首尾相接环，也可以找出多组边组合成的封闭的”环“）。

20200616:
3: 0468, 0491, 0533
4: 0505, 1477
5: 0499
6: 0488

20200615:
3:  1091
4:  0355, 0410, 0428
5:

6.16 第16天3题
1172 //1.openstack永远存半满的坐标 2更新openstack的情况 push(如果first满了poll,这种情况只有push时候会出现一次) pop(每次pop的时候检查last是不是空如果空，要poplast变更且检查之前一个是不是空因为可能先pop完之前的stack)
2.更新stack 1 push(如果openstack为空说明全是满的或没有stack) 2.pop(每次更新openstack时说明最右边为空stack同时减少)
316. 1.最左边的字母一定是最小的，后面包含每一种字母 2. 只有新字母比栈顶小才有机会更新，因为如果大的话保留栈顶总会比较小（贪心选择，当遇到更新是永远保留后面的元素） 。seen中的元素不用看， 情况1来了a， a--b--a b比a大，不更新。b比a小，如果A不更新第一个B说明BA之间一定有比A大但后面没有copy的字母

打卡第三天刷了3个简单题
（版主第一天没加米，在1053楼，第二天也没加，在1111楼，谢谢）

Day 15打卡：3题