刷题打卡贴，监督自己

第一天：
打卡一道DP，三道树的题目
1130. Minimum Cost Tree From Leaf Values：
这道题用一般思路就是DP或者recursion with memo，典型的区间dp的思路就是dp[left][right]表示在区间[left, right]（可以是inclusive或exclusive看题目本身）的目标值，然后最终返回dp[0][n-1]就可以。
中间部分用bottom up思路，最外层循环固定一个d，表示区间长度，然后left从0到n-d，然后right就是left + d。转移函数就是在left到right之间选一个k值，一般就是dp[left][right] 化解成 dp[left][k]和dp[k+1][right]两个子问题。

437. Path Sum III
一般的树的recursion训练，这道题的特征是recursion可以跳过root，所以这里需要一个helper，本质就是保证当前recursion是从root开始的，那么原函数可以化解为 pathSum(root.left), pathSum(root.right), pathSumFromRoot(root)三个子问题。

111. Minimum Depth of Binary Tree
这道题可以用postorder traversal的方法求解min depth，但是更优解应该是一个BFS，因为不需要遍历整个数求解，而是从root开始往下，每一层扫一遍，找到的第一个是leaf的node对应的depth就是min depth

404. Sum of Left Leaves
一个比较常规的recursion，注意条件是只看左叶，包括右边子树里的左叶。

打卡十八天：
接着昨天的stack题的变形，circular list的做法就是遍历两遍。

1. # 如果是circular list就连续遍历两遍，用一个stack。TC: O(N) SC: O(N)
   
2. class Solution:
   
3.     def nextGreaterElements(self, nums: List[int]) -> List[int]:
   
4.         n = len(nums)
   
5.         greater_list = [-1] * n
   
6.         stack = []
   
7.         for i in range(2 * n):
   
8.             while stack and nums[stack[-1]] < nums[i % n]:
   
9.                 greater_list[stack.pop()] = nums[i % n]
   
10.             stack.append(i % n)
    
11.         return greater_list

复制代码

打卡第十六天:
一道DP：把问题转成一个dp(i, j)：对substring s[i : j+1]，需要删除的字符串的最少次数。然后dp(0, len(s) - 1) 如果小于k就是满足的
785. Is Graph Bipartite? 这题确实没想到也是个dfs，具体思路是，从第一个node出发，如果这个node没有被涂色过，就把它涂为红色(0)，并且检查每个邻居，如果涂了色，是不是跟红色相反的颜色(1)，否则返回False，如果没有涂色，涂为相反的颜色(1)然后对新涂色的邻居做同样的dfs。
1102. Path With Maximum Minimum Value：union find的思路，其实也算是一种kraskal的思想：将每个node按从大到小的顺序排列，每一次选当前没选过的最大的node，然后如果其周围有已被选中的node，就union一下，直到(0, 0) 和 (m-1, n-1)相连，刚相连的时候选中的node，它对应的值就是所联通路径的score
1631. Path With Minimum Effort：和1102很像，不过目前只用priority queue的做法解了一下。感觉应该也是可以用kraskal的思想写出来的

刷了四题：
两道array的题，trapping raining water是很经典的一道array的题，用brutal force开始入手，慢慢优化的过程很重要，中心思想是对每一个height[i], 找到其左边的最高的高度和右边最高的高度，两者之间较小的那个可以作为水平面高度L，对于height[i]，其能储存的水就是水平面高度L - height[i], 这里可以看到如果height[i]本身很高，那也储存不了水的。
一道warm temperature的题，也算是array，用stack解，比较容易想到。
另一道graph的题，用了BFS解，感觉还是算容易想到，不过要注意在enqueue的时候想一想这个element是不是应该是一个tuple，存当前person以及当前告知的时间。

补充内容 (2020-11-27 16:50):
十九天

第二天
一道区间DP，一道树的题。

第三天，
做了一道DP的题，用了两种解法
一是可以用BFS来搜索，这一种我觉得是最好理解，也是最make sense的。

还有一种是可以用状态压缩dp来做，将状态转换成int32来表示，从而将一个spelling的问题转化成了bottom up dp.

详细总结：
https://stevensyt.github.io/leet ... ckers-to-spell-word

第四天：
1125. Smallest Sufficient Team
打卡一道DP hard，跟昨天很像也是状态压缩，用bitmask可以解决，也可以用BFS解决。
详细总结：
https://stevensyt.github.io/leet ... est-sufficient-team

昨天太晚了没有写帖子，补一下昨天和今天的。
两道DP hard，都是状态压缩问题，真的做吐了。。。
详细解答：
https://stevensyt.github.io/leet ... hortest-superstring
https://stevensyt.github.io/leet ... tudents-taking-exam

还可以这样督促自己，学习了！楼主赞

第七天：
补昨天刷的一道dp 状态压缩的题：
太难了睡觉前没做出来。
https://github.com/StevenSYT/lee ... parallel-courses-ii
1494. Parallel Courses II
今早优化了才过。应该也能用BFS写，准备下次复习的时候用BFS也写一遍。

睡不着的喵 发表于 2020-11-14 09:52
还可以这样督促自己，学习了！楼主赞

共勉！ 为了刷题督促自己。

第八天：
又一道状态压缩dp，这周被状态压缩整自闭了，全是hard题。
https://stevensyt.github.io/leet ... -hats-to-each-other

第八天：
再补两道 leetcode Nov Challenge的题