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

day 16 # sql 3题
1. 注意连接条件
2. 注意order by
3. lag() over (...)

day 28

lc new 6, review 10+
1091. Shortest Path in Binary Matrix
bfs to find shortest path

1233. Remove Sub-Folders from the Filesystem
sort and add first, move pointer until the file does not starts with first

609. Find Duplicate File in System
map content to pathes

676. Implement Magic Dictionary
build Trie, use a flag used to mark if we have changed one char

773. Sliding Puzzle
convert to string and apply bfs


Minimum Number of K Consecutive Bit Flips   0 minutes ago
AcceptedjavaMinimum Number of K Consecutive Bit Flips   2 minutes ago
AcceptedjavaOdd Even Linked List   12 minutes ago
AcceptedjavaOdd Even Linked List   12 minutes ago
AcceptedjavaValid Palindrome III   13 minutes ago
AcceptedjavaValid Palindrome III   26 minutes ago
Compile ErrorjavaValid Palindrome III   26 minutes ago
AcceptedjavaClosest Leaf in a Binary Tree   30 minutes ago
AcceptedjavaClosest Leaf in a Binary Tree   33 minutes ago
AcceptedjavaClosest Leaf in a Binary Tree   1 hour, 1 minute ago
AcceptedjavaLongest Arithmetic Sequence   1 hour, 2 minutes ago
AcceptedjavaLongest Arithmetic Sequence   1 hour, 5 minutes ago
AcceptedjavaLongest Arithmetic Sequence   1 hour, 7 minutes ago
AcceptedjavaLongest Arithmetic Sequence   3 hours, 10 minutes ago
AcceptedjavaLongest Arithmetic Sequence   3 hours, 25 minutes ago
AcceptedjavaLongest Arithmetic Sequence   3 hours, 27 minutes ago
AcceptedjavaLongest Arithmetic Sequence   3 hours, 28 minutes ago
Wrong AnswerjavaLongest Arithmetic Sequence   3 hours, 29 minutes ago
Compile ErrorjavaLongest Arithmetic Sequence   3 hours, 29 minutes ago
AcceptedjavaLongest Arithmetic Sequence   3 hours, 35 minutes ago

6/28
4 questions in total
Lessons:
1. you can create multiple queries inside a subquery when dealing with count distinct related issues
2. Limit 1 is for MySQL, correct grammar in MySQL server: Top 1
3. you can name a variable/column in a query and then use it directly for the next query.

Day 15 06/28：六道题

day 26
继续三道binary search。。

2020年6月28日，第二十六天发帖。今天状态也不是特别好，只刷了5道题。

552. Student Attendance Record II。这个dp虽然自己想出了一个valid的思路，但是败给了求和的modulo。今天才了解到原来求modulo是只能相加不能相减的，但是自己设计的状态转移函数有减法，于是就不知道该怎么办了。
279. Perfect Squares。这个题目是和朋友做mock interview的第一题。我一开始说了一下brute force是什么样的做法，然后提出先找出小于等于n的最大完全平方数m然后f(n) = 1 + f(n - m)，这样做一个贪心，但是被朋友举反例证伪了。然后朋友提示我让我去分析一下brute force的复杂度，我说如果计它为F(n)，那么F(n) = F(n - 1) + F(n - 4) + ... + F(n - m)，但是这会有重复。朋友再次提示说如果先计算比较小的F(x)就不会有重复了，我一想哦对啊，这样DP就呼之欲出了。后来用DP解了。
222. Count Complete Tree Nodes。这个题目是和朋友做mock interview的第二题。我说brute force解法就是直接把tree遍历一遍，O(n)。然后开始琢磨有没有更优的解法。注意到左右两边的path如果一样长为n那么这个tree的节点数就是2^n - 1，不是的话就比较复杂。然后朋友提醒我可以考虑divide and conquer，于是照此思路想了一下：如果左右path不一样长就计算左子树的节点数 + 1 + 右子树的节点数，这样时间复杂度是O(logN * logN)
850. Rectangle Area II。这道题本来是想做segment tree的例题的，但是真的好难懂啊。于是为了节省时间，我把答案抄了一遍来帮助自己理解segment tree。这个题感觉跟218 skyline好像，属于那种上了考场直接懵逼的题目。
5. Longest Palindromic Substring。这个题目是为了巩固刚刚学习的Manacher算法。

总结一下：
0. 今天学习了Manacher算法；
1. 对答案求modulo的题目只能用加法来计算，设计算法时要注意；
2. 对于数组合个数的算法（比如coin change那种题目），用dp数组从小算到大可以做到组合数不重不漏；

action item：
1. 明天复习算法：Dijkstra，Union Find；
2. 明天学习算法：binary index tree；

dp三道题。。

day 9:
系统设计：
twitter

https://leetcode.com/problems/read-n-characters-given-read4
https://leetcode.com/problems/remove-invalid-parentheses
https://leetcode.com/problems/palindrome-permutation
https://leetcode.com/problems/max-consecutive-ones-iii

06/28/2020，Day23
今天刷了6道题。

Day 25, 刷三道题，两道新题：

Reconstruct Itinerary        LC 332
Valid Anagram        LC 242

1. 第K大数，quick select算法，可以只用left判断，返回条件是start > end: return nums[start]

2. 重新安排行程。本质是寻找一个图的欧拉路径。建图、排序、贪心选字典序最小都没有问题，dfs访问图，关键是最后是返回逆序的结果...不是很理解为什么这样做是对的。

3. Valid Anagram。可以用26个字母范围的数组计数器表示，进阶才是用hash。最后还要return len(cnt_s) == 0。