1月刷题打卡帖

1.14
Find Duplicate Subtrees，后序遍历serialize subtree as string，用hashmap检查重复
Convert BST to Greater Tree，BST转累加树，用global sum
Construct Binary Tree from Preorder and Inorder Traversal，因为是二叉树，没说二叉搜索树，所以需要用两个遍历序列构造，方法都是画图确定build递归时的索引范围，可以用map优化
Construct Binary Tree from Inorder and Postorder Traversal
Construct Binary Tree from Preorder and Postorder Traversal

1.15
Serialize and Deserialize Binary Tree，因为是binary tree，所以为了反序列化，要在序列化时append null，前序/后序/层次遍历都可以，但是中序不行
Serialize and Deserialize N-ary Tree，因为是N-ary tree，不能像binary tree那样最多append 2个null，所以最好是append val，再append size，注意都要加上分隔符，这样每个节点有几个孩子就知道了
Serialize and Deserialize BST，关键是怎么利用BST的性质来避免序列化时存null，一般来说常用BST中序遍历是升序的，但是这里用先序遍历，deserialize时发现一个节点的val不再维护的min, max范围，就知道这个节点不属于这棵子树
Minimum Path Sum，可以用dp做是因为只能向下走向右走，dp subproblems不会形成环，所以可行，而四个方向都可走的shortest path问题要用Dijkstra
Cherry Pickup，贪心走两遍dp是错的，关键是转换思路，变成两个独立的人从终点走到起点，所以是3维状态的dp

1.15

Task Scheduler
LRU Cache
Minimum window substring
Longest string without repeating char
Longest string with at most 2 diff char
Longest string with at most k diff char

1.16
Unique BST，用dp
Unique BST II
Construct BST from Preorder Traversal
Search/Insert/Delete in a BST

1.16

Regular Expression Match
Letter combination of phone number
Sliding Window Maximum

1.17
Intersection of Two Linked Lists，双指针，一个走到头就重置回另一个list的开头，巧妙地counteract diff length of two lists，然后齐头并进直到meet
Lowest Common Ancestor of BST
Lowest Common Ancestor of Binary Tree，因为从底向上找LCA，所以都是postorder traversal，先把框架写出来，不管找几个节点的LCA，都是遇到要找的就返回它，null返回null，如果左右都有说明LCA是root，否则是其中一边返回的那个，如果说要找的节点可能不在tree上，那就不能遇到要找的就返回，而要全遍历到
Lowest Common Ancestor of Binary Tree II, III, IV

1.17
Plus One   
Reverse Linked List   
Reverse Linked List II  
Generate Parentheses

1.18
Valid Parentheses
Remove Invalid Parentheses，删除最少的括号使字符串合法，并返回所有合法字符串，dfs backtrack(s, 0, 0, {'(', ')'}, res)，从last_i开始看，前面已经合法了，如果要删从last_j开始找，注意consecutive/non-consecutive rule[1]删除的情况
Minimum Remove to Make Valid Parentheses，不需要找所有的，所以不用backtrack，只需要从左到右，再从右到左扫描两遍，count<0时不append就行
Longest Valid Parentheses，和前面的区别是longest必须是consecutive的括号，所以相当于longest substring，所以可以用dp，也可以用stack，只不过需要stack.push(-1)，当合法的pair出现时就pop，看stack.peek()不合法的index到当前index的差值，更新max。另一种最简单的做法是先从左到右扫描，如果左括号小于右括号，就重置left, right计数器，再从右到左扫描，如果右括号小于左括号，重置left, right计数器
Minimum Add to Make Parentheses Valid，一个左括号配一个右括号，就是简单地扫描看需要几个右括号，count<0时就代表需要一个左括号去匹配res++，最后别忘了加上count
Minimum Insertions to Balance a Parentheses String，一个左括号配两个右括号，比较tricky的是当遇到左括号时如果需要的右括号数为奇数，需要加一个需求量，再res+=1给一个右括号
Generate Parentheses, backtrack

1.18
322        Coin Change    
42         Trapping Rain Water
91        Decode ways

1.19
Minimum Depth of Binary Tree，BFS
Open the Lock，关键是转化为图BFS求最短路径，从起点"0000"到终点target，每一步相当于在四个位置中只能上拨或下拨，所以一个vertex相当于有8个neighbors，然后一层一层找
Sudoku Solver，回溯就是在穷举，所以先写出backtrack框架，然后再填细节，一行搜完了到下一行
Valid Sudoku，比较tricky的是检查3x3方格，row=i/3*3+j/3, col=i%3*3+j%3，col相当于3,4,5要分别对应到0,3,6，所以i%3*3
Valid Anagram，用in[26]当做map，可以一遍同时扫描s和t