在职招新工作刷题贴

128. Longest Consecutive Sequence: initialize
208. Implement Trie (Prefix Tree): implement trie ( if cur==None, create a new one)
46. Permutations: backtrack
684. Redundant Connection: union find, if two vertices have the same parent, we have cycle

3. Longest Substring Without Repeating Characters: two pointer and hashmap
116. Populating Next Right Pointers in Each Node: bfs -> popleft()!!
310. Minimum Height Trees: topological sort by removing leaves

1110. Delete Nodes And Return Forest: recursion, 分为几个情况 - 有没有parent 在不在to delete 把list改成set速度快了好多
1095. Find in Mountain Array: 找到peak 然后左右各binary search
852. Peak Index in a Mountain Array: 上一题的铺垫题 binary search
1153. String Transforms Into Another String: 一开始没做出来 因为没有把同样的字母加到字典里 最后看 values < 26
911. Online Election: 遍历persons和times然后用array来存储每个时间点应该返回的值 array是初始化成最后一个time+1的大小 用last max和last time 来生成array 不知道为什么这样我的space complexity还是100%。。。
348. Design Tic-Tac-Toe: 看了下自己的答案，没做 - 用hill和dale来存储斜边的数值是最大的takeaway
417. Pacific Atlantic Water Flow: 一开始想用dp做发现要iterate好多次做不出来 就改用bfs 关键在于要开上下左右然后不在result set里的都要重新看一遍
三道Contest

289. Game of Life: if board is infinite: save only live cells. dead to live = 3 live to dead = 2
68. Text Justification: 每句话build string corner case比较多
62. Unique Paths: dp
243. Shortest Word Distance: easy question but idk why i am 12% space when i only used two variables
71. Simplify Path: stack
301. Remove Invalid Parentheses: backtrack
815. Bus Routes: 一开始用dfs做不出 主要是因为图存的方式不对 这个才是难点 这两题都要复习

694. Number of Distinct Islands: hash relative location
305. Number of Islands II: union find
289. Game of Life: 其他数字更新board
543. Diameter of Binary Tree: height, modified
767. Reorganize String: heap, push two at a time
300. Longest Increasing Subsequence: dp, store the longest increasing sequence of every number in the array

21. Merge Two Sorted Lists: iteration, two pointers
23. Merge k Sorted Lists: 用heap k size 或者 不停的merge 2 list直到只有一个list
109. Convert Sorted List to Binary Search Tree: recursion， fast slow pointer 注意用prev track mid前一个node 然后prev next 设为None。 用array可以速度更快 最后的inorder simulation 感觉像是recursion变个样子
207. Course Schedule: topological sort
127. Word Ladder: intermediate word map, BFS. bidirectional bfs就是头尾一起bfs直到找到end 没写
295. Find Median from Data Stream: two heap 或者用一个 sorted list 然后用insertion sort+binary search
K Pairs with Largest Sums (Hard) : 主要在于怎么优化 优化的方法就和merge k sorted list差不多
310. Minimum Height Trees: topological sort remove leaves

Kth Smallest Number (hard): 用quick sort partition 随机找一个pivot 小的左边大的右边 然后根据左边数的数量来继续recurse直到小的数量 = k-1 可以iterative 也可以recursive
895. Maximum Frequency Stack: 自己的做法是用一个 freqToNum 和一个 numToFreq两个字典来存储答案 跟lc答案差不多   grokking 的做法是用自己的数据结构然后用frequency number+max heap来控制哪个先来
358. Rearrange String k Distance Apart 1.: 自己想出来的是heap + queue 2. 看答案做的greedy 但是还是用了max heap来track最多的那个字母 主要是怎么确定是否可以populate string

找到工作还是不能懈怠
重新开始刷 一周三题起步
654. Maximum Binary Tree