力扣经验：刷题范式

数组的题

• 连续子数组
  • 求和的，可以想着转化为累积和之差。注意最好先放一个和为0的值 map.put(0,出现次数/索引/...)，因为有可能需要减0呢。
  • 求正数求和的，可利用双指针穷尽做滑动窗口来延伸或收缩。
  • 求乘积的，不要想着取对数，因为会有精度损失，切记，题解误我。
  • 其他的，一般都可以尝试使用滑动窗口。

深度优先搜索递归实现的题

递归三步走：

• 递归函数的返回值、参数，都有什么意义，按需使用

• 递归函数的终止条件是什么

• 递归函数的遍历过程的确定，如何遍历？记得要恢复哦！对于一棵解树，一般来说，for循环遍历了树的宽度，backtrack即递归遍历了树的高度。

• 易错点

  • 结果的收集，必须使用 new ArrayList<>(list)，必须要 new ，原因是只收集引用，没有半毛钱用，最后都指向同一个地址，根本没有保存结果！

图

图在算法的背景可能会千变万化，有可能是关于一个矩阵，也可能是关于某些物体或人物，但万变不离其宗，要深刻理解图是用来研究物体与物体之间的关系的。

物体就是图中的节点，如果两个物体之间存在某种关系，那么这两个物体在图中对应的节点之间就有一条边相连。很多时候找到图中的节点和边是解决图的问题的关键。

图的搜索

• 很多问题，可以通过 BFS 或 DFS 解决。
• 如果路径的顺序很重要，那么要用回溯（DFS），不用想着用迭代实现回溯，这是相当复杂难做的事情，得不偿失。
• 如果要无权图的最短路径，那么BFS 合适，往往还会用双队列，这样类似树中的层次遍历，从而知道路径的长度何时该增加。
• 如果是有向无环图DAG，那么是不用考虑是否访问过的问题的，一定不会重复访问。但如果是无向图，就往往需要一个数组来记录节点是否已经访问过，防止重复访问。

拓扑排序四步走

拓扑排序可以解决与任务顺序相关的问题。如果某些任务必须在其他任务之前（或之后）完成，则可以用一个有向图描述任务之间的依赖关系，然后通过拓扑排序得到所有任务的执行顺序。

拓扑排序：每次删入度为0的节点，直到空或没有这样的节点。 步骤：

1. 用哈希表构造有向图的邻接表
2. 构造入度数组，并进行初始化
3. 广度优先搜索，搜索所有入度为0的节点，删入度为0的节点之后，更新入度数组，如果变成了0，则入队
4. 判断拓扑序列长度是否等于所有节点数（图空否）

并查集三步走

并查集，开始的时候大家都是孤岛，根节点就是自己，然后我们不断地合并、修改指针，直到所有边都访问到。

1. 数组初始化，每个节点的 parent 指针都指向自己。数组 roots 存放所有节点的祖先节点（根节点，路径压缩）【如果要求子集中元素数量，那么还要再创建一个 counts 数组，存储一份子集元素中的数量，需要在 union 中更新】。
2. 根据所有相连的边，不断地进行查找、合并。
3. 查找用递归、同时能修改查找路径上的所有节点的 parent 指针，合并前先调用查找然后看是否同一子图，是则合并失败，不是则直接将 parent 指针修改一下即可。

有向图是否有环？拓扑排序 DAG ！ 无向图是否有环？并查集！

关于求子集的个数、子集中元素的个数，可以试试把问题转化为图的问题，那么就可以转化为子图的数目、子图中元素数目，应用图的搜索、并查集等！

排序问题

手撕快排

注意预先++和–比判断之后再进行要好，可以通过举例 [3,2,1] 的排序进行查看，我在做 剑指 Offer 40的时候对手撕快排进行了多次尝试，算法那本书里面的写法很优美，严蔚敏的写法也没出错，但是按自己的思路就会错，这一点还需要仔细思考与总结，特别是我的写法跟严蔚敏的很像。