【实验抄题策略】笨办法抄题打卡

问题：1。自己刷题进展太慢，量不够，质也起不来 2. 形成障碍后，容易被打击，心理不太舒服，容易放弃，没有成就感，久而久之就抑郁了。

暂时解决方法：
1. 每天打卡
2.试验专题抄（提高深度）与大公司面试FB题抄（提高宽度）
3. 不讲究理解，能启发多少算多少，讲解速度与数量。
4. 回头看别人的录像

10.22、2020
目标：抄30个

今日专题：二叉树

1609. Even Odd Tree
1. BFS的队列应用 2. 难点奇偶的交替更新 3. 数学最大值小值的应用 math.inf 4. 前后值大小的比较 都很tricky

1. from collections import deque
   
2. class Solution:
   
3.     def isEvenOddTree(self, root: TreeNode) -> bool:
   
4.         q = deque()
   
5.         q.append(root)
   
6.         
   
7.         isEven = True
   
8.         prev_value = -math.inf
   
9.         
   
10.         # normal BFS or level-trasversal
    
11.         while q:
    
12.             level = []
    
13.             for _ in range(len(q)):
    
14.                 node = q.popleft()
    
15.                 level.append(node)
    
16.                
    
17.                 if node.left:
    
18.                     q.append(node.left)
    
19.                 if node.right:
    
20.                     q.append(node.right)
    
21.             # inspect level according to conditions
    
22.             for node in level:
    
23.                 curr_value = node.val
    
24.                
    
25.                 if isEven:
    
26.                     if curr_value%2 == 0 or curr_value <= prev_value:
    
27.                         return False
    
28.                 else:
    
29.                     if curr_value%2 != 0 or curr_value >= prev_value:
    
30.                         return False
    
31.                 prev_value = curr_value
    
32.                
    
33.             # set up for next iteration using the opporsite flag contions
    
34.             isEven = not isEven
    
35.             prev_value = -math.inf if isEven else math.inf
    
36.         return True

复制代码

1600. Throne Inheritance
心得：1. 王位继承应用题 2.二叉树的dfs应用 3. 字典和列表应用

1. class ThroneInheritance:
   
2. 
   
3.     def __init__(self, kingName: str):
   
4.         # taking kingname as root
   
5.         self.root = kingName
   
6.         # notDead will hold all the people who are alive and their level number
   
7.         self.alive = {}
   
8.         self.alive[kingName] = 0
   
9.         # hold edges exsisting in our graph
   
10.         self.edges = {self.root:[]}
    
11.     def birth(self, parentName: str, childName: str) -> None:
    
12.         # birth --> new child so update a live
    
13.         self.alive[childName] = self.alive[parentName] + 1
    
14.         # add praent to child edges i nthe edges dictionary
    
15.         if parentName in self.edges:
    
16.             self.edges[parentName].append(childName)
    
17.             if childName not in self.edges:
    
18.                 self.edges[childName] = []
    
19.         else:
    
20.             if childName not in self.edges:
    
21.                 self.edges[childName] = []
    
22.             self.edges[parentName] = [childName]
    
23.             
    
24. 
    
25.     def death(self, name: str) -> None:
    
26.         # removing the dead people from alive map
    
27.         del self.alive[name]
    
28. 
    
29.     def getInheritanceOrder(self) -> List[str]:
    
30.         hierarchy = []
    
31.         def dfs(cur, parent=-1):
    
32.             nonlocal hierarchy
    
33.             # current person available in alive then only add in hirachy
    
34.             if cur in self.alive:
    
35.                 hierarchy.append(cur)
    
36.                
    
37.             # traverse all the children of current node
    
38.             for i in self.edges[cur]:
    
39.                 if i!=parent:
    
40.                     dfs(i,cur)
    
41.         dfs(self.root)
    
42.         return hierarchy

复制代码

1530. 好叶节点对的个数
1. 先后序遍历 2. 队列里的处理逻辑还不太懂 3. 用了defaultdict 是啥？ 还要注意树高度，为了比较距离。  这题比较综合。

10/24 2020
回溯算法
本质：决策树的遍历过程。 解决决策树的上三个概念。 1. 路径（已作出的选择） 2. 选择列表（当前可以做的选择） 3. 结束条件（树底层，无法做出选择）
框架：
result = []
def backtrack(路径, 选择列表):
if 满足结束条件:
        result.add(路径)
        return

for 选择 in 选择列表:
        做选择
          backtrack(路径, 选择列表)   
        撤销选择
上述框架关键：for 循环里边的递归。 递归前做选择，递归后撤销选择


42. 回溯算法。原来小学就学过。 有了就不能再用了，只能从后面的结果中选择。 然后选择的各条路径就是最终的可能性。 很简单。






心中要有这个结构。
选择路径【1，2，3】 路径【】 选择：就是在节点发生，实际上，就是决策树。


如何遍历这棵树

void traverse(TreeNode root) {
      for (TreeNode child : root.childern)
        // 前序遍历需要的操作
        traverse(child);
        // 后序遍历需要的操作
}











创建访问过的结合 2. 放四个参数，结果，放过，空，数组 3. 子数组加入到结果 4. 做决策 5. 加访问过 -》回溯 -》移走 6 再来遍历第二个树。 关键是回复到上一个状态。 挺好玩。



51. N-Queens
回溯 2. 排出不合法选择 3. 做选择 4. 递归 5. 撤销选择 6. 困难度在于冲突检测。
衍生：数独算法。复杂度非常高。跟动归有联系。

1457. Pseudo-Palindromic Paths in a Binary Tree

伪回文路径的条数

伪回文： 122 可以变成 212 回文。

关键，需要一个字典 2. 字典用来计数 3. dfs的先序遍历 4. 根性全局遍历


1448. Count Good Nodes in Binary Tree

树里的好节点

思想： bfs 2. 队列是一个tuple （子树，和最大值（max，当前节点）） 3. 更新答案

相同的模板题：

112。 路径和：是否存在一条路径的节点和等于给定的值？
Bfs 2. 队列是tuple 3. 更新值用 value + node.val 4. 在根节点进行判断


100.对称树
1. 还是用bfs 2. continue 用法 3. 追加两个节点

102 . Level order traversal
Defaultdict 的使用 2. 深度的使用 3. 字典。values获得列表的使用 （很有意思）

103. Binary Tree Zigzag Level Order Traversal
队列，2. defualtdict 使用 3. Tuple 使用 4. 每一层的处理 5. 取得值
559. Maximum Depth of N-ary Tree
最大深度
1. 到达叶节点，更新，最大深度 2. 加子儿子到队列，并同时更新深度。

10/23 2020
昨天未完成任务：抄了15题，今天继续加油。  

1. 回到基础链表 2。 遍历的新认识： 访问一次且只访问一次。 二叉树10中递归，不使用栈的前中后序非递归遍历 3.
数组遍历框架
1.  线性迭代
for i in range(len(arr)):  
   # 对arr的处理或者有时需要对前后元素的一起处理。
链表有两种遍历方法：线性（迭代）与非线性（递归）
curr = head
while curr:
    # 对curr节点的操作
    curr = curr.next

递归法
def traverse(head) {
   # 操作头结点
  traverse（head.next）
}

树：
def traverse(root) {
   # 操作root结点
  traverse（root.left）
  traverse（root.right）
}

图：
def traverse(root) {
   # 操作root结点
  for child in root.children:
       traverse（child）
}

核心本质： 大部分算法技巧，本质都是树的遍历。
124. Binary Tree Maximum Path Sum
1. 后序遍历 2.  关键：全局最大值 3. 返回当前分支的最大值 3. 中间更新分支最大值
            self.ans = max(self.ans, left + right + root.val)
            return max(left, right) + root.val
105. Construct Binary Tree from Preorder and Inorder Traversal
1. 前序遍历：先处理根节点，在递归处理左子树，然后右子树 2. 结合数组进行划分 3. 融合数组与树，与递归遍历，很经典的题。

99. Recover Binary Search Tree
中序遍历 2. 排序， 交换。 数组遍历与树遍历的组合 经典
LeetCode 19.凑零钱问题 动态规划
产生一个递归树 2. 优化N叉树递归树 3.
# 不过是一个 N 叉树的遍历问题而已
def dp(n):
    for coin in coins:
        dp(n - coin)


N皇后
/* 提取出 N 叉树遍历框架 */
def backtrack(nums, track) {
    for i in range(len(nums))
                # 对track的处理
        backtrack(nums, track);
            # 对track的处理
}



动态规划
问题形式：求最值
所以：必然要穷举选择

# 1. 状态初始化 base case
dp[0][0][...] = base
# 2. 穷举所有状态
for 状态1 in 状态1的所有取值：
    for 状态2 in 状态2的所有取值：
        for ...
                        #3. 明确选择               
            dp[状态1][状态2][...] = 求最值(选择1，选择2…)

一、斐波那契数列
出现递归：
立马想到递归树。
规模： 子问题个数（刚好等于节点个数）*每个子问题需要时间 = 2*n
性质1：出现重叠子问题。


509  Fibonacci Number
法1. 带备忘录的递归法：（非线性遍历，递归剪枝）
    2. 备忘录字典记录{N：值}并初始化base case 3. 开始递归更新备忘录 4. 返回备忘录   
法二： 数组的迭代解法
        dp ={0:0,1:1}  这个叫动态规划表
        for i in range(2,N+1):  迭代（线性遍历）
            dp[i] = dp[i-1] + dp[i-2]   # 这个就叫状态转移方程。 过去dp[i-1]叫状态1，dp[i-2]叫状态2： 状态1 与状态2 相加 再给状态dp[i]（等号） 。 就叫做状态转移方程。 最关键的就是找出这个状态转移方程。
        return dp[N] 最后返回
3. 进一步优化，不需要动态规划整个表，只需要前两个变量 prev 和 curr.
        prev = 0
        curr = 1
        for i in range(2, N+1):  # 线性遍历
            sum = prev + curr
            prev = curr
            curr = sum
        return sum
相当于把整个状态表压缩成2个状态，这个就叫状态压缩。 （一般是2维到一维，一维到两个数）[/i][/i]

322. Coin change
dp和备忘录都是用空间换时间的问题。
关键：dp 数组的定义：当目标金额为 i 时，至少需要 dp[i] 枚硬币凑出。
至少知道备忘录（递归的剪枝，非线性）与动归表（线性过程，迭代法）

10、26、2020

BFS 算法再理解
本质，在图中，找到一条起点到终点的最短路径 2. 一定需要队列辅助 3.
变体： 走迷宫。 单词替换 3. 连连看
111.二叉树的最小深度
1. 递归法 2. bfs： edge case ， 队列， 循环队列， 扩展 下一层， 判断根节点，终点判断。 （BFS 是齐头并进，集体行动，是面。 DFS是单打独斗，是线）

752. 开锁
基本BFS  2. 队列 3. 锁的集合 4. 访问过的集合 5. 新字符串组成。
6。发现如果有target 可以用双向bfs来优化。



再次思考二分法：

思路简单，细节是魔鬼。 Knuth 说的。 主要是两点：
mid 是加一还是减一。 while 是《= 还是<

最好都用elif 来明确三个情况

1. 去哪儿搜索？ 搜索空间为空。 左闭右闭。
2. 下一步去哪儿搜索？


算法关键问题？ 没法处理【1，2，2，2，3】这种情况。 搜索2 返回index 2，但是我们想要索引1怎么办？
主要两块儿：1。 开区间还是闭区间 2. 不返回，如何缩小搜索空间。

双指针三兄弟：左右，快慢（链表），左右的衍生（反转），滑动指针（解字串）
双指针滑动窗口算法
起点是零
遍历
     
    然后遍历缩小小窗口
   
76. Minimum Window Substring

思路： 1. 右边扩大窗口，找到满足的字串（找可行解） 2. 左边缩小窗口，（找最优解）
辅助结构：计数器，用字典来表示。 need a:1， b：1，c:1
LeetCode 567 题，Permutation in String

思想：同样是字串问题。
LeetCode 第 438 题，Find All Anagrams in a String
Anagrams  异位词：本质，返回第一个索引。 同样道理
这是 LeetCode 第 3 题，Longest Substring Without Repeating Characters
一样的思路，滑动窗口。

股票买卖 问题：
关键：
定义状态 ：  哪天做了什么事情后，当前持有状态
dp[n-1][K][0] 最后一天，交易 了K次，手里没有股票
几个题都类似。  含冷冻期和手续费 。
买卖股票的最佳时机
买卖股票的最佳时机 II
买卖股票的最佳时机 III
买卖股票的最佳时机 IV
最佳买卖股票时机含冷冻期
买卖股票的最佳时机含手续费
本质：基本思想 ，还是穷举 各个 状态 ， 定义状态，然后确定状态转化 ，



打家劫舍问题

关键：动态规划，定义状态 ，定义选择抢，不抢 。状态转移。

10、28、2020

10/28、2020

思路：描述一棵树 【2，#，3，#】 left + ‘’，’ + right + root。val
设置一个集合，如果发现有重复”abc“，哈哈，把当前节点放进结果。否则，把’abc’放到集合。 最后返回子树。 如何去重？
用字典额外记录次数。

自取子树对应出现的次数加一。

416. 分割等和子集
与背包问题相同



有个符号叫 > 。 啥意思，就是把命令的输出送入到一个文件中。

main负责接收数据，解负责求解， dp负责具体算法

10、29、2020

数据装在各种容器里

算法是如何一步步操作容器里的这些数据。


线性的：一维数组，二维数组

涉及到数组：必然遍历
For I in range(len(a)):
   

操作的话就是访问。具体的逻辑有：
比大小， max = a[i]
求和  sum+=a[i]
复制  b[i] = a[i]

0 1 2 …. N-1

一半：
临时值为 当前要交换的值
当前值 = a[N-1-i]
a[n-1-i] = 临时值



非线性：列表，树，图，





表面现象（各种各样的题）看本质！！！！！

迷宫（现象） —》 图的遍历 —》 N叉树的遍历 —》 二叉树的遍历 （本质）



递归的理解：
（空间）我有多少头发：一根头发 + 剩下的头发
（时间）我今年几岁： 去年的岁数+1；我1990出生
排序： 先排左边，再右边，合并。 左边怎么拍，读前面的话。

所以：1。 最简单子问题的结束条件 2. 子问题的自我调用
Def get_age(year):
        if year = 1980:
        return 0
      return get_age(year-1) + 1

递归与逆向思考，树形思考，直到看到问题的尽头（或者本质，最基本的东西，也可以说最本质的东西 ）。动态规划的递归解法就是逆向思考， 而用动态规划表就属于正向思考。 但是也需要先流向思考，再正向演绎。

list表长度：
def size（head）：
        if not head：
                reutrn 0
       return 1 +size（head。next ）


最关键是相信： size（head）能够完成任务。 不能跳入细节。

遍历二叉树

遍历（根）：
if not root：
        return
   遍历（左子树）
   遍历（右子树）

遍历N叉树：
if  not root:
        return
For 儿子 in 根的儿子们:
    遍历(child)




437. Path Sum III
计算路径和的个数

没有树：
路径为零

否则
   左边路径和的个数 + 右边路径和的个数 + 以该积点为根，凑出的个数

思想：用了两个递归遍历，



分治法：
解（整个区域）：
      解（左边）
     解（右边）
     合并（左边，右边）
靠： 这玩意儿就是二叉树后序遍历遍历， 合并就是回溯。

这个太狠了，佩服

半年没来，好多题都忘记了。今天重新打卡。
今日目标：
1道设计题 + 5道编程题