Summary.txt

排序算法总结

            时间复杂度           额外空间复杂度          稳定性
选择排序    O(N^2)                  O(1)                无
冒泡排序    O(N^2)                  O(1)                有
插入排序    O(N^2)                  O(1)                有

归并排序    O(NlogN)                O(N)                有               【稳定】
随机快排    O(NlogN)                O(logN)             无               【速度快,常数级领先】
堆排序      O(NlogN)                O(1)                无               【省空间】
==============================================================================================
计数排序    O(N)                    O(M)                有
基数排序    O(N)                    O(N)                有



二叉树的递归套路：
1、假设以X节点为头结点，假设可以向X的左右子树获取任何信息
2、基于1的假设，讨论以X为头节点的树，得到答案的可能性     ❗️(最重要)
    1）X节点参与
    2）X节点不参与
3、列出所有可能后，确定到底需要向左右子树获取什么信息
4、把左右子树信息求全集，就死任何一棵子树都需要返回的信息Info
5、递归函数都行需要返回Info，每一棵子树都这么要求
6、编写代码，在代码中考虑如何把左子树和右子树的信息整合出整棵树的信息Info



暴力递归：暴力递归就是尝试
1、将问题转化为规模缩小的子问题
2、有明确的不需要继续进行递归的条件(base case 边界条件)
3、有当得到了子问题的结果之后的决策过程
4、不记录每一个子问题的解


如何寻找递归问题的动态规划方式
1、设计暴力递归：重要原则+4种常见尝试模型！ 重点❗
2、分析是否否有重复解：套路解决
3、用记忆搜索->用dp表格结构实现动态规划：套路解决
4、看看dp表是否可以继续优化：套路解决     二维转一维、一维转单个变量
动态规划：即利用dp表记录相同子问题的结果，避免进行重复求解！

4种尝试模型：
1）从左往右的尝试模型
2）范围上的尝试模型
3）多样本位置全对应的尝试模型
4）寻找业务限制的尝试模型



树问题解法总结：
❗树的每个节点都会被访问三次，在不同的时机对节点进行处理，即不同的遍历方式。
❗前序位置的代码执行是自顶向下的，而后序位置的代码执行是自底向上的。
二叉树的所有问题，就是让你在前中后序位置注入巧妙的代码逻辑，去达到自己的目的，你只需要单独思考每一个节点应该做什么，其他的不用你管，抛给二叉树遍历框架，递归会在所有节点上做相同的操作。
二叉树题目的递归解法可以分两类思路:
1) 遍历一遍二叉树得出答案（前序💡），这个思路对应着【回溯算法核心框架】
2) 通过「分解」问题计算出答案（后序💡），这个思路对应着【动态规划核心框架】


❗二叉树的构造问题一般都是使用「分解问题」的思路：构造整棵树 = 根节点 + 构造左子树 + 构造右子树 (lc_105、Lc106、lc_654)

BFS/DFS
1）BFS常用于解决最短路径问题，因为BFS的搜索方式就是一圈一圈地往外扩展，最先触碰即为最短
2）DFS即和递归联系在一起