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

# 2020/2/6

1. 完成 Karat 面试

1181. Diameter of Binary Tree
全局存放 diameter 结果，每次返回单一边最大值

920. Meeting Rooms
排序加判断

838. Subarray Sum Equals K
presum, x - y = k，先存 y 值，再找 k - x 值

595. Binary Tree Longest Consecutive Sequence
传 length 变量，临时长度为 length + 1，再将 length 传到下一层

547. Intersection of Two Arrays
记得两个数组都要先排序

451. Swap Nodes in Pairs
理清顺序即可

433. Number of Islands
DFS 解法

1315. Summary Ranges
三指针

# 2020/2/7

1281. Top K Frequent Elements
方法有三种：
1) 正常 Count + 排序
2) 正常 Count + heap
3) 正常 Count + quick select，这里要用 counts[values[(left + right) // 2]] 作为 pivot

1261. Longest Substring with At Least K Repeating Characters
以 counts[char] < k 分开，左右两边再去递归找

1235. Serialize and Deserialize BST
两种方法
1) DFS，分成 [left hand side, right hand side]
2) BFS，分成 [1, 2, 3, ....]，要设置 index 从 1 到 len(order)，每次 pop 一个 node 就 index + 1

363. Trapping Rain Water

137. Clone Graph
注意 corner case

107. Word Break
dp

32. Minimum Window Substring

892. Alien Dictionary
拓扑排序

859. Max Stack
popMax 的时候用一个 buffer 去装临时元素

582. Word Break II
dfs + memo

# 2020/2/7

1281. Top K Frequent Elements
方法有三种：
1) 正常 Count + 排序
2) 正常 Count + heap
3) 正常 Count + quick select，这里要用 counts[values[(left + right) // 2]] 作为 pivot

1261. Longest Substring with At Least K Repeating Characters
以 counts[char] < k 分开，左右两边再去递归找

1235. Serialize and Deserialize BST
两种方法
1) DFS，分成 [left hand side, right hand side]
2) BFS，分成 [1, 2, 3, ....]，要设置 index 从 1 到 len(order)，每次 pop 一个 node 就 index + 1

363. Trapping Rain Water

137. Clone Graph
注意 corner case

107. Word Break
dp

32. Minimum Window Substring

892. Alien Dictionary
拓扑排序

859. Max Stack
popMax 的时候用一个 buffer 去装临时元素

582. Word Break II
dfs + memo

# 2020/2/8

90. k Sum II
简单的 dfs

127. Topological Sorting
BFS ，DFS 两种方法

# 2020/2/9

597. Subtree with Maximum Average
DFS，递归结果返回 total, num

905. Nested List Weight Sum II
获取  BFS order，再从最后一层往前计算结果

1428. Keys and Rooms
DFS 写法，用 set 去存是否已被访问过了

1162. Out of Boundary Paths
DFS + memo, memo[(x, y, steps)] = paths，使用 DFS 在回溯的时候获取 paths

1220. Matchsticks to Square
计算 targets = [sum(nums) / 4] * 4，然后看是否能用完所有的火柴

376. Binary Tree Path Sum
这里要用 curt_sum 记录当前的结果，不能用 target - root.val 来递归，因为会出现重复，应在 not root.left and not root.right 的时候就终止

246. Binary Tree Path Sum II
复习

1020. All Paths From Source to Target
基础 DFS

1031. Is Graph Bipartite
二元着色，遍历所以节点去着色，如果 colors[i] == 0，尝试着色相反色，如果 colors[i] == colors[next] 则 return False

872. Kill Process
构图 + 遍历

1210. Increasing Subsequences
使用局部 visited，可以在区间中不会出现重复

650. Find Leaves of Binary Tree
self.leaves = [[xxx], [yyyy]]，leaves[i] 表示第 i 高度时候的叶子，注意高度是从 leaf -> root

596. Minimum Subtree
简单的 DFS

628. Maximum Subtree
和上一题反着来就行

881. Lonely Pixel II
对每一行进行扫描，获取该行的 col_counts 和 key，再看 key 的数量和每一列的 B 数量是否为 N

# 2020/2/10

778. Pacific Atlantic Water Flow
从四周开始 DFS ，然后找两个 set 的交集即可

1647. Path Search
构图，对于 node: neighbors ，对 neighbors.sort()。全局的 visited 主要是为了防止出现环

1101. Maximum Width of Binary Tree
这里和 vertical traversal 不一样的是, root.left -> 2 * index, root.right -> 2 * index + 1

1353. Sum Root to Leaf Numbers
找出所有的数，再 sum

1612. Smallest Path
dp 类似 unique path

790. Parser
不直接处理字符串，将字符串变成 list ，来处理 list

1015. Find Eventual Safe States

1003. Binary Tree Pruning

677. Number of Big Islands

619. Binary Tree Longest Consecutive Sequence III

652. Factorization

570. Find the Missing Number II

# 2020/2/11

742        Closest Leaf in a Binary Tree

41        First Missing Positive

239        Sliding Window Maximum

91        Decode Ways

380        Insert Delete GetRandom O(1)

426        Convert Binary Search Tree to Sorted Doubly Linked List

350        Intersection of Two Arrays II

981        Time Based Key-Value Store

381        Insert Delete GetRandom O(1) - Duplicates allowed

314        Binary Tree Vertical Order Traversal

42        Trapping Rain Water

114        Flatten Binary Tree to Linked List

987        Vertical Order Traversal of a Binary Tree

196. Missing Number

570. Find the Missing Number II

633. Find the Duplicate Number

928. Longest Substring with At Most Two Distinct Characters

104. Merge K Sorted Lists

67. Binary Tree Inorder Traversal
三种解法：1. dfs 2. 用 stack 3. Morris

392. House Robber
dp 解法

534. House Robber II
两次 dp，第一次去掉第一间房子，第二次去掉最后一间房子

# 2020/2/12

复习 Databricks 题库

131. The Skyline Problem + 218. The Skyline Problem

总结 Databricks 题库

# 2020/2/13

复习 Databricks 题库

总结 Databricks 题库

1534. Convert Binary Search Tree to Sorted Doubly Linked List
分治法

378. Convert Binary Tree to Doubly Linked List
分治法即可，左边生成 doubly linked list，右边生成 doubly linked list，全在一起就可以了

1823. Longest Prefix of Array
遍历一下，如果有符合要求的就设置为 True，最后再检查一下

1822. Minimum Moves
遇到 'a' offset += 1 ，如果 offset == 3 说明要变了，所以 steps += 1，重置 offset = 0

1821. Min Deletions To Obtain String in Right Format
可以一开始先数 A 的数，就是假定要将所有的 A 都变成 B，然后再遍历，如果是 A 那么就不用变，所以 rhs -= 1 ，如果是 B，说明要加入新的 B

1820. Find Letter
两个 set 存放 lower 和 upper，从 upper 取数，每次都比较是否比 result 大

1819. Longest Semi Alternating Substring
这题比较无聊

楼主厉害！
能否share一下google的list？