1/24~3/24 60天刷题全力冲冲冲

512. Decode Ways
dp 解，dp[i] = dp[i - 2] + dp[i - 1]，两种情况相加：当前看成是两个数字（10，20看成一个数字），或看成一个数字（不算 0）

657. Insert Delete GetRandom O(1)
复习，删除的时候将最后一个元素将要删除的元素覆盖，再 pop，同时更新 positions

954. Insert Delete GetRandom O(1) - Duplicates allowed
复习，和上一题不一样的是，self.positions = { val: set() }，删除的时候直接 self.nums[index] = None

1534. Convert Binary Search Tree to Sorted Doubly Linked List
复习，将 left 看成 prev，将 right 看成 next。做 inorder，最后返回 first

651. Binary Tree Vertical Order Traversal
复习，BFS，node -> index，node.left -> index - 1，node.right -> index + 1

69. Binary Tree Level Order Traversal
Easy BFS

363. Trapping Rain Water
复习，左右双指针

383. Container With Most Water
左右指针向中间靠，遍历所有情况即可，min(heights[left], heights[right]) * (right - left)

1310. Product of Array Except Self
对于 products[i] = 前 i - 1 相乘 * 后 i + 1 相乘，所以累乘起来就可以了

453. Flatten Binary Tree to Linked List
复习，注意最后要 return root

601. Flatten 2D Vector
next() 的时候，如果 self.next_elem 是空，就先 has_next 一下。has_next 里先找到目标位置，再去判断目标位置是否合法，最后赋值返回 True/False

528. Flatten Nested List Iterator
这里本来是可以用 queue 的，但是如果 item 是 list 那么不能在 queue 前面追加，所以要用反向 stack 来做

242. Convert Binary Tree to Linked Lists by Depth
简单的 BFS

106. Convert Sorted List to Binary Search Tree
找中点，递归 dfs(head) 和 dfs(middle.next)，注意要将 slow.next = None

今天主要是复习以前的题+follow up 和 related questions，相对简单

vmware是做后台的嘛？

# 2020/1/30

547. Intersection of Two Arrays
三种方法：binary search, hash set, sort + 遍历

548. Intersection of Two Arrays II
hash map 去计数，遍历另一个 array 就可以了

248. Count of Smaller Number
遍历 + binary search

6. Merge Two Sorted Arrays
两种方法：1. 一直排出 2. 一个循环来选中

64. Merge Sorted Array
将 B merge 到 A，从 A 的后面插入

165. Merge Two Sorted Lists
复习，超简单

104. Merge K Sorted Lists
三种方法：
1) Heap
2) 归并算法思想：merge by range -> merge
3) 相邻归并思想：merge by adjacent -> merge

839. Merge Two Sorted Interval Lists
用 push_back 去替换 append。其中，push_back 判断 results 是否为空，last.end < interval.start ?

981. Time Based Key-Value Store
key 对应两个数组 values 和 times，在 times 里二查找到 index，返回 values[index]

# 2020/1/31

1745. Monotonic Array
定义 inc 和 dec，如果遇到反例就变成 False，每次判断 inc 和 dec 是否都是 False，如果都是 False 就是有增有减，return False

838. Subarray Sum Equals K
prefix_sum + dict。注意条件是 if ps - k in store，因为 p_large - p_small = k，后期应该是要看 p_large - k 是否在 store 里的

837. Palindromic Substrings
使用 dp 解法，dp[j][i] 是看 str[j:i + 1] 是否是回文串，条件是 j + 1, i - 1 的位置也是回文，或者 j - i <= 2 ，还有 str[i] == str[j]

551. Nested List Weight Sum
DFS 解决

408. Add Binary
一开始想用 merge sorted arrays，但是其实每个元素可以这样获取：x = int(a[i]) if i >= 0 else 0，循环条件是 while i >= 0 or j >= 0

1704. Range Sum of BST
简单的分治法

945. Task Scheduler
最大的 frequency 是 k ，ans = (k - 1) * (n + 1) + p，p 有相同的频率

920. Meeting Rooms
按 interval.start 排序，遍历加判断

919. Meeting Rooms II
扫描线，将 start, end 变成数据点，start: + 1, end: - 1，每次看有多少个 meeting，比较需要多少个 room

760. Binary Tree Right Side View
获取每一层的最右节点，先遍历右节点，再遍历左节点

421. Simplify Path
将字符串以 '/' 分开，使用 stack，如果不是 '.' 和 '' 就加入，遇到 '..' 就 pop

打算现在开始跟随大神的脚步刷题，跪拜楼主，赐予我力量

# 2020/2/1

137. Clone Graph
用 dict 记录 old node -> new node，要注意将 root = node，最后 return store[root]，因为 node 变量会变

123. Word Search
遍历 + dfs

105. Copy List with Random Pointer
两种方法：
1) 用 dictionary 去存
2) oldNode -> newNode 去获取

95. Validate Binary Search Tree
分治法，每次递归获取 min_node, max_node

74. First Bad Version
二分法

62. Search in Rotated Sorted Array
二层对比：先 A[left] < A[mid]，再比 A[left] <= target <= A[mid]，都和 A[mid] 有关，第一次是 A[left]，再一次是 A[right]

32. Minimum Window Substring
固定左边界 i，再去找 window 的右边界 j，不断比较 min_len 即可

17. Subsets
dfs，注意要先排序，还有每次递归应该从 i 开始 -> self.dfs(nums, i + 1, curt, sets) 不是 self.dfs(nums, index + 1, curt, sets)

892. Alien Dictionary
按字母大小构图，拓扑排序。注意要用 heapify(queue) 来获取字符大小顺序。同时，每个字符都要加入图中，因为所有字符都要排序

362. Sliding Window Maximum
单调栈，注意每次加入的是 index，因为要 popleft 之前的时候需要 index 判断是否 window size 超过 k

121. Word Ladder II
先 BFS 从 end 到所有点，算距离，再 dfs 从 start 到 end，如果 distances[next_word] == distances[curt] - 1 才继续 dfs

653. Expression Add Operators
dfs，有点难。要保存 last ，因为有可能  3 + 2 * 2 的时候要先算乘法。还要注意最后要 if x == 0: break

# 2020/2/2

doc1. Find Parent
{ child: num of parents }
时间：O(n + m)，空间：O(n + m)

doc2. Has Common
1. 构图，2. 找所有 parents，3. 从所有 parents 里找是否存在 parent
时间：O(n + m)，空间：O(n + m)

doc3. Highest Parent
1. 构图，2. dfs/bfs 遍历所以 parents，3. 每次都赋值 self.result
时间：O(n + m)，空间：O(n + m)

doc4. Naive Calculator
遇到数字，计算当前 num，遇到符号，先处理前面的结果，再算新 sign。最后要再算一次结果
时间：O(n)，空间：O(1)

doc5. Basic Calculator
遇到 '('，加入 result 和 sign，重置 result 和 sign。遇到 ')'，先算括号里的 result，算 result * stack[-1] 和 result + stack[-1] 分别 pop，重置 sign
时间：O(n)，空间：O(1)

doc6. Variable Calculator
计算 result += sign * num -> result += sign * (num if is_num else self.map[var])
时间：O(n)，空间：O(1)

doc7. Friend List
构图
时间：O(n + m)，空间：O(n + m)

doc8. Get Department Stat
构图，三层循环判断
时间：O(depart * employee * friend)，空间：O(depart + employee + friend)

doc9. Friends In One Place
构图，BFS
时间：O(n + m)，空间：O(n + m)

doc10. Task Order
构图，BFS + 拓扑
时间：O(n + m)，空间：O(n + m)

doc11. Enter Exit
Enter: 1，Exit: -1，返回 status == 0 的人
时间：O(n)，空间：O(n)

doc12 Find 3 Times
遍历时间，每次从 i 开始找，二分去找
时间：O(name + times)，空间：O(name + times)

doc13. Domain Click
遍历，注意第一次的时候
时间：O(n + m)，空间：O(n + m)

doc14. Longest Continuous Common History
dp，dp[i][j] 表示前 i 和 前 j 的最长的历史长度，同时，每次更新 right = i - 1
时间：O(n * m)，空间：O(n * m)

doc15. Meeting Room
扫描线，最后判断 rooms == 1?

doc16. Merge Intervals
注意要先排序

doc17. Sparse Vector Class
注意要用 self.get(i)，不要 self.vector[i]

# 2020/2/2

1. 复习 databricks karat doc 1 - 17

615. Course Schedule
拓扑排序，但是构图的时候不要用 set ，要用 list，因为有可能边会重复

616. Course Schedule II
还是拓扑

696. Course Schedule III
按 deadline 排序，用 heap 存放 -duration，如果当下超出 deadline，那么去掉一节 duration 最长的课

742. Closest Leaf in a Binary Tree
BFS 的时候不要用 if-elif ，应该都是 if-if

41. First Missing Positive
将 nums[nums[i] - 1] 和 nums[i] 进行交换，最后要返回 i + 1 或者 n + 1

239. Sliding Window Maximum
push 的时候要对比 nums[queue[-1]] 和 nums[i]

91. Decode Ways
双数（正常情况和 10, 20 情况） + 单数

380. Insert Delete GetRandom O(1)
删除的时候，记得要 del self.positions[val]

426. Convert Binary Search Tree to Sorted Doubly Linked List
要用 inorder 去做，中间要初始化 self.first 和连接 self.prev 和 root，再将 self.prev = root 传下去。最后还要将 self.first 和 self.prev 首尾相连

350. Intersection of Two Arrays II
用 dictionary 做

981. Time Based Key-Value Store
用两个数组存，找时间的时候用二分

381. Insert Delete GetRandom O(1) - Duplicates allowed
注意要用 if not self.positions[val]，还有要用 random.choice(self.nums) -> 防止死循环

42. Trapping Rain Water
简单

114. Flatten Binary Tree to Linked List
返回 tail，如果有 left_tail 再继续下一步

314. Binary Tree Vertical Order Traversal
root.left: -1 root.right: +1

987. Vertical Order Traversal of a Binary Tree
这题和上一题有点不一样，坐标不一样，root.left: x - 1, y + 1，root.right: x + 1, y + 1。同时要 sorted, key = lambda x: (x[0], x[1], x[2])
将 mapping 数组变成 {index: [num...]}，返回 store.values()

# 2020/2/5

1. 复习 databricks karat doc 1 - 17

2. 复习 databricks leetcode 题库