在上一篇文章 算法模式：变治法 介绍一种有魔力的，可以将复杂问题化繁为简，化腐朽为神奇的算法模式：变治法。本篇文章，介绍一种“一步三回头”、“落棋有悔”的算法模式：回溯。
回溯 “回溯”算法也叫“回溯搜索”算法，主要用于在一个庞大的空间里搜索我们所需要的问题的解。我们每天使用的“搜索引擎”就是帮助我们在庞大的互联网上搜索我们需要的信息。“搜索”引擎的“搜索”和“回溯搜索”算法的“搜索”意思是一样的。
“回溯”指的是“状态重置”，可以理解为“回到过去”、“恢复现场”，是在编码的过程中，是为了节约空间而使用的一种技巧。而回溯其实是“深度优先遍历”特有的一种现象。之所以是“深度优先遍历”，是因为我们要解决的问题通常是在一棵树上完成的，在这棵树上搜索需要的答案，一般使用深度优先遍历。
“全排列”就是一个非常经典的“回溯”算法的应用。我们知道，N 个数字的全排列一共有 \$N!\$ 这么多个。
使用编程的方法得到全排列，就是在这样的一个树形结构中进行编程，具体来说，就是执行一次深度优先遍历，从树的根结点到叶子结点形成的路径就是一个全排列。
说明：
每一个结点表示了“全排列”问题求解的不同阶段，这些阶段通过变量的“不同的值”体现；
这些变量的不同的值，也称之为“状态”；
使用深度优先遍历有“回头”的过程，在“回头”以后，状态变量需要设置成为和先前一样；
因此在回到上一层结点的过程中，需要撤销上一次选择，这个操作也称之为“状态重置”；
深度优先遍历，可以直接借助系统栈空间，为我们保存所需要的状态变量，在编码中只需要注意遍历到相应的结点的时候，状态变量的值是正确的，具体的做法是：往下走一层的时候，path 变量在尾部追加，而往回走的时候，需要撤销上一次的选择，也是在尾部操作，因此 path 变量是一个栈。
深度优先遍历通过“回溯”操作，实现了全局使用一份状态变量的效果。
解决一个回溯问题，实际上就是一个决策树的遍历过程。只需要思考 3 个问题：
路径：也就是已经做出的选择。
选择列表：也就是你当前可以做的选择。
结束条件：也就是到达决策树底层，无法再做选择的条件。
这三个问题也就对应回溯三部曲：
定义递归函数以及参数
确定递归终止条件
思考递归单层搜索逻辑
代码方面，回溯算法的框架：
result = [] def backtrack(路径, 选择列表): if 满足结束条件: result.add(路径) return for 选择 in 选择列表: 做选择 backtrack(路径, 选择列表) 撤销选择 其核心就是 for 循环里面的递归，在递归调用之前「做选择」，在递归调用之后「撤销选择」，特别简单。
必须说明的是，不管怎么优化，都符合回溯框架，而且时间复杂度都不可能低于 \$O(N!)\$，因为穷举整棵决策树是无法避免的。这也是回溯算法的一个特点，不像动态规划存在重叠子问题可以优化，回溯算法就是纯暴力穷举，复杂度一般都很高。
玩回溯，一定要画出递归调用树。这样可以帮助我们更深入地理解整个回溯的过程，方便进一步剪枝优化。
回溯优化，重要的是，要学会剪枝！
LeetCode 46. 全排列 LeetCode - 46. 全排列 给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
在上一篇文章 算法模式：分治法 介绍一种可用于处理节点前后顺序的算法模式：拓扑排序。本篇文章，介绍一种有魔力的，可以将复杂问题化繁为简，化腐朽为神奇的算法模式：变治法。
变治法 D瓜哥最早知道变治法也是在 《算法设计与分析基础》 中。这里也直接引用该书的介绍。
变治法，就是基于变换的一种思想方法，首先把问题的实例变得容易求解，然后进行求解。
变治法的工作可以分成两个阶段：首先把问题变得更容易求解，然后对实例进行求解。根据我们对问题实例的变换方式，变治思想有3种主要的类型：
实例化简(Instance simplification) — 指将原问题变换为同样问题的一个更简单或者更方便的实例。一个典型的案例是：去重时，先排序，
列表预排序
检验数组中元素的唯一性
模式计算
查找问题
高斯消元法
系数矩阵的LU分解(LU decomposition)
计算矩阵的逆
计算矩阵的行列式
AVL 树
改变表现(Representation Change) — 指将原问题变换为同样实例的不同表现。经典的栗子：霍纳法则。
多路平衡查找树（最简单的情况：2-3树）
求多项式的霍纳法则
两种二进制幂算法
堆排序
问题化简(Problem reduction) — 指把一个给定的问题变换为另一个可以用已知算法求解的问题。（归化思想）转换的难题在于如何找到一个变换的目标算法。典型案例是背包问题，背包问题的本质是线性规划。了解了线性规划的本质后，才能更好地解决高维的背包问题。
求最小公倍数
计算图中的路径数量
最优化问题（最大化问题(maximization problem)、最小化问题(minimization problem)）
线性规划（单纯形法、0/1背包问题）
简化为图问题
LeetCode 474. 一和零 LeetCode - 474. 一和零
给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
请你找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1 。
在上一篇文章 算法模式：减治法 介绍一种有魔力的，可以将复杂问题化繁为简，化腐朽为神奇的算法模式：减治法。本篇文章，继续介绍一种有魔力的，可以将复杂问题化繁为简，化腐朽为神奇的算法模式：分治法。
分治法 关于分治法的内容，这里继续参考 《算法设计与分析基础》 中的内容。
分治法是按照以下方案工作的。
将一个问题划分为同一类型的若干子问题，子问题最好规模相同。
对这些子问题求解（一般使用递归方法，但在问题规模足够小时，有时也会利用另一个算法）。
有必要的话，合并这些子问题的解，以得到原始问题的答案。
图 1. 分治法 从字面上分析就可以看到有哪些步骤：
分-分解-将问题分解为规模更小的子问题，子问题最好相同或相似；
治-求解-将这些规模更小的子问题逐个击破；
合-合并-将已解决的子问题合并，最终得出原问题的解；
从上述步骤中我们可以看出，分治算法一般适用满足以下条件的场景：
问题规模缩小到一定的程度就可以很容易解决；
问题可以分解为若干个规模较小的相同问题；
问题分解出的若干子问题的解可以合并为该问题的解；
每个子问题都是独立的，相互之间没有交集。（这是区别分治法与减）
在“分”的过程中，我们尽可能让分解出的子问题与原始问题相似，而规模更小。这刚好符合递归的特性。因此，分治法往往与递归联系在一起。
在分治法最典型的运用中，问题规模为 n 的实例被划分为两个规模为 n/2 的实例。更一般的情况下，一个规模为 n 的实例可以划分为 b 个规模为 n/b 的实例，其中 a 个实例需要求解（这里，a 和 b 是常量，a≥1，b>1）。
\$T(n) = aT(n/b) + f(n)\$ 其中，\$f(n)\$ 是一个函数，表示将问题分解为小问题和将结果合并起来所消耗的时间
分治法的典型案例如下：
归并排序
快速排序
二叉树的经典遍历算法和其他类似的算法都需要递归处理左右两棵子树
Strassen 算法
最近对问题
凸包问题
分治法对分治出的部分需要分别处理，进行分开的单独计算，而减治法则利用了"一个问题给定实例的解和同样问题较小实例的解之间的关系"，只针对部分子问题求解，减治掉的那部分就不需要了。
减常因子的减治法也可以看做是分治的变种。
LeetCode 148. 排序链表 LeetCode - 148. 排序链表 给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
在上一篇文章 算法模式：拓扑排序 介绍一种可用于处理节点前后顺序的算法模式：拓扑排序。本篇文章，介绍一种有魔力的，可以将复杂问题化繁为简，化腐朽为神奇的算法模式：减治法。
减治法 D瓜哥最早知道减治法是在 《算法设计与分析基础》 中。这里也直接引用该书的介绍。
减治(decrease-and-conquer)技术利用了一个问题给定实例的解和同样问题较小实例的解之间的某种关系。自底向上版本往往是迭代实现的，从求解问题的一个较小实例开始，该方法有时也称为增量法(Incremental Approach)。
减治法有3种主要的变化形式：
减去一个常量。在减常量(decrease-by-a-constant)变化形式中，每次算法迭代总是从实例中减去一个相同的常量。
插入排序
减去一个常量因子。减常因子(decrease-by-a-constant-factor)技术意味着在算法的每次迭代中，总是从实例的规模中减去一个相同的常数因子。在大多数应用中，这样的常数因子等于2，其实就是减半。
二分查找
减去的规模是可变的。在减治法的减可变规模(variable-size-decrease)变化形式中，算法在每次迭代时，规模减小的模式都是不同的。
计算最大公约数的欧几里得算法是这种情况的一个很好的例子。 \$gcd(m, n)=gcd(n,m mod n)\$
LeetCode 50. Pow(x, n) LeetCode - 50. Pow(x, n) 实现 pow(x, n) ，即计算 x 的整数 n 次幂函数（即，xn）。
示例 1：
输入：x = 2.00000, n = 10 输出：1024.00000 示例 2：
输入：x = 2.10000, n = 3 输出：9.26100 示例 3：
输入：x = 2.00000, n = -2 输出：0.25000 解释：2-2 = 1/22 = 1/4 = 0.25 提示：
在上一篇文章 算法模式：快速选择 介绍了如何利用快排思想快速选出第 K 个 最 X 的元素。本篇文章，介绍一种只需 \$O(1)\$ 时间就可以完成排序的算法模式：循环排序。
循环排序 循环排序讲述的是一种很好玩的模式：可以用来处理数组中的数值限定在一定的区间的问题。这种模式一个个遍历数组中的元素，如果当前这个数它不在其应该在的位置的话，咱们就把它和它应该在的那个位置上的数交换一下。你可以尝试将该数放到其正确的位置上，但这复杂度就会是 \$O(n^2)\$。这样的话，可能就不是最优解了。因此循环排序的优势就体现出来了。
图 1. 循环排序 循环排序适用的场景：
包含连续数字的数组（如 1 到 n 或 0 到 n-1）
需要找出缺失/重复数字的问题
需要原地排序且时间复杂度要求高的情况
LeetCode 41. 缺失的第一个正数 LeetCode - 41. 缺失的第一个正数
给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 \$O(n)\$ 并且只使用常数级别额外空间的解决方案。
示例 1：
输入：nums = [1,2,0] 输出：3 解释：范围 [1,2] 中的数字都在数组中。 示例 2：
输入：nums = [3,4,-1,1] 输出：2 解释：1 在数组中，但 2 没有。 示例 3：
输入：nums = [7,8,9,11,12] 输出：1 解释：最小的正数 1 没有出现。 提示：
1 <= nums.length <= 105
-231 <= nums[i] <= 231 - 1
在上一篇文章 算法模式：Top K 问题 介绍了如何利用堆快速选出最 X 的 K 个元素。本篇文章，介绍一种可以快速选择第 K 个 最 X 元素的算法模式：快速选择。
快速选择 快速选择起源于快排算法。在快排算法中，把元素根据基准元素分成左右两部分，一边的元素小于基准元素，另外一个的元素大于等于基准元素，再对两边的元素递归处理，最终得到有序结果。受此启发，在将元素根据基准元素分成左右两部分后，这里假设，左边小于基准元素，右边大于等于基准元素，那么会有如下三种情况：
当前基准元素所在位置正好是 K，正好是所求结果，直接返回；
当前基准元素所在位置小于 K，那么 K 位置在当前基准元素的右边；
当前基准元素所在位置大于 K，那么 K 位置在当前基准元素的左边；
所以，该模式不仅适用于求第 K 个之最元素，也适用于求“Top K 问题”。
LeetCode 215. 数组中的第K个最大元素 LeetCode - 215. 数组中的第K个最大元素 给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 \$O(n)\$ 的算法解决此问题。
示例 1:
输入: [3,2,1,5,6,4], k = 2 输出: 5 示例 2:
输入: [3,2,3,1,2,4,5,5,6], k = 4 输出: 4
在上一篇文章 算法模式：双指针 介绍了双指针的算法模式。本篇文章，介绍一种类似双指针的算法模式：滑动窗口。
滑动窗口 滑动窗口类型的题目经常是用来执行数组或是链表上某个区间（窗口）上的操作。比如找最长的全为1的子数组长度。滑动窗口一般从第一个元素开始，一直往右边一个一个元素挪动。当然了，根据题目要求，我们可能有固定窗口大小的情况，也有窗口的大小变化的情况。
图 1. 滑动窗口 滑动窗口大概思路如下：
// 向前滑动窗口 while (right < array.lenght) { // 扩大窗口，将元素放入窗口 right++; while (缩小窗口条件) { // 处理窗口内的元素 // 缩小窗口，将元素丢出窗口 left++; } } 下面是一些我们用来判断我们可能需要上滑动窗口策略的方法：
问题的输入是一些线性结构：比如链表，数组，字符串之类的
让你去求最长/最短子字符串或是某些特定的长度要求
LeetCode 3. 无重复字符的最长子串 LeetCode - 3. 无重复字符的最长子串 给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。 示例 2:
输入: s = "bbbbb" 输出: 1 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。 示例 3:
输入: s = "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。 请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
在上一篇文章 算法模式：区间合并 介绍了合并区间所用的算法模式。本篇文章，介绍一种即可以用在数组，又可以用在链表中的算法模式：双指针。
双指针 双指针是这样的模式：两个指针朝着左右方向移动（双指针分为同向双指针和异向双指针），直到他们有一个或是两个都满足某种条件。双指针通常用在排好序的数组或是链表中寻找对子。比如，你需要去比较数组中每个元素和其他元素的关系时，你就需要用到双指针了。
需要双指针的原因是：如果你只用一个指针的话，你得来回跑才能在数组中找到你需要的答案。这一个指针来来回回的过程就很耗时和浪费空间了 — 这是考虑算法的复杂度分析的时候的重要概念。虽然 Brute F orce 一个指针的解法可能会奏效，但时间复杂度一般会是 \$O(n^2)\$。在很多情况下，双指针能帮助我们找到空间或是时间复杂度更低的解。
识别使用双指针的招数：
一般来说，数组或是链表是排好序的，你得在里头找一些组合满足某种限制条件
这种组合可能是一对数，三个数，或是一个子数组
LeetCode 15. 三数之和 LeetCode - 15. 三数之和 给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0。请你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例 1：
输入：nums = [-1,0,1,2,-1,-4] 输出：[[-1,-1,2],[-1,0,1]] 解释： nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。 nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。 nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。 不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。 注意，输出的顺序和三元组的顺序并不重要。
在上一篇文章 算法模式：双指针 介绍了双指针模式。本篇文章，再介绍一种即可以用在数组，又可以用在链表中的算法模式：快慢指针。快慢指针，其实是双指针模式的一个变种。所以，两者在很多地方有相通之处。
快慢指针 快慢指针模式，有一个非常出名的名字，叫龟兔赛跑。大家肯定都知道龟兔赛跑啦。但还是再解释一下快慢指针：这种算法的两个指针的在数组上（或是链表上，序列上）的移动速度不一样。还别说，这种方法在解决有环的链表和数组时特别有用。
通过控制指针不同的移动速度（比如在环形链表上），这种算法证明了他们肯定会相遇的。快的一个指针肯定会追上慢的一个（可以想象成跑道上面跑得快的人套圈跑得慢的人）。
咋知道需要用快慢指针模式勒？
问题需要处理环上的问题，比如环形链表和环形数组
当你需要知道链表的长度或是某个特别位置的信息的时候
那啥时候用快慢指针而不是上面的双指针呢？
有些情形下，咱们不应该用双指针，比如我们在单链表上不能往回移动的时候。一个典型的需要用到快慢指针的模式的是当你需要去判断一个链表是否是回文的时候。
LeetCode 141. 环形链表 LeetCode - 141. 环形链表 给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。
示例 1：
输入：head = [3,2,0,-4], pos = 1 输出：true 解释：链表中有一个环，其尾部连接到第二个节点。 示例 2：
输入：head = [1,2], pos = 0 输出：true 解释：链表中有一个环，其尾部连接到第一个节点。 示例 3：
输入：head = [1], pos = -1 输出：false 解释：链表中没有环。
在上一篇文章 算法模式：改进的二分查找 介绍了二分查找以及相关变种。本篇文章，继续介绍数组相关的算法模式：区间合并。
区间合并 区间合并模式是一个用来处理有区间重叠的很高效的技术。在涉及到区间的很多问题中，通常咱们需要要么判断是否有重叠，要么合并区间，如果他们重叠的话。这个模式是这么起作用的。
给两个区间，一个是 a，另外一个是 b。别小看就两个区间，他们之间的关系能跑出来6种情况。详细的就看图啦。
图 1. 区间关系 观察这六种排序，明显后三种排序是前三种排序的一个“变种”：对区间根据起点和终点进行排序，就是剩下前三种排序了。再对其进行合并就很简单了：
没有重叠，则直接开启新区间。
有重叠，起点和终点分别取最大值和最小值即可：由于区间已经排序，则相邻两个区间的起点是前面区间的起点，重点则是两个区间终点的最大值。
LeetCode 56. 合并区间 LeetCode - 56. 合并区间 以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi]。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
示例 1：
输入：intervals = [[1,3],[2,6],[8,10],[15,18]] 输出：[[1,6],[8,10],[15,18]] 解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6]. 示例 2：
输入：intervals = [[1,4],[4,5]] 输出：[[1,5]] 解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。 提示：
1 <= intervals.length <= 104
intervals[i].length == 2
0 <= starti <= endi <= 104
