刷题技巧+经典题

1. 刷题方法论

刷题口头思路表达方式：

审题拆分题目关键词：
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) ]

2. 不同类型题目技巧

2.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放限制条件。

2.2 二叉树解题流程：

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

3. 各类型经典题

DFS/BFS树遍历的变型题

662. 二叉树最大宽度 - 力扣（LeetCode）力扣 LeetCode

图

https://www.nowcoder.com/practice/a77b4f3d84bf4a7891519ffee9376df3?tpId=196&tqId=37158&rp=1&ru=%2Factivity%2Foj&qru=%2Fta%2Fjob-code-total%2Fquestion-ranking&tab=answerKey

数组

正在做：

多叉树的直径_牛客题霸_牛客网www.nowcoder.com

最长公共子序列(二)_牛客题霸_牛客网www.nowcoder.com

二叉树中的最大路径和_牛客题霸_牛客网www.nowcoder.com

多叉树的直径_牛客题霸_牛客网www.nowcoder.com

最大数_牛客题霸_牛客网www.nowcoder.com

连续子数组的最大乘积_牛客题霸_牛客网www.nowcoder.com

可以想想连续子数组最大乘积的变种，结果返回连续子序列而不是最大乘积

连续子数组的最大乘积_牛客题霸_牛客网www.nowcoder.com

通过部分的题目/难题

最大正方形_牛客题霸_牛客网www.nowcoder.com

最长上升子序列(三)_牛客题霸_牛客网www.nowcoder.com

多叉树的直径_牛客题霸_牛客网www.nowcoder.com

4. 寻找两个正序数组的中位数 - 力扣（LeetCode）力扣 LeetCode

多叉树的直径_牛客题霸_牛客网www.nowcoder.com

987. 二叉树的垂序遍历 - 力扣（LeetCode）力扣 LeetCode

已刷题目

0、容易卡边界题

154. 寻找旋转排序数组中的最小值 II - 力扣（LeetCode）力扣 LeetCode

最长公共前缀_牛客题霸_牛客网www.nowcoder.com

4. 寻找两个正序数组的中位数 - 力扣（LeetCode）力扣 LeetCode

76. 最小覆盖子串 - 力扣（LeetCode）力扣 LeetCode

1. Sorting

quick sort

https://app.gitbook.com/o/MQg1qdqArWYMTe4S9fPp/s/-MU4s3p9Ql9V0G1xvT9E-2910905616/datastructure/sorting/find-topk-largest-quickselect-kuai-su-xuan-ze-method

merge sort

https://app.gitbook.com/o/MQg1qdqArWYMTe4S9fPp/s/-MU4s3p9Ql9V0G1xvT9E-2910905616/datastructure/sorting/mergesort-linkedlist

heap sort

https://app.gitbook.com/o/MQg1qdqArWYMTe4S9fPp/s/-MU4s3p9Ql9V0G1xvT9E-2910905616/datastructure/heap-and-queue/find-the-k-largest

23. 合并 K 个升序链表 - 力扣（LeetCode）力扣 LeetCode

378. 有序矩阵中第 K 小的元素 - 力扣（LeetCode）力扣 LeetCode

最大数_牛客题霸_牛客网www.nowcoder.com

2. Search

二分查找-II_牛客题霸_牛客网www.nowcoder.com

154. 寻找旋转排序数组中的最小值 II - 力扣（LeetCode）力扣 LeetCode

3. stack & heap /哈希表

有效括号序列_牛客题霸_牛客网www.nowcoder.com

滑动窗口的最大值_牛客题霸_牛客网www.nowcoder.com

76. 最小覆盖子串 - 力扣（LeetCode）力扣 LeetCode

4.单调栈

84. 柱状图中最大的矩形 - 力扣（LeetCode）力扣 LeetCode

5.LinkList

25. K 个一组翻转链表 - 力扣（LeetCode）力扣 LeetCode

判断一个链表是否为回文结构_牛客题霸_牛客网www.nowcoder.com

判断链表中是否有环_牛客题霸_牛客网www.nowcoder.com

反转链表_牛客题霸_牛客网www.nowcoder.com

合并k个已排序的链表_牛客题霸_牛客网www.nowcoder.com

链表中倒数最后k个结点_牛客题霸_牛客网www.nowcoder.com

6.Tree

树遍历

1522. N 叉树的直径 - 力扣（LeetCode）力扣 LeetCode

二叉树的镜像_牛客题霸_牛客网www.nowcoder.com

重建二叉树_牛客题霸_牛客网www.nowcoder.com

树+ DP

7. 字符串

151. 反转字符串中的单词 - 力扣（LeetCode）力扣 LeetCode

字符串+DP:

72. 编辑距离 - 力扣（LeetCode）力扣 LeetCode

132. 分割回文串 II - 力扣（LeetCode）力扣 LeetCode

72. 编辑距离 - 力扣（LeetCode）力扣 LeetCode

84. 柱状图中最大的矩形 - 力扣（LeetCode）力扣 LeetCode

8.DFS/BFS / backtracking

dfs/bfs 看成树的特例(遍历顺序，限制遍历步数，遍历顺序，剪纸等)

216. 组合总和 III - 力扣（LeetCode）力扣 LeetCode

# 组合和排列的dfs不一样的地方在于：
         组合每层会遍历一个选项， 分支只有这个选项用还是不用 2条路
        
        排列的话， 每层都会把选项列表遍历，但是会把已经选过的选项放到头部
           下一层只会遍历后面没有用的选项。 考虑哪个选项先用后用