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

# 2020/2/15

复习 Databricks 题库

加了 Inorder traversal 的总结

加了 House Bobber 的总结

535. House Robber III

A: How to get a DP Path
Q: 用 backtrack 数组去记录，backtrack[i] 应该记录上一个的坐标。当要获取路径的时候，就要关注哪个 Index 要被加入到路径，否则就忽略或者移到下一个坐标

加了 Merge K Sorted Lists 的总结

# 2020/2/17

复习 Databricks 题库

准备明天的面试，BQ，项目介绍等

# 2020/2/19

935. Cartesian Product
dfs 组合问题，从每个 list 选一个数出来组成结果

1360. Symmetric Tree
对比 left.left 和 right.right 以及 left.right 和 right.left

1208. Target Sum
第一种是暴力 DFS 解法
第二种 DFS + memo, memo[(start, curt)] -> ways

1413. Tree
BFS + 找 fathers，要注意用 visited 去存已访问过的点

1410. Matrix Water Injection
一道经典的小岛问题

1479. Can Reach The Endpoint
常规小岛问题

808. Movie Network
图 + BFS + heap，注意不要把开始的点也算进去

1386. Cable Car Ride
DFS + memo, memo[x][y] = cost

878. Boundary of Binary Tree
找左边界，右边界，leaves 然后合在一起就可以了

1244. Minimum Genetic Mutation
word ladder 的 BFS 经典题

164. Unique Binary Search Trees II
分治，start -> end

# 2020/2/21

348. Design Tic-Tac-Toe
左到右，上到下，左上到右下，右上到左下，如果可以遍历完，就返回 player

138. Coy List With Random Pointer
两种方法：1) 用 hash table 存关系 2) old node -> new node

5. Longest Palindromic Substring
中间开始向两边看

151. Reverse Words in a String
使用内部函数即可

794. Valid Tic-Tac-Toe State
判断 o_num 和 x_num 的关系，再判断如果某个玩家赢了之后的情况

273. Integer to English Words
枚举 + 递归，多种情况都要考虑，分成 < 20, tens, thousands, million, billion

146. LRU Cache
Hash table + Linked list

42. Trapping Rain Water
两种方法，1) 双指针，2) 单调栈

134. Gas Station
一路走下去，遇到 gas_remain < 0 就从 i + 1 开始

443. String Compression
双指针做法，注意 chars[left + 1:left + 1 + len(len_str)] = len_str，这里要算的是 len_str 的长度

206. Reverse Linked List
很简单的一道题

楼主有点牛啊。。一天能刷这么多

# 2020/2/22

557. Reverse Words in a String III
比较直白的一道题

44. Wildcard Matching
两种方法：DFS + memo / DP。DFS + memo 要考虑多种情况，DP 只考虑当前情况

909. Snakes and Ladders
BFS + Hash Table，比较难的地方是算坐标，这里要 s - 1

103. Binary Tree Zigzag Level Order Traversal
正常的 BFS order traversal，不同的是需要一个中间的 queue 去记录，而不是直接 popleft，还需要有一个 flag 记录顺序

54. Spiral Matrix
经典题

297. Serialize and Deserialize Binary Tree
DFS 返回数组比较容易

769. Max Chunks To Make Sorted
找前缀最大和后缀最小， 每个区间结尾的位置必然是前缀Max小于下一个位置的后缀Min

768. Max Chunks To Make Sorted II
和前一题的解法一样

1185. Day of the Week
算两个时间点的天数差，再去取余，再去找星期几

1. Two Sum
很简单的一道题

22. Generate Parentheses
要注意的是 left num <= right num

470. Implement Rand10() Using Rand7()
比较 tricky 的一道题

200. Number Of Islands
Easy~

98. Validate Binary Search Tree
分治，要注意等于的情况也算是 False

我也要加一

# 2020/2/23

535. Encode and Decode TinyURL
很奇怪的一道题

93. Restore IP Addresses
普通的 DFS

25. Reverse Nodes in k-Group
遍历一次，每次先找 n1 ->...-> nk，断开 nk -> nk_next，将 n1 -> ... -> nk 反转，再继续

431. Encode N-ary Tree to Binary Tree
n-ary 可以生成
```
    root
   /
left
   \
     rest nodes
```

232. Implement Queue using Stacks
两个 stack 互相作用

127. Word Ladder
经典的 BFS 题

21. Merge Two Sorted Lists
EZPZ

510. Inorder Successor in BST II
如果有右节点，就找右节点的最左节点，否则要一直找一个 parent,使得 parent.val > node.val

105. Construct Binary Tree from Preorder and Inorder Traversal
这里要注意的是 preorder 和 inorder 都只去掉 root 的元素就可以了

445. Add Two Numbers II
获取 number 相加，再生成 linked list

236. Lowest Common Ancestor of a Binary Tree
判断 root 是否是 p, q。再去看左右两边的结果

836. Rectangle Overlap
这道题要静下心来想，要注意等于的情况

225. Implement Stack using Queues
两个 queue，pop 和 top 的时候要看最后一个 pop 出来的元素即可

8. String to Integer (atoi)
首先 strip，看符号，去掉非数字，生成数字，判断是否 overflow

23. Merge k Sorted Lists
EZ

53. Maximum Subarray
prefix sum + 全局记录 min sum 和 max sum

116. Populating Next Right Pointers in Each Node
BFS 分层法

# 2020/2/23

2. Add Two Numbers
使用 carry 贯穿

722. Remove Comments
考虑 open block 的情况

56. Merge Intervals
经典题

540. Single Element in a Sorted Array
二分法

99. Recover Binary Search Tree
找到 first = prev，和 second = root，交换这两个节点的值

# 2020/2/26

863. All Nodes Distance K in Binary Tree
传统 BFS + queue

450. Delete Node in a BST
分两种情况，第一，只有一个节点就直接接上，第二，两个节点找右节点的最左节点，交换值后更改树结构

33. Search in Rotated Sorted Array
二分法

121. Best Time to Buy and Sell Stock
遍历，找最小 price，和最大 profit

143. Reorder List
找中点，反序，合并