在职招新工作刷题贴

Leetcode:
95. Unique Binary Search Trees II: 比96简单 左右左右的加subtree就行了 helper(i,j)
96. Unique Binary Search Trees: recursion不够快 每次这种时候可以用dp array然后从0一直build array到最后
224. Basic Calculator: iterative TLE, 用stakc做 速度都是O(n) 不知道为什么iterative会TLE
22. Generate Parentheses: subset的做法 当成BFS做 root是 '(', 每次加一个'(' or ')' 一直加到'('==n 当新的iteration == last iteration 的时候停止；也可以用backtrack做
32. Longest Valid Parentheses: stack 主要是每次stack空了的时候要把当前的index加上去 - 这一点不是很懂
16. 3Sum Closest: 比3sum还要简单点 不用担心duplicate 每次看看跟存的diff小就行了
12. Integer to Roman: iteratively遍历整个string
27. Remove Element: two pointers

55. Jump Game: 先recursion 加memo table 优化成dp 最后根据题目优化成greedy
1306. Jump Game III: 上一题做到dp这一步 每次有新的0就要看array里面有没有能到这个index的
1305. All Elements in Two Binary Search Trees: stack in order traversal
1304. Find N Unique Integers Sum up to Zero: 偶数从1开始加正负 奇数就减一然后加0
54. Spiral Matrix: 用integer来指引方向
268. Missing Number: actual - expected 高斯求和写不出来用的array
59. Spiral Matrix II: 和54一样做法 这次build array
58. Length of Last Word: 每次看到空格就找到下一个字母更新last index 没有的话就return
60. Permutation Sequence: 用数学的做法 + recursion 第一个数字是count // (count-1)! - 1

61. Rotate List: 头尾连接然后算出位置prev next=null and head = cur
63. Unique Paths II: dynamic programming 从final开始填minimal travel distance
62. Unique Paths: 同上
64. Minimum Path Sum: 差不多同上
83. Remove Duplicates from Sorted List: two pointer如果有duplicate第二个pointer就一直iterate到不一样的数
80. Remove Duplicates from Sorted Array II: 我的做法是先把duplicate变成x 然后再iterate一次把array并在一起 这种复杂的two pointer做起来还是有点困难
82. Remove Duplicates from Sorted List II: 用了三个pointer做这道题 保存上一个不同的node 上一个遍历到的node 和当前的node
86. Partition List: 不知道为什么明明是medium做法确这么简单。。两个list加在一起就行
91. Decode Ways: 先用recursion然后用dp做了一遍 这个edge case有点多 但是主要还是从后往前填

92. Reverse Linked List II: 先reverse然后再接起来 edge case是none的list
90. Subsets II: 从empty开始每次网上加一个字母 如果是duplicate就只加上一次的
116. Populating Next Right Pointers in Each Node: bfs的很简单 用next这个property可以做到不用extra space
110. Balanced Binary Tree: 检查左右是否balance 然后再看高度是不是差大于一
117. Populating Next Right Pointers in Each Node II: 从每一层的leftmost开始把child连在一起 主要难点在于找到leftmost
143. Reorder List: 这道题把linkedlist的特点都问到了 two pointer找到中间 然后reverse 然后串在一起
150. Evaluate Reverse Polish Notation: stack

160. Intersection of Two Linked Lists: 遍历到结尾变成另一个的头 等两个pointer一样了就是intersection
137. Single Number II: XOR + AND + NOT 这道题要复习
159. Longest Substring with At Most Two Distinct Characters: 见下 可以用two pointer我用的dict
340. Longest Substring with At Most K Distinct Characters: 用k size的dict 如果满了替换最小的
590. N-ary Tree Postorder Traversal: stack 遍历 记得把没有child的node加回去 然后最后一个开始加node
145. Binary Tree Postorder Traversal: 同上
121. Best Time to Buy and Sell Stock: 这类题老是做不出 要复习
120. Triangle: dp做到 initialize成最后一行的大小然后覆盖就行了 space On
129. Sum Root to Leaf Numbers: backtrack找到所有path然后加起来
156. Binary Tree Upside Down: 我用了一个int来track该往哪里加 0是root然后就在1 2之间变换 加到stack的时候右边如果没有要加个null

165. Compare Version Numbers
昨天就做了一题。。。

981. Time Based Key-Value Store: hashmap 但是没想到可以用binary search增快速度
187. Repeated DNA Sequences: 想到了最粗暴的办法 但是答案里的bit还有特殊的算法都没想出来
186. Reverse Words in a String II: stack. O(n)的做法是reverse array然后把每个字反过来
173. Binary Search Tree Iterator: 用的stack
168. Excel Sheet Column Title: base26 calculation
171. Excel Sheet Column Number: 上一题反过来

1007. Minimum Domino Rotations For Equal Row: 做的时候没意识到只要看开头两个就行
236. Lowest Common Ancestor of a Binary Tree: 左右的看 如果有return 没有往下走
1110. Delete Nodes And Return Forest: 用helper function parameter里面要有parent

108. Convert Sorted Array to Binary Search Tree: recursion
249. Group Shifted Strings: calculate diff between char
1057. Campus Bikes: distance map and iterate over to find the smallest for each distance. Map: distance[ bike(worker sorted by id) ]
1066. Campus Bikes II: Distance map and depth first search, build list

444. Sequence Reconstruction: disjoint set 看每个source是不是只有一个
399. Evaluate Division: disjoint set 用这个方式存储： a（ b， a/b）然后对于query找到parent并且记录一路上总共乘了多少次
684. Redundant Connection: disjoint set 用rank来确保快速的find
200. Number of Islands: disjoint set的做法是每次看到一个1就把上下左右全部记录到set里 然后算总共多少个set
545. Boundary of Binary Tree: 先左右找出来 然后dfs按sequence找到最下面一层
1086. High Five: heapq, nsmallest
937. Reorder Data in Log Files: two pointers