在职招新工作刷题贴

329. Longest Increasing Path in a Matrix: DFS + memo做起来很简单 但是可以用 topological sort+ dp 从leaf开始加层数 （peeling onion）
1042. Flower Planting With No Adjacent: 用adjacency map存节点然后拿最小的candidate（1，2，3，4）就行
346. Moving Average from Data Stream: queue
1128. Number of Equivalent Domino Pairs: one pass可以用dict存 我是用i j两个iterator然后略过已经看到过的node，effectively O（N）
959. Regions Cut By Slashes: 把每个node分成四份 上下左右四个三角然后union find

261. Graph Valid Tree: 遍历每个edge 然后把node union起来 如果两个node的parents是一样的 False 如果edge数量不等于node数量-1，false。 BFS DFS 也可以做这道题
947. Most Stones Removed with Same Row or Column: 我用的Union Find，把每个row和col上的stones union在一起 把graph按adjacency node的方法存起来
162. Find Peak Element: 通过这个数组的特性（increasing or decreasing）做binary search
459. Repeated Substring Pattern: 一开始想的每个比较一下 但是 build string比多一个loop快

228. Summary Ranges
950. Reveal Cards In Increasing Order: 这道题用simulation 很有意思
332. Reconstruct Itinerary: dfs
929. Unique Email Addresses
Fruit into basket: hashmap

1007. Minimum Domino Rotations For Equal Row: 第二遍， 看前两个就行
416. Partition Equal Subset Sum: 用dp，dp的array index代表sum (从零到整个array的sum的一半），从第一个数字开始每次iteration加一个数字 最后看dp的最后一个值是不是true
698. Partition to K Equal Sum Subsets: dfs 来construct sets
78. Subsets: 每次iteration把新的数字加到每个现成的list上然后把新的加到result里
621. Task Scheduler: 用heap来存储tasks 然后用queue存储idle的task
337. House Robber III: 用dfs+memo 每次iteration选 rob或者不rob，然后return max（rob，不rob）
515. Find Largest Value in Each Tree Row: BFS

121. Best Time to Buy and Sell Stock: 有一个minprice maxprice 其中minprice为目前看到的最低值 maxprice为当前price-minprice
122. Best Time to Buy and Sell Stock II: 每次有上升的价格趋势就买卖
714. Best Time to Buy and Sell Stock with Transaction Fee: 记住上一个最低值，关键在于每次更新最低值要 valley-fee这样如果在上升趋势中发现更大的 减去valley时不会多减一次fee

99. Recover Binary Search Tree: 用DFS做 因为dfs的特点，现在的数肯定小于上一个数，所以如果上一个数更大就知道上一个要换 把要换的数存起来然后找到下一个顺序错误的数进行调换
416. Partition Equal Subset Sum: 背包问题 用dp找sum的一半可不可以被subset组成
10. Regular Expression Matching: recursion 每次碰到*就有两种情况 只有不match或者1+字母match 下一次recursion就是text除去第一个和pattern match或者text match pattern除去前两个
44. Wildcard Matching: 和上题差不多的做法但是如果recursion就MLE了，dp的做法感觉和subset sum差不多 看每个subset能不能match现在这个text

295. Find Median from Data Stream: two heap, min max
460. LFU Cache: 用了两个map一个queue 着实有点慢。。
410. Split Array Largest Sum: Binary Search， lo是最小的数 hi是总和 然后每个iteration按mid为上限分array 如果需要的格子多与给的说明这个数太小了 otherwise太大了
198. House Robber: 只有一个variable的dp。。。
grokking - k-way merge

213. House Robber II - 第二遍 当作两个n-1大小的arra做
1153. String Transforms Into Another String: 用map看每次的value是不是都一样 最后比value是不是小于26，如果等于不可能互相变换

208. Implement Trie (Prefix Tree)
1146. Snapshot Array: 当前的数值用dict而不是array表示 省空间
809. Expressive Words: encode的方法是两个 一个是对应位置的字母 array 一个是重复次数 比我一开始想的dict好很多

41. First Missing Positive: 答案的那个做法没看懂 用的dict
659. Split Array into Consecutive Subsequences: 用frequence map和end map来greedy寻找所有可能性
4. Median of Two Sorted Arrays：我寻思 two heap也能做 但是用的two pointer trick是先找出短的那个 如果exceed了短的那个把p1 p2全部放到长的那个区
402. Remove K Digits: recursion 去掉leading zero 找到第一个大于右边的数的数，删除后往下recurse
315. Count of Smaller Numbers After Self: 用了自己想的data structure（num，index，smaller） 然后merge sort的时候顺便改变每个值