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

楼主是每个题都全部写码吗？感觉其实没必要，medium的话写个思路就行了，hard写全比较好

wangdiao01 发表于 2020-1-25 00:44
楼主是每个题都全部写码吗？感觉其实没必要，medium的话写个思路就行了，hard写全比较好

可能我还比较菜吧 哈哈 我是主攻 Medium, Hard 随缘了

hai_guai 发表于 2020-1-25 00:49
可能我还比较菜吧 哈哈 我是主攻 Medium, Hard 随缘了

这样效果不太好，如果你一天能刷20medium，换成20hard肯定也可以的。刷多了题的难度就都一样了，加油

# 2020/1/24

928. Longest Substring with At Most Two Distinct Characters
使用 dict 去记录每个 char 最右边的 index，每次都更新 r - l 的值，如果 len(dict) > 2，那么更新 l 的值（在 dict 里找最小）

386. Longest Substring with At Most K Distinct Characters
将上题的 2 变成 k 即可

669. Coin Change
dp -> 0 ~ amount，每次判断 for curt -> amount, curt - coin >= 0 时，就 dp[curt] = min(dp[curt], dp[curt - coin] + 1)，看上一次 + 1 是否更少。注意初始化时都是 float('inf')

92. Backpack
dp: n 行 m 列，n -> item, m -> size。 dp[i][j] 前i件物品，size == j

125. Backpack II
和前一题差不同就是 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] + 1) 变成  dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] + V[i - 1])

440. Backpack III
和前一题不同的是 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] + V[i - 1]) 变成  dp[i][j] = max(dp[i - 1][j], dp[i][j - 1] + V[i - 1]) ，因为第i个也可以继续选，所以是 dpi[i][xxxxx]

562. Backpack IV
dp[i] 表示 fill 到 i 的时候有多少条路，所以 dp[i] = dp[i] + dp[i - num]

563. Backpack V
和上题代码差不多，但是这里是从后往前，上一题从前往后是可以一直累积路径，而从后往前则不能，也就是每个数只能用一次

749. John's backyard garden
这题和 Coin Change 差不多，只是不计算多少个，而是简单地判断

588. Partition Equal Subset Sum
先 sum(nums) -> target，判断 target % 2 == 1? -> False。然后 target // 2 -> m，再用 dp 做即可

134. LRU Cache
Easy, Linked list + hash table 背背佳

楼主太可怕了。。。。一天刷我一个星期的量233333

加油。集中刷效果好

加油加油！祝早日上岸！！

doc1. Find Parent
统计每个节点的入度，再去看入度是 0 或者 1，然后加入 results 即可，这里要注意的是 parent 有可能也能成为 child

doc2. Has Common
递归找 Parents，将 parents 都找出来遍历判断是否有相同节点（Parents）

doc3. Highest Parent
递归找 Parents，每次都打擂台去更新结果即可

doc4. Calculator
很简单的 Calculator，在开始之前要加 '+' 来完成最后一次的计算

doc5. Basic Calculator
在前一题的基础上加一个 stack，遇到 '(' 将 result 和 sign 加入，result = 0, sign = 1 相当于重新算 result。遇到 ')' 计算当前的 result，然后算前一次的 sign 和与前一次的 result 相加，再 pop 掉两次

doc6. Variable Calculator
在前一题的基础上加一个 var，遇到字母就 var += char，再加一个 flag 判断当前应该是 number 还是 self.map[var]

doc7. Friend List
用边生成无向图

doc8. Get Department Stat
直接写即可，只要判断存在有不同部门的人就 break

doc9. Friends In One Place
BFS

doc10. Task Order
[0, 1] 先修完 1 再修 0，图里应该是 1 的 neighbors 是 0， 1 -> 0 应该表示 1 的下一步是 0，而不是关系。还有初始化的时候要将入度为 0 的加到 queue 里。

doc11. Enter Exit
enter: 1, exit: -1，每次都计算状态，如果不是 0 就是 mismatch

doc12. Find 3 Times
用 heap 来存时间，再次遍历的时候找 time + 60 的 index，看 index - i >= 3 ? -> 找到，break

doc13. Domain Click
简单的计数，注意要从后往前连接即可

doc14. Longest Continuous Common History
使用 dp，dp[i][j] 表示 user[i] 和 user[j] 前最长的 continuous common history，如果 user1[i - 1] == user2[j - 1]，dp[i][j] = dp[i - 1][j - 1] + 1，这个是长度，更新长度的时候也要更新 right = i - 1，最后 right -> right - i 去 append(user[i]) 即可

doc15. Meeting Room
先以 interval.start 来排序，lambda x: x.start，再比较 intervals[i].end > intervals[i + 1].start ? -> return False

# 2020/1/27

doc16. Merge Interval
先按 interval.start 来排序，设置 left, right，如果 right < interval.start，那么将 Interval(left, right) 加入，否则更新 right = max(right, interval.end)，将最后一次 Interval(left, right) 加入

doc17. Sparse Vector Class
并没有觉得什么难的

651. Binary Tree Vertical Order Traversal
使用 dictionary 来存，index: node，记 root: x, root.left: x - 1，root.right: x + 1，初始化 root -> 0，然后用 BFS 去遍历存好，再按顺序生成即可

363. Trapping Rain Water
每次累加 max - curt

453. Flatten Binary Tree to Linked List
divide_conquer，每次返回 tail，如果 left_tail 不存在就返回，否则连接，注意要将 root.left 断开，返回 -> right_tail or left_tail or root

1534. Convert Binary Search Tree to Sorted Doubly Linked List
first 和 prev 记录开头和结尾，使用 inorder 去做，left 看成是 prev，right 看成是 next 即可

362. Sliding Window Maximum
使用 deque，一直保证是单调递减的，如果 nums[dq[-1]] > nums[i] 就 dq.pop()，如果 dp[0] == i - k + 1 就是大于 k 了，就 popleft()，每次 results.append(nums[dq[0]) 就是最大值

131. The Skyline Problem
放弃了。。

854. Closest Leaf in a Binary Tree
dfs 遍历，将 parents 找全，找到疑似 k 的 node。从 node 开始做 BFS，分别加入左节点，右节点，parents 节点。如果遇到叶子节点就 return

189. First Missing Positive
遍历数组，将 A[A[i] - 1] 和 A[i] 进行交换，注意条件是 A[i] in bound，A[A[i] - 1] != A[i] 和 A[i] != i + 1。最后再遍历一次，遇到非法就 return i + 1

633. Find the Duplicate Number
使用快慢指针，slow, fast = nums[0], nums[nums[0]]，相遇后，slow = 0 再次移动找到开始环的 index

196. Missing Number
和 189 差不多，就是条件变成了 i != nums[i]，还有不能直接用 python 的方式去交换: A[A[i] - 1] != A[i] 和 A[i] != i + 1（错的）

570. Find the Missing Number II
dfs 去找，用 used 去存是否被访问过了，所有不符合要求的返回 -1，如果符合要求就返回结果，每次截取 1 -> 2 个字符

362. Sliding Window Maximum
复习

928. Longest Substring with At Most Two Distinct Characters
用 dictionary 记录 longest substring 的 { char: index }，如果 len(dict) > 2 就要更新 left = min(left, value)，再更新 longest = max(longest, right - left + 1)

692. Sliding Window Unique Elements Sum
用一个 dictionary 来存放 { num: counts }，遍历的时候先看 nums[i - k] 再看 nums[i]。要注意 window[nums[i]] == 1 的情况，分成 not unique 和 unique again

81. Find Median from Data Stream
左边是存 max_heap，右边存 min_heap，中位数就是 max_heap[0]

360. Sliding Window Median
先将前 k - 1 个元素加入 max_heap 和 min_heap，再 slide window，每次先加入，maintain balance，获取中位数，再移除 nums[i - k + 1]

604. Window Sum
prefix sum 解决，先初始化 sums[0]，再计算 sums[i] = sums[i - 1] + nums[i + k - 1] - nums[i - 1]