在职招新工作刷题贴

221. Maximal Square: 跟朋友互相面试 提醒了一下存现在的size就dp做出来了
642. Design Search Autocomplete System: 细节上纠结太久 半个多小时没写完最后的autocomplete 主要思路就是trie + dfs 每次input新字母的时候到那一层的ACS object 和答案不一样的地方是我每一层都存了hot degree 但其实存在字尾就可以 觉得店面应该不考 电面过来再准备一下
560. Subarray Sum Equals K: 复习 用dict linear过 每次看 diff是不是再dict里 如果是的话说明可以从那里生成n个k
79. Word Search: 复习了一下dfs 我的TLE了因为看四个方向的时候没有及时return
215. Kth Largest Element in an Array: heap或者 quick select -》 这个差不多就是binary search + quicksort 因为每次partition之后 kth的左边肯定小于k 如果目标大于k就没有必要继续sort。 所以根据最后的左边左右的移动
1277. Count Square Submatrices with All Ones: maximal square's solution modified
450. Delete Node in a BST: BST 里 要replace一个数的话可以 1.有right，找successor 然后recursively替换successor直到successor变成leaf 2.有left没right 找到predecessor然后做一样的事 这道题难在用dfs找predecessor和successor
426. Convert Binary Search Tree to Sorted Doubly Linked List: stack + DFS, keep track of head, prev. 每次node就 node.left = prev prev.right = node, prev = node 结尾的时候prev.right = head, head.left = prev

246. Strobogrammatic Number: corner cases
379. Design Phone Directory: dropbox的题目为什么在谷歌的mock里。。这道题为什么是medium set做就行
280. Wiggle Sort: 一开始想的是不行就左右互换 但是想得太多 直接换就行 因为condition的原因。。 有点复杂 我的做法就是sort然后换
324. Wiggle Sort II: 没做 答案的做法是quicksort为基础， 找到median然后小于median的在odd 大于的在even
75. Sort Colors: 比较tricky的two pointer
227. Basic Calculator II: 我寻思这题比 I 还要难 一开始直接从右往左做没想到运算规律 最后用stack做的 先把乘除做完再做加减
224. Basic Calculator: 我iterative的做的 不知道为什么比stack要慢
52. N-Queens II: 基础backtrack dfs 就是存皇后的方法比较奇特 对角线array存的
51. N-Queens: 同上

794. Valid Tic-Tac-Toe State: 横竖斜 从nqueens学到的 hill dale
348. Design Tic-Tac-Toe: 一开始用2d array和两个array代表所有横竖和斜杠 其实用两个array of array和两个size 2 的array就能代表整个board
134. Gas Station: proof of contradiction 用cur tank和total tank就能做 如果剩下的不足以到k那么就和之前的定理相反 其实是到数学题。。。
310. Minimum Height Trees: BFS 一直删leave直到没有edge或者没有leave return最后的leave
明天看 articulation ， bridge，tarjan graph有关的题 然后就开始复习之前做过的题

622. Design Circular Queue: size, item count, queue, head, tail.
917. Reverse Only Letters: skip all non chars while reversing
1055. Shortest Way to Form String: 用一个next array来存储source存不存在target下一个字母 存在的话在哪 然后greedy做法（每次尽力加最多的字母进去）
1056. Confusing Number

1192. Critical Connections in a Network: https://www.youtube.com/watch?v=aZXi1unBdJA helped a lot.
做法是 用 id 和 low map来保存每个node的id和能到达的最小的值。如果id《能到达的最小的值（id《low）那说明就是bridge 因为这表明了后面一部分图无法返回到之前的图的部分里 所以说low的assignment是最重要的：if visited: low=min(low[at],id[to)（如果遍历过了，就有可能是小的那个）else: dfs; low = min(low[at],low[to])这样就先设了下面的数的low，然后对比

297. Serialize and Deserialize Binary Tree: BFS
489. Robot Room Cleaner: 这道题想多了 直接backtracking开始就行。。
494. Target Sum: 用一个array保持上一层的 sum 然后每次加减
1239. Maximum Length of a Concatenated String with Unique Characters: 我用的set 做dfs set可以在On的情况下保证没有duplicate
935. Knight Dialer: recursion with memorization -》 dp
979. Distribute Coins in Binary Tree: 这道题主要在于理解题意。。

复习(https://leetcode.com/discuss/int ... view-questions-sde1)
1. Two Sum
20. Valid Parentheses: 题意 stack
8. String to Integer (atoi): edge cases
36. Valid Sudoku
39. Combination Sum: backtracking
1343. Maximum Product of Splitted Binary Tree: iterate once, get total, then for everynode. calculate max(max,right*(total-right),left*(total-left))
361. Bomb Enemy: dp

247. Strobogrammatic Number II: recursion, add to middle, or add to side
248. Strobogrammatic Number III: same idea, count the numbers
1088. Confusing Number II: confusing - strobogrammatic
1007: Rotation_A Rotation_B

15. 3Sum: sort + two pointer
230. Kth Smallest Element in a BST: pre-order + count
1. Two Sum: dictionary
16. 3Sum Closest: sort, same as 3sum, use diff
259. 3Sum Smaller: two pointer

399. Evaluate Division: parents[x] = [node, r*y/x]