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

打卡第 ③ 天

刷题：3 道

主题：DP + 每日一题

感悟：做过一遍的题现在再做能让代码更精简了。DP能独立完成啦，还做了优化
1. 新建一个List类型的数组： ArrayList<Integer> buckets[] = new ArrayList[n];
2. DP可将自顶向下 优化为 自底向上+回溯
3. decode ways的思路有点像subsets， 但要注意仔细观察规律

连续第 8 天打卡，完成 5 道 Graph 题：(3.5/5)

1. Course Schedule
2. Course Schedule II
3. Number of Islands
4. Minimum Height Trees
4. Is Graph Bipartite?

Tips 总结：
1. Graph 的基本算法有 dfs, dfs_all, bfs, bfs_all；
2. Graph 基本算法的应用有 topological sort, cycle detection, connected components；
3. 首先学会处理 directed graph，然后延伸至 undirected graph；
4. Graph 题还是蛮难的，把 leetcode 结合算法课的题目联系一下吧，你阔以的；

Day 9th
https://leetcode.com/problems/longest-substring-without-repeating-characters/
hash map + two pointers
939. Minimum Area Rectangle
https://leetcode.com/problems/minimum-area-rectangle/
Putting all points to a set, and calculate two points's diagonal to see whether they are in the set.
if yes, calculate it's space.
https://leetcode.com/problems/expression-add-operators/
282. Expression Add Operators
need to reserve the numRes, pre, when it's multiply, numRes = -pre+pre*cur, pre = pre*cur.
time complexity n*4^n

打卡第 ② 天

刷题：4 道

主题：DP, Math

感悟：虽然是想练DP，但今天似乎和数学过不去了。DP虽好，但有时候背后的数学规律才是最简单的办法，不要有了工具就哪里都想用。

Day 9th:
昨天加班，断了一天
269. Alien Dictionary
建立indegree和gragh，有一些细节，indegree所有的char初始为0，graph建立时，如果前一个word更长的话返回false。
结束后需要所有的char的indegree都是0，否则返回false。
670. Maximum Swap
从前往后记位置，从前往后从‘9’开始找比cur大的，然后交换返回。
140. Word Break II
memorize每一次recursion的结果，时间复杂度2^n+n*n+1/2+w
空间复杂度 2^n*n + w
114. Flatten Binary Tree to Linked List
using stack to store the node from right to left.
->next = top().

日期: 7/15/2020
题目: [3]
96. Unique Binary Search Trees
151. Reverse Words in a String
1514. Path with Maximum Probability

压点打卡
LC 图相关题四道：133. 331. 127. 126
主要是BFS和Backtracking用的比较多
再次吐糟C++，最后一道hard居然写了将近五十行，效率太低

连续第 7 天打卡，完成 4 道 DP 题：(1.5/4)
1. Longest Palindromic Substring
2. Unique Binary Search Trees
3. Minimum Cost For Tickets
4. Burst Balloons

Tips 总结：
1. LPS 属于第一类 recursion pattern (single array)，同时用到了二度 dp 的方法进行降速，这个在和 palindrome 相关的问题中十分常见；
2. UBST 也属于第一类 recursion pattern (single array)，我感觉这道题的 recursion 还蛮难 design 的，十分特殊，可记；
3. MCT 披着羊皮的 knapsack 问题，害，本可以写出来的；
4. BB 属于最为少见且最为困难的第四类 recursion pattern (intervals)，其实没有看上去那么难啦；

连续第 7 天打卡，完成 4 道 DP 题：(1.5/4)
1. Longest Palindromic Substring
2. Unique Binary Search Trees
3. Minimum Cost For Tickets
4. Burst Balloons

Tips 总结：
1. LPS 属于第一类 recursion pattern (single array)，同时用到了二度 dp 的方法进行降速，这个在和 palindrome 相关的问题中十分常见；
2. UBST 也属于第一类 recursion pattern (single array)，我感觉这道题的 recursion 还蛮难 design 的，十分特殊，可记；
3. MCT 披着羊皮的 knapsack 问题，害，本可以写出来的；
4. BB 属于最为少见且最为困难的第四类 recursion pattern (intervals)，其实没有看上去那么难啦；

连续第 6 天打卡，完成 5 道 Math, Greedy, DP 题：(4.5/5)
1. Angle Between Hands of a Clock
2. Best Time to Buy and Sell Stock
3. Best Time to Buy and Sell Stock II
4. Best Time to Buy and Sell Stock III
5. Longest Increasing Path in a Matrix

Tips 总结：
1. DP 标准步骤：define size of the problem - define the problem in terms of size - define recursive case - define the base case - choose bottom up (potential for optimized space complexity) or top down (easier to implement, no need to figure out filling order)；
2. 其中，design recursion 有常见的 5 种 patterns：1) given two arrays 2) given one array 3) knapsack (0-1, complete, multiple constraints) 4) intervals 5) matrix movement；
3. 难的 DP 题目要注意二次提速，以避免重复运算；
4. Greedy 怕不就是一种贪婪的思想罢了，目前靠的是一种感觉，下一个要刷的 tag 就是它了；