刷题记录帖子

整理下，昨天周赛的内容，和同学讨论过，有部分内容可以优化的就都优化了。

1598. Crawler Log Folder

其实就是 stack 的应用，到了 '../' 就 pop top elements，其他 string 就添加，'./' 保持不动。

1599. Maximum Profit of Operating a Centennial Wheel

题目比较拗口，但是做法其实就是用类似 simulation 的方法来模拟每个 时刻你的动作，因为 来参与的顾客的数量是不确定的，所以不能保证最准确的达到需要的人数，所以最快时间也是 O（n） n 是来参与的顾客数量。

当然有几个可以优化的地方，

1. 如果 顾客的 票钱 x 4 都低于 operation 的cost， 那么这个时候就不应该开始运作，直接停下是最好的选择。

2. 在 loop 完顾客数列后可以选择的方法不是像我原来的解法那样，每次减少 4 ，可以直接取 module，然后剩下的问题就是对于最后剩下的那几个不满 4 个那趟 rotation 是不是要转，这个取决于剩下的人数和 每次 operation cost 的差值。

1600. Throne Inheritance

这道题目，最正统的做法是用 Tree 来做，但是如果只是为了这道题目，可以用两个 dict 代替 tree class。
必须注意，如果某个王子公主排名在前面，即使 ta 挂了，也是 ta 的子女继位，除非他们都不在了，才到该王子公主的兄弟姐妹。 === 》 我半天才反应过来这点。

同时注意这道题目，可以用 继承人树 · heir tree， https://www.jiuzhang.com/problem/heir-tree/

但是其实你可以直接用字典模拟这个 tree，记录下 root 就行。

933. Number of Recent Calls

这道题目还是值得思考 == > 一个解法是 二分搜索，另一个就是 sliding window。

但是其实更好的方法 是 slide window 这个是 可以 O（n） 的，因为最坏就是要检查全部的 元素， 3000 个。

官方解答很好， https://leetcode.com/problems/number-of-recent-calls/solution/

39. Combination Sum

DFS 解决，但是如何去重 和 加速求解非常值得学习，这里记录下解法，https://maxming0.github.io/2020/10/02/Combination-Sum/

答案真是巧妙，通过两个调节比较

核心是，每次比较的时候判断是不是需要加入， 首先是排序

显然，
（1） num 大于 target 就没必要加入了， 甚至后面的都不用加入了
（2） 其次是，num 必须比已经加入答案的最后那个元素 大，否则，如果这个 num 加入就会算入了 更小的那个答案，这里必须加入以去重！

532 K diff Pairs in an Array

简单题，还是比较容易的，特比要注意的是 k == 0 和 k ！= 0 的情况是不同的。

k == 0 就是要找出现 2 次已经以上的数
k ！= 0 就直接超找 freq table 即可。

1288 Remove Covered Intervals

嗯，其实要理解下题意，我一开始一位是安排最多任务那种，所以删除掉了大的区间，但是其实这道题目是要保留大区间，删除小区间。

另外的思路就是按照左边排序, 同时需要对于右边的边界的负数也排序。
这样保证每次找到的右边的都是更长的那个区间。
然后依次查找 右边的边界，当然需要记下前面的右边的坐标。

参考这个帖子， https://maxming0.github.io/2020/10/04/Remove-Covered-Intervals/

1609. Even Odd Tree

还是经典的套路， level traversal

1. 
   
2. 
   
3. # Definition for a binary tree node.
   
4. # class TreeNode:
   
5. #     def __init__(self, val=0, left=None, right=None):
   
6. #         self.val = val
   
7. #         self.left = left
   
8. #         self.right = right
   
9. class Solution:
   
10.     def isEvenOddTree(self, root: TreeNode) -> bool:
    
11.         # level traversal
    
12.         stack = []
    
13.         stack.append( root )
    
14.         even = False
    
15.         while stack:
    
16.             current_level = []
    
17.             k = len(stack)
    
18.             even = not even
    
19.             while k > 0:
    
20.                 node = stack.pop(0)
    
21.                 # check value is meeting requirements
    
22.                 if even:
    
23.                     if node.val % 2 != 0:
    
24.                         current_level.append(node.val)
    
25.                     else:
    
26.                         return False
    
27.                 if not even:
    
28.                     if node.val % 2 == 0:
    
29.                         current_level.append(node.val)
    
30.                     else:
    
31.                         return False
    
32.                 k -= 1
    
33.                 if node.left: stack.append(node.left)
    
34.                 if node.right: stack.append(node.right)
    
35.             # check if meet the order requirements
    
36.             # edge case 1 : if duplicate, return False
    
37.             if len(current_level) != len(set(current_level)):
    
38.                 return False
    
39.             # check order
    
40.             if even:
    
41.                 needed_current_level = sorted(current_level)
    
42.                 if needed_current_level != current_level:
    
43.                     return False
    
44.             if not even:
    
45.                 needed_current_level = sorted(current_level, reverse=True)
    
46.                 if needed_current_level != current_level:
    
47.                     return False
    
48.         # finish loop
    
49.         return True
    

复制代码

1009. Complement of Base 10 Integer

这道题目做过，结果还是没做出来，最好的方法其实是 用 11111 mask 和 原数 取 XOR，这样就可以保留下 complment 的要求。

记忆！

701 Insert into a Binary Search Tree

啊啊啊啊啊啊啊啊啊啊啊，居然忘记了 BST 的 insert。

其实错误就发生在写法上，最简洁的方法是 如果 遇到null node 就是插入的 node，这个时候确实是需要新建 node 但是也相应的丢掉了，新建 node 的 parent。所以解决方法就是层层 递归的时候层层赋值。