刷题记录

刷题口头思路表达方式：

审题拆分题目关键词：
1. 最长/最大/最小等等： DP,
2. 是否能编辑/有重复：哈希表
3. 组合数目： DFS, BFS
4. 无重复：用字典/哈希表
5. 有无序/找出xxx：二分/排序/树遍历/ DFS/BFS
6. 子序列 (可以连续或者不连续)： DP 前后依赖
7. 公共子串： 2维DP
8. 公共前缀： DP
9. 连续子序列：公共前缀（DP）/ 单调栈
10. 只要能把问题拆解成明确的子问题，每次遍历都是子问题的重复叠加，就不会想其他乱七八糟的corner case 加if else.，除非是你的子问题没有想明白
数据结构工具
1. 单调栈：栈内元素单调增/减，用来找和大小相关的序列问题， 比当前进栈元素i刚好小（第二大）或刚好大（第二小）的值肯定在stack[-1]
2. 双指针：对array linkedlist，滑动窗口
3. 哈希表：去重，映射中间结果， key 不一定是位置索引， 可以是某种中间结果
4. DP：常数(只依赖上一次结果，上一次结果通过max, min等过滤选择)，一维度/二维 array (要记住依赖不同位置结果)
5. DFS/BFS回溯：排列组合 / 二维或树状搜索
6. Tree：搜索树（右边> root>左边）平衡树，完全数，
刷题方法：
1. 刷2次
2. 1刷刷思路和问题拆分方法以及题感，确保第一次刷快并覆盖大量题型
3. 2刷刷corner case，和记住细节

解题流程

确定问题，题目细节：输入，输出，输入范围，输出范围， corn case
确定思路方向：是什么类型题目(tree, dp, dfs, bfs等)，用什么数据结构：list，tree, heap, stack...
确定自己大概解法思路 (思路清晰的话可以跳过这一步)：可以先不沟通思路，自己先写伪代码
定义变量：
1. 定义变量, 说明含义, 作用 .
2. 定义表诉对象，为了简洁，后面说思路时直接用表述对象名称说明
拆分大问题成小问题（程序是遍历重复执行，执行的每步都是最小子问题）：
1. 遍历/递归过程中，有什么边界问题
2. 什么时候应该更新哪个变量/边界
3. 怎么更新变量（有哪些子case列出来）
4. 做不出来时，是否变量定义有问题
5. 什么时候终止程序/边界条件
6. 例子：
  1. 数组最长连续上升子序列
    问题拆分：怎么定义子序列？什么时候更新子序列边界？怎么更新子序列边界？怎么保存最长位置和返回？
  2. 二叉树中和为最大的路径
    问题拆分：怎么定义路径？经不经过root？路径的左右边界怎么确定？怎么保存路径并进行对比？
表达思路：每说一步，可以举个例子说明
写代码
分析复杂度

注意python细节

-用 for去初始化矩阵列表，不要用 [[0]*n]*m , 这种方法是弱引用，所有行都会指向同一个行！

dp = [[0 for i in range(cols+1) ] for j in range(rows+1) ]

动态规划解题流程：

确定当前问题是不是可以拆成子问题，比如输入矩阵或者数值，把它看成i, i+1的数值看看之间是否有依赖
DP的存储有O(1), O(n), O(n^2)
- 题目输入如果是1个1维度数值，一般是O(n)
- 如果是2维数值或多个1维数值，一般是O(n^2)
- 如果感觉当前最优解要依赖多个或者会变动的变量时，一般是用O(n)方法
- 如果感觉当前最优解依赖固定1~3 个变量时，一般用O(1)方法
- 最最最重要是定义清楚dp数组存放的元素物理含义！如果定义错了，就会觉得差了信息，一般就是问题拆分得不够细导致的！
- DP最考验初始值边界条件以及转移公式的情况有没有漏掉！
- DP题目变形：
  - 最长的xxx
    最大和，最大乘，连续子序列，蓄水池，子序列
  - 二维DP:
    最长公共子序列，最长公共子字符串（改写），最大正方形，二维路径和，二维连续路径
- DP 数组的索引一般代表含义有以下
  - 字符串/数组的位置索引: 多个字符串/数组就有多个索引。或者像回文串这种∟和自己对比的话就有2个位置索引，所以是2维DP
  - 代表限制条件：像背包问题，这种在变量v和为N限制条件下，找xxx子集最大值，那么dp的索引就是 限制条件+ 位置信息。比如 dp[i][j] 代表从0到i的数组里， v数组和为j的子集最大值
  - 前缀和 / 前子集最优解： dp[i]指 arr 0-i子arr 的最优解。 dp[i] - dp[j]代表中间子集最优解
  - 注意：只要有限制条件在，我们很难找到位置连续的最优解，这种情况只能加多一维的DP放限制条件。

二叉树解题流程：

把二叉树路径看成arr，但是遍历方式是树的遍历
注意点:
- 一般用递归
- 想清楚递归节点的输入，输出，
- 用bottom-up还是top-down 传参，
- 如果题目是加了DP，看是否要在递归外用一个变量存放额外状态数据
树题目变形：
- 树的直径
- 树+DP：树的最大直径（经过root），树的最大路径（不一定经过root）
- 多叉树(类似DFS，BFS)
- 搜索树：左子树所有数<root< 右子树所有数。
- 满二叉树：除了叶节点外，每个节点都有左右节点
- 完全树：树的左右子树高度<=1 /完全树，且叶节点都在左边
- 平衡树：树的左右子树高度<=1 /完全树