7月缺米的来刷题/Mock interview活动

第一次参加这个活动，
863. All Nodes Distance K in Binary Tree， 一开始建了个HashMap来记录每个node的父节点，后来发现其实可以dfs往回传上去target的距离非常巧妙。
227. Basic Calculator II， deque来记录每个num的值，用一个operation的变量来记录当前num该加减乘除的操作，括号可以再recursion进入这个function返回一个括号里计算后的值
572. Subtree of Another Tree， 比较简单，dfs用一个isSame(s.left, t.left) && isSame(s.right, t.right)返回判断是不是一样的tree结构
348. Design Tic-Tac-Toe， 用int[] rows 和 int[] cols就可以记录每行/每列是不是到了N或-N的边界，再加两个对角线的变量，减少了挺多空间复杂度。

打卡第二天
今天复习sql, 发现了个不错的帖子, 里面有database和88个与这个database相关的题目, leetcode刷了三题
https://www.richardtwatson.com/dm6e/Reader/ClassicModels.html
H - Index (I/II)
Arranging Coins                       
Find the smallest missing number

今天做了Best Time to Buy and Sell Stock IV，花了些时间理解状态转移里面k的含义，需要注意的是如果最大允许交易次数k超过n/2，就相当于k为正无穷的情况。
补充：现在做题数量还不是很多，需要花时间学习理解，所以尽量每天1~2题，争取后面每天3道题~

大家加油打卡，有些小伙伴分数没有满100，可能没办法给别人加米。楼主看到了会补上去。其他小伙伴记得给前面的加米~如果发现多次白p的会被取消资格. 希望大家相互监督！

Day 1, 0701, 三道题

946. Validate Stack Sequences
挺好玩一个题，用了两个指针和一个stack，这样i指针遇见就进stack，j指针跟top of stack比较，相同就pop j++，不相同就move i。多过了几次例子就顺了，而且自己有点不敢make assumption怕错，感觉以后要敢，错了比卡着浪费时间好。

809. Expressive Words
自己写了个复杂的，preprocess用List<Pair<Character, Integer>>存了三个信息： 相对位置，char，和count。这样可以每个word对比这个String S跟每一个word，同位置char不一样return false，count<3还不一样return false，否则就继续判断。看答案有直接用指针比较，跟前两个一样或者跟前后一样就过，写的很简单。。。

1110. Delete Nodes And Return Forest

Again，自己写的又特别复杂，每个值都去存好的root的list里一个一个找。看了答案，只用遍历一遍树，把val做成一个set，这样就每个判断是不是，是就处理，不是就过。容易多了。。。思路还是有些窄。而且这个题为了不用处理那么多root，肯定是要postorder来做。我竟然没有想到。。。第一次明白postorder的好处。

今天三题：
263 Ugly Number
74 Search a 2D Matrix
82 Remove Duplicates from Sorted List II

打卡 7.1 Day 1
今天刷完了Queue&Stack 学习卡的最后六题（如图）：
卡住的题主要是 Decode string这题，之前没有做过类似题目没有思路怎么用stack来解题，遇到这种recursion或用stack的题，第一步还是简化问题例如 a2[bc] -> prefix + repeat * [str]， 然后再去考虑怎么用stack 或者pointer去表示prefix,repeat,str。
Flood fill 和number of islands几乎一样
01 matrix 其实是简化版的walls and gates，可以用multiple source BFS
keys and rooms 就是一个directed graph,可以用BFS
另外求米求米

第二天打卡：一共刷了5题
Minimum Distance to Type a Word Using Two Fingers
Minimum Insertion Steps to Make a String Palindrome
Shortest Path in a Grid with Obstacles Elimination
Number of Ships in a Rectangle
Arranging Coins

前面的四题目虽然是hard， 但是都比较简单。其实比较有趣的是Minimum Insertion Steps to Make a String Palindrome. 要求找出插入几个字母可以使现在的string变为palindrome. 比较有趣的地方在于其刚好等于找longest palindrome， 然后，n - longest_seq_len。

Minimum Distance to Type a Word Using Two Fingers这题则需要记住要用memo做优化，不然会超时。

在国服做的三题

刷了四题，其中arranging coins，longest substring为新题：
Arranging coin：此题典型的binary search解，要注意两点：1. int overflow (cpp/Java) 2. 答案take floor of the int
3 Sum：很久没做，忘了hashtable做完了以后要去重，所以要加一个hashset。Two appointer做法更straight forward
Container with most water：two pointer做。start with i = 0，j = n - 1, 注意update的条件是将两个板中较短的那个往前或往后移动。
Longest substring without repeating character： 用sliding window做。不难。