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

Day 26, 刷三道题。

1. 臭名昭著的天际线问题。扫描线算法。其实没怎么看懂。大概就是遇到左端点入堆，右端点出堆，如果目前维护的最大高度和上一个转折点不同，那么就迎来了新一个转折点。偏偏python3没有红黑树这种删除节点很方便的库，trick的做法又看不懂，于是草草copy/paste了事。

2. Unique Path。DP + 滚动数组优化空间。

3. 两个栈实现队列。出队的时候倒一下，剩栈底元素，出队，再倒回来就行啦。

哎...令人心碎的天际线问题。

打卡第29天

6.29 连续第九天 打卡三题

Monotonic Array，one-pass，可以乘正负号来表示上升或下降序列
Stone Game II，DP，需要注意到找自己最好的策略是使得对手最好的策略最坏
Unique Paths，DP题，状态转移方程比较直观

第七天，三道题
course schedule
clone graph
reshape the matrix

菜鸡第三十天！

今天又是不会做题的一天
1. flatten binary tree to linked list: 用的recursion，用一个pre来记被展开的开头，先把right subtree展开，再把left subtree展开
    每次update pre，把展开的pre加到node.right里面，同时把node.left设成null，最后pre=null
2. daily temperature: 从右向左看，如果T[i] < T[i+1], res[i] = 1, 不然的话就说明明天比今天冷，这个时候从k=i+1开始看，找到下一个
    比今天气温高的日期，每次k+= res[k]快一点，找到就是k-i，如果中间有res[k] = 0, 就说明没有比今天气温高的日期了，对应的是0
3. next greater element: 可以用一个stack和map，每次遇到num就pop stack直到element不再小于num，再把num push进去，这样
    stack就会从上到下递增，可以把stack.pop()和num存map里面，最后从map里找对应的next great element，没有就是-1
4. kth smallest element in BST: 用一个stack做dfs，每次把current node push到stack里，cur = cur.left, 知道cur是null，就pop一个
    cur = cur.right, 每次pop之后检查是不是k，然后减一
5. remove element: in place remove, 可以用一个ind记非target的index，在每个element如果nums[i] != target, nums[ind] = nums[i],
    再把ind加一，最后return index，就是非target的个数

今天刷了六道题 三题是hard的 明天继续加油 :)

#第20次打卡 今天刷了五道题，前面的四道都是easy或者medium，很快就写完了，时间主要都花在了最后一道hard上面，但是在这道题上思考新的方法不断改进时空复杂度的过程让我十分享受。最后看到discussion里面的O(n)时间，O(1)空间的解法时真的有一种欣赏艺术品的舒适感。

6.29 今天刷了6道sql、3道algorithm

打卡第20天。249. Group Shifted Strings; 299. Bulls and Cows; 1048. Longest String Chain。截图放在截图

Jun 29 打卡第29天，6道题
1140. Stone Game II, 博弈minimax题目，下一个人保证他的结果是最小的，自己的结果max；而且利用hash记录中间结果，和startIndex，M有关；
486. Predict the Winner, Minimax, recursive function is slow… 可以使用DP，dp[i][j] 表示从i-j fst player可以比snd player多得的分数，dp[i][j] = Math.max(nums[i] - dp[i+1][j], nums[j] - dp[i][j-1]); 最后看dp[0][n-1]>=0?
877. Stone Game, 和486一样，dp space可以优化成O(n); 但是降维不太清晰…
952. Largest Component Size by Common Factor, UnionFind将factor一起union，最后map查找最大值，巧妙！