LeetCode题解及算法记录

2022-07-28 约 72586 字预计阅读 145 分钟 - 次阅读 - 条评论

这是个人平时刷力扣和学习数据结构的记录，仅供个人复习使用。另外由于部分复杂Latex语法不支持，因此显示上略有问题。

输入输出

起手

1

Scanner scanner = new Scanner(System.in)

nextInt()、nextLine() 的区别
- nextInt() 只会读取数值，剩下"\n"还没有读取，并将cursor放在本行中。
- nextLine()会读取"\n"，并结束
- 如果想要在 nextInt() 后读取一行，就得在 nextInt() 之后额外加上 scanner.nextLine()
对于读取一行用空格隔开的整数，可以采用

1
2
3
4
5
6

// n num
String[] snums = scanner.nextLine().split(" ")
int[] nums = new int[n]
for(int i = 0; i < n; i++){
    nums[i] = Integer.valueOf(snums[i]);
}

多行数字同理利用读取一行的方法

数组篇

二分-查找元素或索引

定义 nums 为升序数组, left , right , mid 分别为左、右边界和中点, target 为目标值, left 初始为 0 , right 初始为 nums.length - 1

是否有某数（数组元素无重复）（简单）

链接：题目链接
判断条件：left <= right
边界更新：比较 mid 与 target 的值, 从而 left = mid + 1 || right = mid - 1
返回值与条件：循环内判断相等返回

是否有某数,没有则找插入位置（数组元素无重复）（简单）

链接：题目链接
判断条件：left <= right
边界更新：根据 mid 的值与target的值相比, left = mid + 1 || right = mid - 1.
返回值与条件：循环内相等返回或循环外返回left
推理证明：如果能找到，那就和1一样；如果初始 left = right , 则 mid = left . 如果 mid > target, 那么 target 应当插在 mid 位置, 即 left ; 反之 target 应当插在 mid + 1 位置, 此时 left 恰好为 mid + 1. 而若初始 left != right , 那么在变成 left = right 前, 还会有 left = right - 1 这个情况, 这时 mid = left . 如果 mid < target, 那么 target 应当插在 mid + 1位置, 此时 left 恰好为 mid + 1 , 同时该情况退化为 left = right 的情况；反之 target 应当插在 mid 位置, 此时 left 恰好为 mid .

二分-旋转排序数组

旋转排序数组是指将原本有序的数组循环右移任意位后的数组

旋转后的排序数组查找（数组元素无重复）（中等）

链接：题目链接
解题思路：分类讨论即可，在普通二分 mid 不等于 target 时要先判断 mid 落在数组的哪一侧，然后再具体分析来更新 left 或 right 。

旋转后的排序数组查找（数组元素有重复）（中等）

链接：题目链接
边界更新：相比无重复情况，首先判断 left 和 mid 对应的值是否相等，若相等则 left++ , 目的是除去重复.

寻找旋转后的排序数组的最小值（数组元素无重复）（中等）

链接：题目链接
解题思路：实际还是找分界点；排除原数组为单元素或本身就是有序数组的情况，依次判断当前点是否是目标点（先判断 mid 和 mid + 1, 再判断 mid 和 mid - 1），而后比较 mid 和 0 的值，选取无序的一方，因为分界点在无序的一方。

寻找旋转后的排序数组的最小值（数组元素有重复）（困难）

链接：题目链接
解题思路：先排除单元素和本身就是严格有序数组的情况，注意这里不能包括非严格有序的情况，如[3, 1, 3]（这种情况并没有想到特别好的解决方案，因此只能放到后面去做）。而后传统二分，先解决两种特殊情况：left == mid 和 mid == right。二者分别对应重复无效数据，则通过while循环不断 left++ 和 right–，但要注意的是，左侧可能完全一样或右侧可能完全一样，因此 while 之后要判断是不是边界点；另外由于前面没有判断整个数组一样的情况，因此 left 那里判断下是否是该情况。这之后，就可以参考无重复的情况代码即可。

二分-山脉数组

山脉数组：一个先严格递增后严格递减的数组，元素数不少于3

山脉数组判断（简单）

链接：题目链接
解题思路：从两端分别向分界点处扫描即可，而后判断得到的两个分界点是否相同；但这里要注意避开严格单调递增或严格单调递减的情况。

山脉数组峰值索引（简单）

链接：题目链接
解题思路：还是二分的思想来加速（相比线性扫描），不过循环退出条件改为 left < right，同时边界更新是判断是否在递增区，若是则 left = mid + 1，反之 right = mid。最后返回 left 即可。

二维矩阵

顺时针打印矩阵（简单）

链接：题目链接
解题思路一：模拟矩阵，定义方向矩阵为向右（坐标变化值，如 {0, 1}、向下、向左、向上四个方向；然后定义一个方向矩阵索引坐标，每次用当前坐标叠加索引对应的方向变化（判断是否越界或数字已经打印，若有则索引循环加 1（指不能大于方向矩阵大小））即可。
变体：按顺时针序生成一个 1 -> n^2 的矩阵，方法同上

旋转矩阵（顺时针90度）（简单）

链接：题目链接
提示：顺时针90度等于先转置后左右对称
变体：顺时针180°（先左右再上下对称）、逆时针180度、逆时针90度（先左右对称再转置）

搜索二维有序矩阵（行有序且列有序，但下一行首未必大于上一行尾）（中等）

链接：题目链接
解题思路一：由于有序（递增），因此可以每行或每列二分搜索，具体搜索行或列应该看行和列那个小，时间复杂度O(min(row, col)log(max(row, col)))
解题思路二：由于有序，可以从左下或右上开始搜索（ **思考为什么不用左上或右 **）；以左下为例，比目标值大则往上（行索引减一），反之往右（列索引加一）。若找到则返回，越界则失败，时间复杂度仅(O(row + col))

搜索二维有序矩阵第 K 小元素（行有序且列有序，但下一行首未必大于上一行尾）（简单）

链接：题目链接
解题思路一：把二维矩阵变为一维矩阵而后排序，时间复杂度O(n^2 * logn)，还需要额外n^2的存储空间
解题思路二：因为每行且每列都有序，因此可以采用归并排序的思想，只不过这里要用堆的思想来优化下，时间复杂度O(klogn)，极端情况下 k = n^2。该方法尚未实现；
解题思路三：思考对于一个固定的值（其值介于该二维矩阵的值域内），那么比其大的数一定在其右下方，比其小的数一定在其左上方，毕竟有序么。那么如果统计比他小的数的数量，而后判断其是否和 K 相等，是不是就可以得到目标值呢，而且时间复杂度还很低（统计数O(n)，更新固定比较值O(logn)）？这里还有个问题，这样搜索后这个固定值不一定存在于二维矩阵中。因此，我们要这么更新边界：上边界为原数组最小值，下边界为原数组最大值；当上边界小于下边界时，计算原数组中比二者的中间值小的数，比较其与 K 的关系：若不小于 K ，则下边界等于中间值；反之上边界等于中间值加一。最后返回上边界。接下来证明一下这个数为什么一定存在于数组中。某次迭代，小于等于 mid 的数恰好是 K 个，但这不代表 mid == 第 K 小的数；因为，mid 可能大于第 K 小的数，但又不存在矩阵中；此次迭代后，right 的值大于第 K 小的数，但又不存在矩阵中。可以预见，在经历一定次数的迭代后，最终 left == 第 K 小的数，而 mid 的值域是 [left, right)。很显然，由于 mid >= left，所以小于等于 mid的数依然恰好是 K个，那么 right == mid，右边继续缩小。在后续的迭代中，left保持不变，right 一直减小，直到 right == left == 第 K 小的数。

滑动窗口

滑动窗口最大值（困难）

描述：给定一个数组和一个长度 k ，返回数组中每 k 个数的最大值构成的数组。
链接：题目链接
思路：
- 既然是长度 k，那自然想到滑动窗口，但怎么高效地获取最大值呢？遍历循环是可以的，但那样复杂度就是 $O(nk)$。那有没有更好的方法呢？答案是单调队列。
- 那是选递增还是递减呢？答案是递减，因为是求最大值，根据单调递增队列的定义，如果有一个比队尾小的数过来，就会导致队伍内比它大的数全部被弹出，而这显然不是我们想看到的。递减队列则相反，较大的数会被保留，队首则是最大的数。
- 总结一下，对于每个新入元素，先判断队首和当前元素索引差是否大于 k 来保证划窗，然后更新单调队列，最后判断当前元素索引是否大于 k - 1 来决定填充答案数组。

和至少为 K 的最短子数组（困难）

描述：给定一个数组 nums 和一个数 k，求该数组的子数组中和不小于 k 的子数组的最小长度，不存在则返回 -1。
链接：链接
思路：
- 这道题困难的点在于现在给定的数组中包含负数，导致原来使用的划窗法失去了二段性，比如这样的窗口（[6, -4, 17, 2], 20）。
- 考虑划窗计算窗口和的前缀和数组中的两个索引 i, j。如果 arr[i] > arr[j], i < j，那么如果后面有 arr[k] - arr[i] >= k，那么 arr[k] - arr[j] >= k 且后者对应数组显然更短。
- 因此我们可以对数组前缀和维护一个单调递增队列，而后在每次有新元素进来时比较和队首的差值：若比 k 大，则更新结果值并移除队首值（根据上面的证明）；

K 个不同整数的子数组（困难）

描述：给定一个数组 nums 和一个数 k，求该数组中所有恰好包含 k 个不同元素的子数组的个数
链接：链接
思路：恰好 k 个的数量 = 最多 k 个的数量 - 最多 k - 1 的数量（思路清奇有没有）。而对于恰好 k 个的数量，可以轻松用划窗做。简单证明下二段性：假设当前窗口满足元素种类为 k，而加上被扔掉的左边则会增加元素种类。那么对于向右延伸的窗口，添加被扔弃的左边自然也会增加元素种类，所以左边会被永久扔弃。

最小区间（困难）

描述：给定 k 个非递减数组，求一个最小区间[a, b]，使得 k 个数组中都至少有 1 个数出现在该区间中。其中最小区间是指：对于区间 [a, b] 和 [c, d]，如果 d - c < b - a 或 d - c = b - a && c < a，则区间 [c, d] 比 [a, b] 更小。
链接：链接
解法一：首先将所有数组中的元素复制到一个新的数组 all 中，且该数组中的每个元素为一个新的类型 Pair，表明了它的值 Pair.num 和来自那个原数组 Pair.idx。那么如果该新数组在 num 维度上递增有序，原问题就可以转化为：对于一个数组，找到一个最短子数组，使得子数组中不同元素来源的种类为 k（原本总共就只有 k 类）。这样就变成了一道简单的划窗问题了。
解法二：原问题可以转化为：从 k 个数组中各取一个数构造一个数组 temp，求这些数组最大值与最小值构成的区间中的最小区间。因为这个数组 temp 是固定长度的，所以我们只需要一种数据结构能快速知道其区间最大和最小值，这里选用堆这个结构。同时因为原来的 k 个数组都是递增的，因此选用小顶堆。而后每次先更新最小区间，然后移除最小的元素，并将它对应数组的下一个元素加入堆中，并更新最大值。如果下一个元素不存在，自然就不再存在下一个最小区间，可以直接结束遍历，返回答案。

滑动窗口中位数（困难）

链接：链接
思路：暴力的方法就是每次复制滑动窗口的值到对应数组，然后排序，然后得到中位数。该题目超过时间限制。
优化思路一（二分 + 排序）：因为每次要更新滑动窗口数组前，滑动窗口都是有序的。故而不用重新复制滑动窗口值，而是可以二分查找要替换的值的位置，然后更新该位置的值就可以了。这样相对更快，本题能过。另外可以不排序新的滑动窗口数组，而是查找可以插入的位置，然后依次右移对应元素，这样比排序是要快。
优化思路二：因为每次都要重新对滑动窗口对应部分重排，故而是否可以采用一个内部有序的结构来加快排序部分？Java 自带可用的数据结构有 TreeMap 或 PriorQueue，这两个需要自己实现中位数功能。或者可以自己手撕二叉搜索树并实现快速求中位值。

满足不等式的最大值（困难）

链接：链接
描述：给定一个二维数组，其第二维代表 x, y，且该数组沿 x 方向递增排列。给定一个数 k，求 $max(y_i + y_j + |x_i - x_j|);s.t. \ x_i < x_j;x_j - x_i <= k$
分析：力扣这标签标的也太奇怪了。首先对于给定表达式，可以更改为$max(y_i + y_j + x_j - x_i) \to max(x_j + y_j) + max(y_i - x_i)$。可以看到更改后，前项因为k 的限制必然会划窗遍历，所以只要遍历即可；而后项这个表达式，很显然就可以用单调递减队列维护即可，故而原题目即有解。

跳跃游戏 VI（中等）

链接：链接
描述：给定一个数组nums和一个整数k，你初始在索引0的位置，每次你最多可以往前跳跃k步（但不能超出数组最大索引），每次跳到一个索引处，你都会得到一个分数，它等于nums在索引处的值（初始点也算），求跳到最大索引处时你能得到的最大分数。
思路：看到这个问题下意识就会想到用动态规划，转移方程也很简单，如下：
$$dp[i] = max(dp[i-k],…,dp[i-1]) + nums[i] \ (1)$$
但这道题会超时，所以要优化。反过来想想，对于dp[i]，我们可以用它来更新dp[i+1],...,dp[i+k]。那么对于i<j<k，如果dp[i]<=dp[j]，那么其实在(1)方程中，我们计算dp[k]时明显不需要考虑dp[i]而只需要关心dp[j]即可。因此我们可以利用dp[i]顺向更新dp[i+1],...,dp[i+k]，并在dp[i+t] >= dp[i]时直接结束当前更新循环即可。

至少有 K 个重复字符的最长子串（中等）

链接：链接
描述：给定一个字符串s和一个整数k，找到一个最长子串，且该子串中所有字符出现的次数都不少于k次。
思路：
- 看到这个问题，首先想的是有没有一个数据结构可以实时记录当前子串中各个字符的个数，然后双重for循环即可解决问题。基于这个思路，可以构造(n + 1) * 26的cnt数组，然后循环，结果打败 5%，直接放弃好吧，虽然从数据量来说就应该这样。
- 再换个角度，是否可以用二分来解决问题呢？显然这道题是不行的，因为没有二段性质。
  - [二段性质]：假设有长度 t 的一段区间满足要求的话，t + 1 长度的区间是否「一定满足」或者「一定不满足」呢？
  显然这道题的结果取决于长度t区间的字符种类和t + 1处字符的种类。因此我们无法是使用「二分」，相应的也无法直接使用「滑动窗口」思路的双指针。
  因为双指针其实也是利用了二段性质，当一个指针确定在某个位置，另外一个指针能够落在某个明确的分割点，使得左半部分满足，右半部分不满足。
  那么还有什么性质可以利用呢？这时候要留意数据范围「数值小」的内容。
  题目说明了只包含小写字母（26 个，为有限数据），我们可以枚举最大长度所包含的字符类型数量，答案必然是 [1, 26]，即最少包含 1 个字母，最多包含 26 个字母。
  你会发现，当确定了长度所包含的字符种类数量时，区间重新具有了二段性质。
  当我们使用双指针的时候：
  右端点往右移动必然会导致字符类型数量增加（或不变）左端点往右移动必然会导致字符类型数量减少（或不变）当然，我们还需要记录有多少字符符合要求（出现次数不少于 k），当区间内所有字符都符合时更新答案。
启发：当我们采用常规的分析思路发现无法进行时，要去关注一下数据范围中「数值小」的值。因为数值小其实是代表了「可枚举」，往往是解题或者降低复杂度的一个重要（甚至是唯一）的突破口。

子序列或子数组

递增子序列（中等）

链接：链接
描述：给定一个数组，返回所有的递增子序列
解法：就是回溯么，关键是如何剪枝来去重

最长递增子序列（中等）

链接：链接
解法一（动态规划）：关键状态变量选好。设 dp[i] 代表选择 nums[i] 情况下的最长子序列长度，那么有 $dp[i] = max(dp[j]) + 1$ where $\text{j < i & nums[j] < nums[i]}$。最后对 dp 所有值取 max即可。
解法二（贪心 + 二分查找）：考虑一个简单的贪心，如果要让递增子序列尽可能的长，那么就要让子序列上升的尽可能的慢，因此希望每次加在末尾的那个数尽量的小。那么我们可以定义一个数组 d[i] 来表示一定长度 i 下末尾元素的最小值。可以证明该数组是关于数组长度 i 单调递增的。那么我们的遍历过程就变成这样的：
- d[1] = nums[0]，len = 1
- 对于 nums[i]，如果 nums[i] > d[len]，那么 d[len + 1] = nums[i], len++
- 反之，在 d[i] 中二分查找 max(d[k] < nums[i])，并 d[k + 1] = nums[i]
变体（中等）: 链接现在改为求最大。在解法上其实多了一个数量数组的 dp。在之前比较的情况中，我们可以区分 dp[j] + 1 和 dp[i] 的大小关系来更新数量数组 count。如果二者相等，那么说明最长子序列长度不变但数量增加，因此 count[i] 要加上 count[j]；反之则说明最长子序列更新了，故而 count[i] = count[j]。

最大子数组和（简单）

链接：链接
描述：给定一个数组，求其最大连续子数组和。
解法（动态规划）：定义状态变量 dp[i] 代表包含 nums[i] 的最大子数组和，那么 dp[i] = max(dp[i - 1] + nums[i], nums[i])，然后取 max(dp[i]) 即可。
解法（分治法）：归并么
提升：输出具体的最大子数组。分治法天然能得到，动态规划的话其实也行吧，就构造么。

长度最小的子数组（中等）

链接：链接
描述：给定一个数组和一个目标值 target，求所有满足和不小于 target 的子数组的最小长度。
解法：连续子数组么，就滑动窗口

最短无序连续子数组（中等）

链接：链接
描述：给定一个子数组，找出其最短的无序连续子数组。最短是指对这个子数组进行排序后，整个子数组都将变为有序的。返回该子数组的长度。
解法一：先排序，然后依次找左右有序边界即可。
解法二：其实和解法一思想类似，先找出最小和最大值。然后找出左右边界，使得左边界往左均小于最小值，右边界往右均大于最大值，最后相减得到区间长度即可。

最长重复子数组（中等）

链接：链接
描述：给定两个数组，求出两个子数组的最长公共子数组的长度
解法一（动态规划）：设状态变量 dp[i, j] 代表 nums1[i :] 和 nums2[j :] 的最长公共前缀，那么容易得到状态转移方程。另外根据这个转移方程可知需要倒序遍历。

$$ dp[i][j] = \begin{cases} dp[i + 1][j + 1] + 1 & \text{nums1[i] = nums2[j]} \ 0 & \text{otherwise} \end{cases} $$

解法二（滑动窗口）：原来划窗是划二个数组起始位置相对另一个数组起始位置啊，然后 for 循环遍历，懂了懂了。注意滑动是两个数组都要划一遍，即第一个不动，第二个右滑和第二个不动和第一个右滑。
解法三（二分查找 + 哈希）：先不看了

子数组的最小值之和（中等）

链接：链接
描述：给定一个整数数组 nums ，求 $\sum {min(b)}$，其中 b 是 nums 的任意连续子数组。
解法一：暴力 for 循环，$O(n^2)$ 超时

解法二：单调栈。如果要快，实质上是要找到对于当前数，以当前数为最小值的子数组个数。这里选择使用一个单调递增栈，然后这样计算：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

  int res = 0, tmp = 0, count = 1
  for num in nums
      count = 1
      while !stack.isEmpty() && stack.peek().val >= num
          Pair top = stack.pop()
          count += top.count
          tmp -= top.val * top.count
      tmp += num * count
      res = (res + tmp) % 1000000007
      stack.push(new Pair(num, pair))

解释下为何能这样，count 代表栈中（包括当前元素）不大于当前元素的元素的数量：
- 对于一个递增数组，stack 中的每个元素 Pair 的 count 都为 1。那么他们的子数组的最小和应当是这样叠加计算：$target = \sum_{i = 1}^{n} {nums[i] * (n - i - 1)}$ ，这个就解释了为什么上述代码中 tmp 是不断累加 $nums[i] * count$。举个例子：[1, 2, 3] = 1(1) + [1(1, 2) + 2(2)] + [1(1, 2, 3) + 2(2, 3) + 3 (3) ]
- 而当有一个比栈顶元素小的元素 nums[j] 过来值，新增加的所有子数组应当是以 nums[j] 打头直到栈底的所有连续子数组。对于这些子数组的最小值，显然以 nums[j] 为最小值的子数组的数量即 $count_j$ 应当是 $1 + count_i$ $where$ $nums[i] >= nums[j]$ ，而剩下包含栈底剩余元素的子数组的最小值 $tmp_{new} = tmp - count_i * nums[i]$ $where$ $nums[i] >= nums[j]$ 。所以所有包含该元素的子数组的最小值的和是 $tmp_{new} + count_j * nums[j]$。

乘积最大子数组（中等）

链接：链接
描述：给定一个数组，求其所有连续子数组中乘积最大的乘积值
解法：粗想就是设 dp[i] 代表包含 nums[i] 的最大乘积，那么 dp[i + 1] = max(dp[i] * nums[i], nums[i])。但这是错误，因为原数组里可能包含负数，如 [-2, 3, -4]，负负得正就不对。因此可以设状态变量 dp[i, j]，dp[i, 0] 和 dp[i, 1] 分别包含 nums[i] 的最大和最小乘积，然后更新时同时考虑最大最小即可。

连续的子数组和（中等）

链接：链接
描述：给定一个正整数数组 nums 和一个目标值 k，求数组中是否存在长度不小于 2 且和为 k 的倍数的连续子数组。
分析：
- 看到这道题想到前缀和是很简单的，然后两个 for 循环一套，发现本题会超时。
- 然后根据典型的空间换时间想法，我是想到了用一个哈希表存储余数的，但之后就没下文了。但根据同余定理，那其实可以用有序的 Map 来存储余数作为 value，同时用下标当做 key。证明可以参照同余定理的定理一。
同余定理：
- 定义：对于三个正整数 a 和 b 和 m，如果 a % m = b % m，则称 a, b 对模 m 同余，记做 a = b % m。
- 定理一：正整数 a 和 b 对模 m 同余的充要条件是 a - b 能被 m 整除，即 m | a - b。
- 定理二：同余关系具有自反性、对称性和传递性。
- 定理三：若 a = b % m, c = d % m, 则 a + / - / * c = b + / - / * d % m；
- 定理四：若 ca = cb % m，gcd(c, m) = d, 则 a = b % (m / d)。gcd(c, m) 表示二者的最大公约数。
- 定理五：若 a = b % m, 则 $a^n = b^n % m$ 。

连续数组（中等）

链接：链接
描述：给定一个只包含 0 和 1 的数组，求一个最长连续子数组，其中 1 和 0 的数量相同，返回它的长度。
解法：哭了还是没做出来。方法还是前缀和 + 哈希表。哈希表记录 bal - 索引键值对就可。同样利用哈希表查找是否先前有同样的 bal，有则获得长度并更新最大长度。由于我们只在哈希表中不存在对应 bal 时放入该键值对（这样确保获得的确实是最长的），所以得到的一定是最长的。

最长连续序列（中等）

链接：链接
描述：给定一个数组 nums，求其数字连续的最长序列（无论其元素在数组中的位置关系如何）的长度。如 [4, 1, 2, 3, 5, 5, 6] 的连续最长序列应该是[1, 2, 3, 4, 5, 6]
分析：下面只讨论时间复杂度为 O(n) 的方法，sort 的方法再见（虽然计数排序等是 O(n)，但 $10^9$ 的数组元素范围给劝退了。
- 按照大佬的思路，一般力扣中对时间有要求的都可以用空间来换（什么歪理），那就定义个 Set 来保存原数组的元素（正好还去重了）。
- 然后一个重要的一点是判定最长序列的起始点 X。简单来说，如果 Set 里包含 X，那么当前 X 肯定不是起始点，这个很容易推出，因此我们就最只需要找到一个合适的 X 后往前推进就好了。不过感觉这时间复杂度也不只 O(n) 吧。

子数组按位或操作（中等）

链接：链接
描述：给定一个数组，返回其所有连续子数组中或值不同的个数。
分析：
- 上来我就是一个动态规划 + 哈希表，这不简单的事么，$O(n^2)$ 的时间复杂度竟然超时了，一看长度 5000，还真是回事。
- 然后分析下，其实有些步骤可以不用整的。以正序遍历为例，两重 for 循环量分别为 i 和 j，状态变量 dp[j] 是对应区间 [j, i] 的或值。由于或运算只会越或越大，故而当 dp[j] | dp[i] = dp[j] 时（因为我们用一维数组记录，所以剩下的必然是大的数），说明后续叠加不会让或值有变换，因而可以提前终止，这样就能过了。

摩尔投票法

多数元素/众数（简单、中等）

链接：链接
描述：给定一个数组 nums ，找出数组中出现次数大于 $\lfloor len_{num} / 2 \rfloor$ 的那个数。数组中有且仅有一个多数元素。
解法一： HashMap 么，懂得都懂
解法二：排序后取索引 $\lfloor len_{num} / 2 \rfloor$ 的数
解法三（位运算）：不断判断 32 位中当前位应该取 1 或 0，然后构造解。
解法四（摩尔投票法）：核心就是对拼消耗。因为有且仅有一个多数元素，那么我们维持两个变量 candidate 和 count，其中前者代表目标值，后者代表与目标值相同的数，初始时前者随机，后者取 0。然后遍历数组，遇到和 candidate 不同的就 count - 1，反之加一；但若 count = 0，则更新 candidate为当前值。因为多数元素仅有一个，而它数量最多，所以最后剩下的一定是它。
解法五（随机算法）：每次随机选一个竟然都有 O(n) 的时间复杂度，牛皮
解法六（分治算法）：没啥好写的，就那样么
变体（简单）：链接现在数组中不一定存在主要元素，继续求多数元素，不存在则返回 -1。下面只讨论O(n) 时间复杂度，O(1) 空间复杂度的做法。
- 改进的摩尔投票法：因为不一定存在多数元素，因此这里要对 candidate 进行验证。如果 count > 1 显然结果是对的；反之再置零 count 判断数组中 candidate 的数量即可。
变体（中等）：链接这次是找出所有出现次数大于 $\lfloor n / 3 \rfloor$ 的数的集合。下面只讨论O(n) 时间复杂度，O(1) 空间复杂度的做法。
- 改进的摩尔投票法：容易得知，出现次数大于该数组长度 1 / 3 的值最多只有 2 个。那么我们定义两个 candidate 和 count 就好了。然后更新时应当按照以下规则：
  - 如果某个 candidate 的 count 为 0，在 num 不等于其他 count 不为零的 candidate 情况下赋值给这个 candidate，并且 count 置 1
  - 反之比较两个 candidate，如果有一个与当前 num 相同，则对应 candidate 的 count 加一；若一个都不相等，则两个 candidate 的 count 都减一。
  - 最后因为不一定存在众数，同样需要再遍历一遍数组来判断是否为真的众数。

排序算法篇

排序算法理论学习

简单选择排序（了解）

算法思路：每次选取数组中最小数的索引，不断扩大数组头的有序数组
参考代码：selectSort
特点：交换次数最少，在交换成本较高时可以考虑采用

插入排序（了解）

算法思路：在数组头维持一个有序数组，每次将未排序数插入该有序数组
参考代码：insertSort
特点：「插入排序」可以提前终止内层循环，（体现在nums[j - 1] > temp不满足时），在数组「几乎有序」的前提下，「插入排序」的时间复杂度可以达到O(N)；由于「插入排序」在「几乎有序」的数组上表现良好，特别地，在「短数组」上的表现也很好，因为「短数组」的特点是：每个元素离它最终排序的位置都不会太远；

冒泡排序（了解）

算法思路：设定一个有序方式，从0开始，依次交换不符合该有序方式的一堆数；如果指定升序，那么最大的数会依次被排到最后；
参考代码：bubbleSort
特点：在遍历的时候，如果提前检测到数组是有序的，就可以提前结束排序；而「选择排序」依然需要走完全部流程。

归并排序（重点）

算法思路：分半后依次排序，然后合并
参考代码：mergeSort
优化一：对于「小区间」可以转而使用「插入排序」，JDK 源码中也有类似操作；「小区间」的长度是一个超参数；
优化二：当两个数组本身就是有序关系时，不需要排序；
优化三：可以全程使用一个和原数组等长的「临时数组」来避免创建、销毁临时数组，只是计算时要注意下标；

快速排序（重点）

算法思路：选定一个 pivot，然后两侧同时循环，将左侧比它大的填到右侧，右侧比它小的放到左侧
优化零：分割时可以采用双向扫描，即 Hoare 的提出的双向扫描法；双向扫描用两个标志 i 、j，分别初始化成数组的两端。主循环里嵌套两个内循环：第一个内循环 i 从左向右移过小于枢纽元的元素，遇到大元素时停止；第二个循环 j 从右向左移过大于枢纽元的元素，遇到小元素时停止。然后主循环检查 i、j 是否相交并交换 A[i]、A[j]。优化有序数组情况
优化一（不重要）：pivot 不采用固定的，如最后一个或第一个数，而是采用随机一个；这样尽管不会对时间和空间复杂度有所改善，但能减少出现最坏情况的概率（原数组已经有序）；对重复数组优化不大
优化二：三数取中。即取三个元素进行排序，然后交换中间值和左端值，并取交换后的中间值作为 pivot。三个元素一般是取待排序数组的左端、右端和中间三个数，也可以随机选取；对重复数组优化不大
优化三：当待排序数组长度小于一定长度（例如 JDK 源码中的 7）后，采用插入排序。对重复数组优化不大
优化四：在分割时考虑将和选定的 pivot 放在一起。具体来说，定义两个边界 p 和 q，使得 p - q 之间均为相等的数，p 左边为较小的一堆， q右边为较大的一堆（升序排列时）。实现时可以仅比较 nums[i] > pivot 和 nums[i] == pivot 的情况来实现。对重复数组优化较大
优化五（不重要）：采用递归实现时，为了避免左右两侧数的数量不均，可以改为尾递归，每次仅先递归元素较多的一部分，这样剩下的一部分的元素量一定不大于原数组元素量的一半；其实这种优化编译器会自己优化
参考代码：quickSort

希尔排序（了解）

基本思想：按照不同部长对元素进行排序。

计数排序

基本假设：假设 n 个输入元素中的每一个都是在 0 到 k 区间内（对于小于 0 的可以加上偏置来使得它不小于 0）的整数，其中 k 为某个整数。当 k = O(n) 时，排序的运行时间为 O(n)（这里的 O 指代带横杠的那个）。
基本思想：对每个输入元素 x，确定小于 x 的元素个数。利用这信息，就可以直接把 x 放在它在输出数组中的位置上。每次放了之后，把小于 x 的元素个数减一。时间复杂度 O(n)，空间复杂度可能较大，因为无法预估数组元素的大小范围。
参考代码：countSort

基数排序

基本思路：也称基于关键字的排序。比如对十进制数的排序，从低位到高位依次进行「计数排序」。排序时「低位优先」。相比计数排序，主要优化了在输入元素跨度过大时空间复杂度过大的问题。举个例子，以 10 进制为例，最多需要的空间就是 10，因为 10 进制只有 10 个数字。

桶排序（了解）

基本思想：假设输入数据服从均匀分布，平均情况下时间复杂度为 O(n)。它假设输入是由一个随机过程产生，该过程将元素均匀地分布在 [0, 1) 区间上。因此桶排序将 [0, 1) 区间划分为 n 个相同大小的子区间，或称为桶；而后将 n 个输入数分别放在各个桶中。为了得到输出结果，首先对每个桶中的数进行排序，然后遍历每个桶，按照次序把每个桶中的元素取出即可。

小总结

任何比较排序的算法在最坏情况下的比较次数要有Ω(nlgn)。
稳定排序：相同值的元素在输出数组中的相对次序与在输入数组中的相对次数一致；选择排序、快速排序、希尔排序、堆排序是不稳定的排序算法，冒泡排序、插入排序、归并排序、基数排序、计数排序是稳定的排序算法。
原址排序：基本上不需要额外的辅助空间，允许少量额外的辅助变量进行的排序。

排序算法实战

计算数组的逆序数（困难）

描述：逆序对是指对于数组中的两个不同的数 A[i] 和 A[j]，有 i < j 和 A[i] > A[j]
链接：题目链接
解题思路：仔细思考下，数组中逆序对的数量和对数组进行「插入排序」时所移动的数量，二者是不是相等的？因此，我们可以将求逆序对数量的问题转化为求「插入排序」移动数量的问题；但是插入排序太慢了，我们可以进而采用分治的方法优化它
参考代码：countInversion

动态规划篇

最长递增子序列的长度

描述：给定一个数组 nums，求其最长严格单调递增子序列的长度 LIS 。
分析：
- 朴素的思维是 $O(n^2)$ 的动态规划，设 dp[i] 代表截止索引 i 为止的最长子序列长度，则
  $\ \ \ \ dp[i] = \mathop{max} \limits_{0 <= j < i;\ nums[i] > nums[j]} (dp[j] + 1, dp[i]); \ \ \ LIS = \mathop{max} \limits_{0 <= i < len_{dp}} dp[i]$
- 但如果换个思路，设 dp[i] 代表截止长度为 i 的最长递增子序列最后一位的最小值，那么我们可以遍历所有元素，然后二分查找比当前小的索引 j , 再将 dp[j + 1] 设为当前元素。当然这样需要初始化除了 dp[0] 为某一不可能取到的值如 Integer.MAX_VALUE，然后最大长度即为第一个非默认值的索引。这样时间复杂度即为 $O(nlgn)$。

最长递增子序列的个数（中等）

链接：链接
描述：现在要求求给定数组的最长递增子序列的个数，因为可能不只一个。
分析：
- 依旧是套上面的思路，对于朴素的思路，我们可以额外定义一个 count 数组，count[i] 表示长度为 dp[i] 的递增子序列的个数，那么可以如下方法更新 count[i] ，并维护一个 LIS 变量表示最长递增子序列的长度，从而得到最终答案；
$$ nums[i] > nums[j] \to \begin{cases} count[i] = count[j] & dp[i] < dp[j] + 1 \ count[i] += count[j] & dp[i] = dp[j] + 1 \end{cases} \ len_{LIS} = \sum_{i = 0}^{len_{dp}} count[i] \ (if \ dp[i] = LIS) $$
- 然后是 $O(nlgn)$ 的解法——线段树。

得到子序列的最少操作次数（困难）

链接：链接
描述：给定两个数组 target 和 source，你可以对 source 进行任意次增加操作使得 target 变成 source的一个子序列，求进行操作的最少次数。增加操作是指在 source 的任意位置中添加任意一个数字。另外，target 数组中无重复元素。
分析：
- 首先可以看出这是一个求最长公共子序列的问题，然后想到 $O(n^2)$ 的动态规划。但数据量最大是 $10^5$ 故而放弃。
- 而后注意到 target 无重复元素，因此可以将 source 中包含的 target 元素提取出来并以下标表示构造数组，记做 nums
- 那么现在这个问题就变成求 nums 的最长递增子序列问题，可以用 $O(nlgn)$ 的做法解决它。

打家劫舍问题

你是一个小偷，来到一片 XX 形状的房屋群 nums，每个房屋中有着不同数额的金钱 nums[i]，你不能连着偷两家有相连关系的房间（具体看题目定义），问你能偷到的最大金额？

基础篇（中等）

链接：题目链接
描述：每两家是相连的，偷了前一家就不能偷下一家
思路：$dp[i]$ 表示偷第 i 家情况下前 i 家能偷到的最大金额
状态转移方程：$dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])$

进阶 1 ：环（中等）

链接：题目链接
描述：现在最后一家和第一家也连在一起了
思路：既然最后一家和第一家连在一起，不如先分别偷第 1 - n-1 和第 2 - n 家，比较两次偷到的最大金额，按最大的金额偷就好了，这样也可以避免同时偷第一家和最后一家的尴尬。

进阶 2 ：二叉树（中等）

链接：题目链接
描述：你又来到了一片新的区域，聪明的你发现这片房屋像是一颗二叉树（吐），而这里同样不能偷两间直接相联的房子。注意偷并不需要按照二叉树路径去偷
思路：定义这样两个函数 f(o), g(o), 其中 f(o) 表示偷了 o 房屋的最大收益，g(o) 表示没偷 o 房屋的最大收益，那么不难想到 f(o) 和 g(o) 的状态方程为：

$$ \begin{cases} f(o) = nums[o] + g(o.left) + g(o.right) \ g(o) = max(f(o.left), g(o.left)) + max(f(o.right), g(o.right)) \end{cases} $$

因此我们可以设置两个 HashMap 保存 f 和 g，然后深度优先遍历 root 房屋即可。

数位 dp 问题

2 的出现次数（困难）

链接：题目链接
描述：给定一个数 N，统计 0 - N 范围内 2 的出现个数。注意，22 应当视作 2 出现 2 次，其余类推。这个次数设定为 numsOf2(N)。$N_i$代表 N 倒数 i 位数构成的数，类似的$N_{i\to{j}}$代表 N 倒数 i 到 j 位数构成的数。
思路：还是找规律，不过思路要转个弯。我们可以依次统计N 这个数的各个位数上出现 2 的个数而不是直接递推。假设 N 有 n 位，第 n 位为 k ，则 0 - N 范围内 2 的个数可以表示为：
- ① $k\in[0, k-1]$, 后 n - 1位上出现 2 的次数，即$k\cdot numsOf2(9…9(n-1)) $。因为当 $k\in[0, k-1]$时，后 n - 1位总是可以取全 0 到全 9 范围内的所有数字。
- ② 当第 n 位取 k 时，后 n - 1 位上出现 2 的次数，即 $numsOf2(N_{0\to n-1})$。因为后 n - 1 位不一定能到全部都是 9 。
- ③当第 n 位取 $[1, k]$ 时，第 n 位上出现 2 的次数，即

$$ numsOf2(N_n) = \begin{cases} 10^{n - 1} & \text{k > 2} \ numsOf2(N_{0\to n-1}) + 1 & \text{k == 2} \ 0 & \text{0 < k < 2} \end{cases} $$

因为当 k 小于 2 时，第 n 位不可能出现 2；当 k = 2 时，第 n 位为 2 的次数就是后面 n - 1 位数构成的数到 0 的数目，即 $numsOf2(N_{0 \to n-1})+1$ ；而当 k > 2时，因为后面 n - 1 位最大可以到 n - 1 个 9，因此不用按等于 2 的方法算而是直接算出个数就好了，也就是 $10^{n - 1}$。
这样一来所有 n 位上出现 2 的次数都被统计过了，也就算出了 0 - N 范围内 2 的出现个数。但是注意到我们的递归公式还包含后 n - 1 位全是 9 的情况的个数，而这个同样可以用上面的方法来递推，因此我们可以设置一个二维 dp 数组，前一个统计前 i 位包含 2 的个数，后一个统计前 i 位全为 9 时包含 2 的个数，最终得到递归公式如下如下。最后我们返回 $dp[n][0] $即可。

$$ \begin{cases} digit = log10(N) + 1(exp:100\to{3}) \ dp \to{int[n + 1][2]} \ dp[1][0]=N %10 >= 2 ? 1 : 0; dp[1][1] = 1; \end{cases} $$

$$ dp[i][j] = \begin{cases} k * dp[i - 1][1] + dp[i - 1][0] + 10^{i - 1} & \text{k > 2 & j = 0} \ k * dp[i - 1][1] + dp [i-1] [0] + N% 10^{i - 1} + 1 & \text{k = 2 & j = 0} \ k * dp[i-1][1] + dp [i-1] [0] & \text{0 < k < 2 & j = 0} \ 10 * {dp[i - 1][1]} + 10^{i - 1} & \text{j = 1} \end{cases} \text{for i = 2 to n; } k = (n / 10^{i - 1}) % 10 $$

i 的出现个数（困难）

链接：自己想的变体
描述：类比 2 的出现个数，我们现在要计算 0 到 N 范围内 i 的出现个数，其中 i 可以是 0 到 9 中的任何一个数。
思路：仿照 2 的出现个数的方法，我们完全可以更改 k 的条件范围（如原本以 2 为边界分为三种情况）即可适应所有 i 的可能值。

最大为 N 的数字组合（困难）

链接：题目链接
描述：给定一个字符串数组 S ，其中元素的值仅在 1 - 9 之间无重复，如{‘1’, ‘2’, ‘9’}；输入一个数 N，你可以任意重复使用 S 中的元素来组成一个数，求这些数中小于 N 的个数。假设 N 的位数为 n。
思路：就按照普通思考就可。设 N 的第 i 位为 k，除去小于 n 位的那些数，如果 k 大于 $S_i$，你还可以构造$len(S)^{i - 1}$个比 N 小的 i 位数；若 k 等于$S_i$，则还能构造的数量等于 i - 1 位除去小于 i - 1 的数时能够造的数的数量。
状态转移方程：设 dp[i] 表示构造的 i 位数中小于 N 的后 i 位的数的数量，则状态方程如下。最后只要在返回前叠加上位数小于 n 的那些数的数量$\sum_{i = 1}^{n - 1} {len(S)^i}$就够了。需要注意的是题目要求的是所有不大于 N 的个数，而 dp[i] 最大只代表长度和 N 相等长度的部分，所有最终答案应该要加上前面几位取零即位数小于 N 的部分。

$$ dp[i] = \begin{cases} dp[i - 1] & \text{k = S[i]} \ len(S)^{i - 1} & \text{k > S[i]} \end{cases} for \ i \ in \ [0, len(S) - 1] \ result = dp[len(N)] + len(S)^{len(N) - k} \text{ for k in 0 to len(N) - 1} $$

不含连续 1 的非负整数（困难）

链接：链接
描述：给定一个正整数，求出 [0, n] 范围内二进制表示中不存在连续 1 的数的个数。
分析：这是一道典型的数位 DP 题目，对于这种题，通常是从高位到低位的分情况讨论。不失一般性的考虑数值 n 的某一位 cur 是如何被处理的：
- 如果当前位为 1，由于需要满足不大于 n，所以如果该位填 0 的话，后面低位填什么都满足要求。因此我们期望能够查出 长度为 i + 1, 且二进制位置 i 的数值为 0 时有多少合法数值，并将其累加到答案中；相反，如果当前位填 1，则需要保证非连续性，因此需要记录上一位 prev。
- 如果当前位 cur = 0，我们只能选 0，并决策下一位。
- 当出现当前位无法填入 cur 或者决策到最低位时，则完成了所有合法答案的统计（实际上是保证前 i 位选择 n 自身东西情况下，后面 j 位有多少种可能的选择）
而对于上面所说的查表，我们可以定义数组 f(i, j) 表示二进制长度为 i，最高位不超过 j 的合法数的个数。不失一般性地考虑 f(i, 0) 和 f(i, 1) 可以更新的状态：
- 如果 j = 0，则只能在 f(i - 1, 1) 的前面加 0，因为 f(i - 1, 1) 包含了 f(i - 1, 0) 的部分，所以有 f(i, 0) = f(i - 1, 1)
- 如果 j = 1，则可以在 f(i - 1, 0) 前面加 1 或 f(i - 1, 1) 前面加 0，所以有 f(i, 1) = f(i - 1, 0) + f(i - 1, 1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

int[][] f = new int[40][2]; // 比 32 大防止溢出即可
f[1] = new int[]{1, 2}; // 0 | 1, 0
for(int i = 2; i < 40; i++){
    f[i][0] = f[i - 1][0];
    f[i][1] = f[i - 1][0] + f[i - 1][1];
}

int len = 0, m = n;
while(m > 0){
    len++;
    m >>= 1;
}

int prev = 0, ans = 0;
// 从最高位开始
for(int i = len - 1; i >= 0; i--){
    int cur = (n >> i) & 1;
    if(cur == 1){
        // 当前位填 0 的合格数的数量
        ans += f[i + 1][0];
        if(prev == cur){
            break;
        }
    }
    prev = cur;
    if(i == 0){
        ans++;
    }
}

股票系列

给定一个数组 prices 代表股票每天的价格，然后按照一定条件买入卖出。求你可以获得的最多利润 maxProfit

买卖股票的最佳时机 1（简单）

链接：题目链接
描述：最多一笔交易；不能当天买当天卖；只能同时持有一股；
思路：拿一个变量 minPrice 记录先前的最低价格，maxProfit 记录当天卖出股票所能的获利，然后遍历循环即可

买卖股票的最佳时机 2（简单、中等）

链接：题目链接
描述：可以进行多笔交易；不能当天买当天卖；只能同时持有一股；
思路：定义二维 dp 数组，$dp[i][0]$ 表示当天持有股票时的收益，$dp[i][1]$ 表示当天不持有股票的收益。那么状态转移方程如下。另外，由于后一天仅依赖于前一天，其实还可以进一步压缩状态。

$$ \begin{cases} dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]) \ dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i]) \end{cases} $$

变体（中等）：链接：题目链接；每笔交易要收手续费 fee（买入和卖出为一笔交易）；解决方法很简答，在 $dp[i][1]$ 后面那项加上$prices[i]$ 后面减去 fee 即可，但是不能在买入的时候减去；
变体（中等）：链接：题目链接；卖掉一次股票后要休息一天才能买；定义状态转移数组$dp[天数][当前是否持股][当天是否卖出股票]$，则状态转移方程为如下，最后返回 $max(dp[n][0][0], dp[n][0][1])$即可。另外从状态方程中可以看见第 4 个变量并没啥用，同时当天变量仅依赖于前一天变量，故而可以进一步压缩状态，但可读性会下降。

$$ dp[0] = [0, -\infty, -prices[0], -\infty] $$

$$ dp[i][j][k] = \begin{cases} max(dp[i - 1][0][0], dp[i - 1][0][1]) & \text{j = 0, k = 0} \ dp[i - 1][1][0] + prices[i] & \text{j = 0, k = 1} \ max(dp[i - 1][1][0], dp[i - 1][0][1] - prices[i]) & \text{j = 1, k = 0} \ -\infty & \text{j = 1, k = 1} \end{cases} \text{ for i = 1 to n} $$

买卖股票的最佳时机 3（困难）

链接：题目链接
描述：最多两笔交易；不能当天买当天卖；只能同时持有一股；
思路：思考一天结束时的状态：可能持股，可能没持股，可能卖出过一次，可能卖出过两次也可能没卖出过；所以定义状态转移数组$dp[天数][当前是否持股][卖出的次数]$
- 未持股，没卖出过股票。$dp[i][0][0] = 0$
- 未持股，卖出过一次股票。$dp[i][0][1] = max(dp[i - 1][1][0] + prices[i], dp[i - 1][0][1])$
- 未持股，卖出过两次股票。$dp[i][0][2] = max(dp[i - 1][1][1] + prices[i], dp[i - 1][0][2])$
- 持股，没卖出过股票。$dp[i][1][0] = max(dp[i - 1][1][0], dp[i - 1][0][0] - prices[i])$
- 持股，卖出过一次股票。$dp[i][1][1] = max(dp[i - 1][0][1] - prices[i], dp[i - 1][1][1])$
- 持股，卖出过两次股票（最多两次交易，因此不存在卖出两次后还持股的情况）。$dp[i][1][2] = -\infty$
- 初始化注意：$dp[0][0][1 - 2] = -\infty$(第一天不可能已经卖出过)。$dp[0][1][1 - 2] = -\infty$(第一天持股不可能卖出过)
因此只要对这六种状态进行更新即可，同时观察到第 1 种和最后一种不会变，写的时候可以舍弃。进一步可以用 4 个变量来进行状态压缩。

买卖股票的最佳时机 4（困难）

链接：题目链接
描述：最多 K 笔交易；不能当天买卖；只能同时持有一股；
思路：类比买卖股票的最佳时机 3，定义状态转移数组为$dp[天数][当前是否持股][卖出的次数]$。仿照 3 中的定义 j = 1 为持有股票，k 代表卖出次数，然后稍微总结下得出状态转移方程为：

$$ dp[i][j][k] = \begin{cases} max(dp[i - 1][j][k], dp[i - 1][1][l - 1] + prices[i]) & \text{j = 0, k != 0} \ max(dp[i - 1][j][k], dp[i - 1][0][l] - prices[i]) & \text{j = 1, k != K} \end{cases} $$

注意：如果 K 小于 1 或 $len_{price} < 2$可以直接返回 0，否则 $K = min(K, len_{price} // 2)$。另外第一天卖出 1 次以上的金额应设为一个无穷小值或者不会越界的值（考虑 Java 的 int 情况）；然后没持股没卖出过和持股卖出过 K 次不用考虑，因为前者永远为 0 ，后者不存在该情况。最后其实可以压缩下状态，但可读性会下降；

背包系列理论基础（背包九讲）

0 - 1 背包问题

描述：有 N 件物品和一个容量为 V 的背包。第 i 件物品的体积为 $ W_i$，价值为 $V_i$，求解将那些物品放入背包可使获得价值总和最大。

思路：定义状态转移数组 $dp[使用前几个数][背包容量]$。考虑第 i 个物品是否要放入背包，分为加和不加两种情况，那么容易得到状态转移方程为：$dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - W_i] + V_i)$。因此容易写出伪代码：

1
2
3
4
5
6
7
8
9

int[][] dp = new int[N + 1][V + 1]
for i = 1 to N
	for j = 1 to V
        // 这里注意即便当前物品放不下，也可以拿之前的物品充数
		if(W_i > j)
			dp[i][j] = dp[i - 1][j]
		else
			dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - W_i] + V_i)
return dp[N][V])

优化空间复杂度：实际上容易发现 dp[i] 仅依赖于 dp[i - 1]，那么我们可以优化下空间，将 dp 变为一维数组，但这个时候就要逆序进行，否则 $dp[i][j]$的更新就依赖于$dp[i][j - W_i]$而不是$dp[i - 1][j - W_i]$。伪代码如下：
1 2 3 4 5

int[][] dp = new int[V + 1] for i = 1 to N for j = N to W_i dp[j] = max(dp[j], dp[j - W_i] + V_i) return dp[V]
初始化的细节问题：事实上该问题可分为两类，一类是恰好装满背包，另一类则没有要求装满背包。两种问题的初始化略有不同。如果是第一种，那么除了 dp[0] 为 0 外，dp[1…V] 均应设为 $-\infty$，这样能保证最后得到的 dp[V]是一种恰好装满背包的最优解；而对于第二种情况，则全设为 0 即可。
一个常数优化：二重 for 循环中的 j 的下限可以改为 $max(V - \sum_{i}^{N} w_i, w_i)$，这个可以根据二维 dp 的状态转移方程推出，分别对应拿了和没拿第 i 个物品。

完全背包问题

描述：类似于 0 - 1 背包问题，所不同的是每种物品有无限件。也就是从每件物品角度考虑，与它相关的情况并非取或不取，而是取 0 件，取 1 件，… ，取$\lfloor V / W_i \rfloor$件等多种情况；
基本思路：一个基本的想法是类似 0 - 1 背包的解法，考虑取不同个的情况，那么类似的状态转移方程也很容易写出来：$dp[i] = max(dp[j - k\cdot W_i] \lvert 0 \le k\cdot W_i \le V)$，此时的时间复杂度是 $O(NV\sum_{1}^{N} {\lfloor V/W_i \rfloor})$，其实算是蛮大的。针对这个，我们可以简单优化一下：若两件物品 i, j 满足 $V_i \le V_j$ 且 $W_i \ge W_j$ ，则显然可以去掉物品 j 。这个优化可以在 $O(N^2)$ 内实现，一般可以承受。另外，针对背包问题一种比较不错的一种方法是：首先将费用大于 V 的物品去掉，然后用类似计数排序的做法计算出重量相同物品中价值最高的是哪个，可以使用 O(V + N) 的方法实现这个优化。
转化成 0 - 1 问题的优化写法：比起直接转成 $\lfloor V/W_i \rfloor$件，我们可以采用二进制的转化方式（任何一个数都可以由若干个比它小的 2 的幂的和组成），将原物品转化为一系列重量为 $W_i \cdot 2^k$, 价值为 $V_i \cdot 2^k$ 的物品，其中$W_i \cdot 2^k \le V$。这样就把每件物品拆分成 $O(log_2 V/W_i)$件物品，是一个很大的改进。
进一步分析：考虑到每件物品可以取任意次，那么 $dp[i][j]$ 的更新完全可以依赖于 $dp[i][j - W_i]$；一方面没有重复取问题，另一方面这样取也是最优的（因为在考虑选取第 i 件物品时，我们正好需要一个可能已选入第 i 件物品的子情况）。此时时间复杂度为 O(NV)。
1 2 3 4 5

int[] dp = new int[V + 1] for i = 1 to N for j = W_i to V dp[j] = max(dp[j], dp[j - W_i] + V_i) return dp[V]

多重背包问题

描述：现在第 i 个物品最多有 $M_i$ 件可以取，求可以获得的最大价值
基本思路：与完全背包一样，这道问题同样可以化成 0 - 1 背包问题来解决，对应的状态转移方程为 $dp[i][j] = max(dp[i - 1][j - k\cdot W_i] \lvert 0\le k \ge M_i)$。时间复杂度为$O(V\sum_{1}^{N} {M_i})$

转化为 0 - 1问题的优化写法：参考完全背包的优化方法，这里同样采用二进制的转化方式，那么时间复杂度就优化成了 $O(V \sum_{1}^{N} {log_2 M_i})$，是很大的改进。下面给出其伪代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

// 处理一件 0 - 1 背包中的物品过程
def zeroOnePack(dp, W, V)
	for j = V to W
		dp[j] = max(dp[j], dp[j - W] + V)
// 处理一件完全背包中的物品过程
def completePack(dp, W, V)
	for j = W to V
		dp[j] = max(dp[j], dp[j - W] + V)
// 处理一件多重背包中的物品过程
def multiplePack(dp, W, V, M)
    // 此时该物品不可能取到多于 M 件
	if W * M >= V
		return completePack(dp, W, V)
	else
		k = 1
		while k < M
			zeroOnePack(dp, kW, kV)
			M = M - k
			k = 2k
        // 考虑无法取余 2 的部分
		zeroOnePack(dp, W * M, V * M)
int[] dp = new int[V + 1]
for i = 0 to N
	multiplePack(dp, W_i, V_i, M_i)

进一步优化：应用单调队列的方法，可以间给每个状态的值优化到 O(1) 的时间求解，从而使得总的时间复杂度优化到 O(VN)（但实际上该方法常数项较大，~~也比较难写~~，实际小数据集可能没有二进制拆分快）。假设一件物品重量为 w, 价值为 v，数量为 n，背包总承重为 V，那么可以发现：

$$ \begin{cases} f(b + kw) = max(f(b + kw), f(b + (k - 1)w) + v, …, f(b) + kv) \ f(b + (k - 1)w) = max(f(b + (k - 2)w) + 2v, …, f(b) + (k - 1)v) \ … \ f(b + 0w) = max(f(b)) \end{cases} $$

而后进一步对上述公式进行一个**简单**的变换，就能得到：

$$ \begin{cases} f(b + kw) - kv = max(f(b + kw) - kv, f(b + (k - 1)w) - (k - 1)v, …, f(b)) + kv \ f(b + (k - 1)w) - (k - 1)v = max(f(b + (k - 2)w) - (k - 2)v, …, f(b)) + (k - 1)v \ … \ f(b + 0w) - 0v = max(f(b)) + 0v \end{cases} $$

容易发现每一项求最大值时的项值都有重复，这就可以用单调队列来优化了，下面给出优化代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

def multiplePackWithMonotonicQueue(Deque deque, int weight, int value, int num)
    // wstart, wend 分别对应 deque 的窗起始和窗结束
    k, wstart, wend = 0
    // b 对应背包容量取余 weight 的余数
    for b = 0 to weight
        deque.clear()
        wstart = b
        for j = b, b + weight, b + 2 * weight, ..., capacity
            if wend - wstart = num * weight
            	// 第一个不一定对应 wstart
                if deque.peekFirst()[0] == wstart
                    deque.removeFirst()
                wstart += weight
            k = (j - b) / weight
            while !deque.isEmpty() && deque.peekLast()[1] < dp[j] - k * value
            	deque.removeLast()
            deque.addLast([j, dp[j] - k * value])
            wend = j
            dp[j] = deque.peekFirst()[1] + k * value

混合背包问题

描述：如果将 0 - 1 背包、完全背包和多重背包的情况混合情况，这该怎么求解？
分析：其实只要判断当前物品属于哪一类，然后分别用先前对应的背包递归公式去整就好了。判断也只需要 O(1) 的时间。

二维背包问题

描述：对于每件物品，具有两种不同的空间消耗，选择两种物品必须同时付出这两种代价。设第 i 件物品的两种代价分别为 $C_i$ 和 $D_i$，两种代价可付出的最大值分别为 V 和 U，物品的价值为 $W_i$。
分析：因为只是多了一维代价而已，所以只要更改状态至三维即可，那么容易写出状态转移方程如下：$dp[i, u, v] = max(dp[i - 1, u, v], dp[i - 1, u - U_i, v - V_i] + W_i)$。而后剩下的就是按照先前问题的解法：当每件物品只可以取一次时变量v和u采用逆序的循环，当物品有如完全背包问题时采用顺序的循环，当物品有如多重背包问题时拆分物品。
变化的描述：有的时候，“二维费用”是用这样的一种隐含的方式给出的——最多只能取 U 件物品，这实际上相当于每件物品多了一种“件数”的费用，而每个物品的件数费用均为 1 ，可付出最大件数费用为 U。之后剩下的就是基本操作了。
另一种看待角度：也可以将二维背包看成复整数域上的背包问题。也就是说，背包的容量以及每件物品的费用都是一个复整数。而常见的一维背包问题则是自然数域上的背包问题。所以说，一维背包的种种思想方法，往往可以应用于二位背包问题的求解中，因为只是数域扩大了而已。

分组背包问题

描述：有 N 件物品和一个容量为 V 的背包。第 i 件物品的费用为 $C_i$，价值为 $W_i$。这些物品被划分为 K 组，每组中的物品最多选一件。求可获得的最大价值总和。
分析：实际上这个问题变成了——对于每一组物品，是选择一件物品，还是一件物品都不选。那么我们设状态数组 dp[k, v] 代表前 k 组物品花费费用 v 能取得的最大利益，容易得到转移方程为：

$$ dp[k, v] = max(dp[k, v], dp[k - 1, v - C_i] + W_i \lvert item_i \in group_k) $$

而这里的每个物品显然是 0 - 1 物品，接着就容易写出伪代码：

1
2
3
4

for k = 1 to K
	for v = V to 0
		for item i in group k
			dp[v] = max{dp[v], dp[v - C_i] + W_i}

有依赖背包问题

泛化物品

背包问题问法的变化

引言：常见的背包问题问法的变化可能包括：最多能放多少物品或最多能装满多少背包的空间等，这些只需要根据具体问题来更改状态转移方程即可。还有比如要求“总价值最少”或“件数最少”，这个也只要把原式子的 max 改为 min 即可。
输出方案：这个在动态规划里其实很经典，只要根据状态转移方程判断当前状态的上一个状态是什么，然后一直往前推就可以得到答案。
输出字典序最小的方案：这里“字典序最小“是指 1…N 号物品的选择方案排列出来后字典序最小。一般来说只要在转移时注意策略即可。（暂且不看）
求方案总数：对于一个给定了背包容量、物品费用、物品间相互关系（分组、依赖等）的背包问题，除了再给定每个物品的价值后求可得到的最大价值外，还可以得到装满背包或将背包装至某一指定容量的方案总数。对这种问题，一般只要把状态方程中的 max 改为 sum 即可，同时初始条件 dp[0, 0] 应设为 1。能够这样做是因为状态转移方程遍历了所有可能的背包方案；

最优方案总数：这里的最优方案是指物品总价值最大的方案，下面以 0 - 1 背包问题为例，我们设 dp[i, v] 代表该状态的最大价值, g[i, v] 代表这个子问题的最优方案总数。那么：

1
2
3
4
5
6
7
8
9

g[0, 0] = 1
for i = 1 to N
	for v = 0 to N
		dp[i, v] = max(dp[i - 1, v], dp[i - 1, v - C_i] + W_i)
		g[i, v] = 0
		if dp[i, v] == dp[i - 1, v]
			g[i, v] += g[i - 1, v]
		else
			g[i, v] += g[i - 1, v - C_i]

求次优解、第K优解：对于这种问题如果能写出状态转移方程并用动态规划求解，那么求解复杂度往往仅比求最优解的复杂度上多个 K 。其基本思想是，将每个状态都表示成有序队列，将状态转移方程中的 max/min 转化成有序队列的合并。（暂且不看）

背包问题具体问题

分割数组（中等）

链接：题目链接
描述：给定一个数组，是否能将其分割成两个子数组，使得两个子数组的和相同
0 - 1背包思路：其实只要找到一个子数组，那剩下的必然是另一个子数组。而每个子数组的和已知，且原数组每个数只能用一次。那么原问题可以转化为给定一个容量为原数组和一半的背包，求是否存在将其填满的 0 - 1 背包问题了。注意初值 dp[0] = 0。状态转移方程为 dp[i] = dp[i] || dp[i - v]。

目标和（中等）

链接：题目链接
描述：给定一个数组，其中的每个数均非负。给定一个目标值，在数组中的每个数前均要加上 “+” 或 “-” 号，求使得最终计算值等于目标值的添加符号的方案总数。
0 - 1 背包思路：粗看其实没什么想法（~~就是没想法~~），但是再考虑到原数组非负，那么这个 target 肯定是两个子数组值相减得出来的。再分析下两个子数组的值，容易得到较大的一个子数组的值应该为 (sum + target) / 2，其中 sum 为原数组的和。那么目标很明确了，原问题转化为求给定一个容量为该值的背包，求从原数组刚好填满该背包的 0 - 1 背包问题。由于是求方案数，那么状态转移方程应该用 sum 即 dp[i] = sum(dp[i] + dp[i - j])，另外初值 dp[0] = 1。

盈利计划（困难）

链接：链接
思路：太久没做背包问题了，一时间竟然没看出来是二维背包问题。本质上还是一个二维 0 - 1 背包问题，那就套模板，设 dp[i, j, k] 代表拿 i 个物品用 j 个人且最小利润是 k 的方案数，容易知道 dp[i, j, 0] = 1 和状态转移方程 dp[i, j, k] = dp[i, j, k] + dp[i, j - C_i, max(0, k - V_i)]。

最后一块石头的重量 2（中等）

链接：题目链接
给定一个数组，每个元素代表一块石头的重量，现在让你在直到原数组非空或仅剩一个元素前任意挑选两块石头进行碰撞。如果两块石头重量相等，那么两块石头全都消失；反之轻的一块消失，重的那块的重量留下但要减去轻的那块的质量。现在求剩下石头的最小重量。
基础思路：要使得剩下石头重量最小，当然要从最大的开始挑，每次碰的时候挑质量最相近的碰才行。那么可以先对数组进行排序，然后逆序两两碰撞，不断循环，直到数组为空或剩下一个元素。设数组长度为 n ，假设使用计数排序，那么时间复杂度大约是 O(nlogn)，递归易得(T(n) = T(n/2) + 3.5n)。（~~但整体设计好繁琐就没写，绝不是因为我又懒又菜。~~）
0 - 1 背包思路：其实换个角度，既然我们每次都逆序挑两个重量相近的石头碰，那为什么不把这个过程中两个石头组合下变为两组呢？（~~脑袋突然开窍~~）那么如果想得到最小剩余重量，设总重量为 sum，那么较小质量那组质量最好是 $\lfloor sum / 2 \rfloor$，这样最小剩余重量就是 $sum - 2 * \lfloor sum / 2 \rfloor$。这样这个问题又变成一个 0 - 1 背包问题了（欧耶)，但有可能这个数取不到，不过由于我们计算了取到 0 到这个数为止的可能情况，所以问题不大。

零钱兑换（中等）

链接：题目链接
描述：给定一个数组，每个元素代表不同面额的零钱，现给定一个总金额 target，求用零钱凑成总金额的最小个数，每种零钱随便取。
完全背包思路：其实就是完全背包问题嘛。看到最小个数，啪的一下很快啊，祭出了完全背包的代码，提交，果不其然地没有闪（~~出错了~~）。一看还是初值设的不对，设为 Integer.MAX_VALUE 越界了，再一看 target 范围，走您， AC 了。顺带记下状态转移方程：dp[j] = min(dp[j], dp[j - coin] + 1)。

零钱兑换 2（中等）

链接：题目链接
描述：咱这次不求最小个数，来求个组合方案
思路：这不就完全背包把 min 改成 sum 的事嘛，啪的一下很快啊，完全背包一写，噌地通过了。记录下状态转移方程 dp[j] = dp[j] + dp[j - coin]，另外 dp[0] = 1（~~上一题的遗产~~）。

组合总和 4（中等）

链接：题目链接
描述：基本与零钱兑换 2 一致，但顺序不同的序列将被视为不同的组合（~~题目你不讲武德啊，描述不写放在示例输入里阴我~~）。
思路：看了眼题解，发现把 for 循环中的 i 和 j 的顺序换了过来就能 work，这是为什么呢？举个例子，假设计算 dp[4]，然后数组里有 1 和 3，显然这样的循环会分别考虑 1 打头和 3 打头的两种情况，所以这种做法考虑了不同的排列顺序。而正常情况下，计算 dp[4] 其实是递进计算的，先计算 1 可以填多少个，再计算 3 可以填多少个，所以不包括排列顺序。下面是正常循环的 dp 数组变换情况。

$$ dp = \begin{cases} [1, 0, 0, 0, 0] & \text{initial} \ [1, 1, 1, 1, 1] & \text{add 1} \ [1, 1, 1, 2, 2] & \text{add 3} \end{cases} $$

路径篇

不同路径（中等）

链接：题目链接
描述：求从（0， 0）走到（m, n）的所有不同路径，每次只能往上或往右走一步。
动态规划思路：$dp[i][j] = dp[i - 1][j] + dp[i][j - 1]$ and $dp[0][0] = 1$。
数学题的思路：其实就是排列组合么，一共移动 m + n - 2 次，其中 m - 1 次向下移动，那么只需要计算 $C_{m + n - 2}^{m - 1}= $ 就好了。
1 2 3 4 5

ans = 1, i = n, j = 1 while j < m ans = ans * i / j i++ j++

不同路径 2（中等）

链接：题目链接
描述：和之前一样，但有些位置有障碍。
动态规划思路：和之前一样，但有障碍直接不更新就好了么（~~傻逼LC把障碍放在入口~~）。其实空间还可以进一步压缩，因为我们可以逐行扫描（因为每次扫描是 $dp[i][j]$ 是基于先前的 $dp[i - 1][j] $ ，其实逐列也可以）。那么空间复杂度可以从 O(mn) 压缩到 O(m)。

最小路径和（中等）

链接：题目链接
描述：给定一个数组，每个元素代表经过这里的代价，每次只能向下或向右走一步，求从左上到右下的最短代价路径。
动态规划思路：其实二维的很简单么，但其实可以压缩到一维，不过要花点心思注意下，下面是压缩后的状态转移方程，分别对应第一列、第一行第一列和其余行列三种情况。

$$ dp[j] = \begin{cases} cost[i][j] & \text{j = 0} \ dp[j - 1] + cost[i][j] & \text{j != 0 & i = 0 } \ min(dp[j], dp[j - 1]) + cost[i][j] & \text{j != 0 & i != 0} \end{cases} \text{for i = 1 to m, for j = 1 to n} $$

三角形最小路径和（中等）

链接：题目链接
描述：现在给定的数组是三角形的了，其他一样，但走的时候应满足规则：若上一层走第 k 个，则下一层只能走第 k 或 k + 1 个。求从最上层走到最小层的最短代价
动态规划思路：其实状态转移方程也不难想么，设 $dp[i][j]$ 为到达第 i 层第 j 个的最短代价，则

$$ dp[i][j] = \begin{cases} cost[i][j] & \text{i = 0 & j = 0} \ dp[i - 1][j - 1] + cost[i][j] & \text{i != 0 & j = i} \ min(dp[i - 1][j], dp[i - 1][j - 1]) + cost[i][j] & \text{i != 0 & j != i} \end{cases} \text{for i = 1 to len, j = 1 to i} $$

续：其实观察下状态转移方程，可以状态压缩下，只不过这时候遍历 j 的时候要倒序遍历（参考完全背包的想法）；另外如果可以修改原数组，可以直接就地修改数组。最后遍历最后一层输出最小值即可。

字符串编辑

一次编辑（中等）

链接：题目链接
描述：给定两个字符串，判断第一个是否能经过一次操作（插入、删除、替换）变成另一个
朴素思路（双指针）：先判断长度差，大于 1 肯定不行；如果相等，单指针记录不同的数量，大于 1 则 false；反之双指针记录不同的数量，如果不同则较长字符的指针加一，反之两者均加一，最后也是判断不同的数量。
动态规划思路：（~~想来自己还是又懒又菜~~）虽然知道是 dp 题，但也没往这方面想，不过其实想着拓展到n 次操作着朴素思路确实就不行了。废话不多说，记 $dp[i][j]$ （两维长度分别为原字符串长度加一）使得两个字符串前 i 和前 j 个字符相等所需要进行的最少操作，那么容易得到转移方程（中间前两个对应插入或删除，后一个对应替换）；而且改进后可以适配 n 次 操作的情况，更加通用。

$$ dp[i][j] = \begin{cases} dp[i - 1][j - 1] & s1_i = s2_j \ & \ i != 0 \ & \ j != 0 \ min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1 & s1_i != s2j \ & \ i != 0 \ & \ j != 0 \ max(i, j) & \text{i = 0 || j = 0} \end{cases} $$

续：其实从转移方程可以看出，如果我们能记录下一些中间变量 $dp[i -1][j - 1]$，那么这个状态数组完全可以变成一维的，从而进一步压缩状态；

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

int[] pre = new int[2]
for i = 1 to len_s1
	dp[0] = i
	// dp[i - 1][j - 1]
	pre[0] = i - 1
	for j = 1 to len_s2
		pre[1] = pre[0]
		// set pre[0] to next dp[i - 1][j - 1](dp[i - 1][j])
		pre[0] = dp[j]
		swap dp[i - 1][j - 1] with pre[1] in the transfer function

编辑距离（困难）

链接：题目链接
描述：与一次编辑类似，只不过这次不是让你求是否一次编辑的成果，而是让你计算最少编辑次数
动态规划思路：其实一次编辑里已经讲过了，最后返回的不是判断而是 dp 末尾那个就好了

含正则的字符串匹配

正则表达式匹配（困难）

链接：题目链接
描述：给定一个字符串 s 和一个字符规律 p，判断 p 是否能正则匹配 s。两个字符串中都仅包含小写字母，另外 p中可能包含 $"\ast"$ 和 $"."$，其中前者代表匹配 0 个或多个前面的有效字符，后者匹配任意的字符。题目保证每次出现字符$"\ast"$ 时，前面都能匹配到有效的字符。
动态规划思路：设定状态变量 $dp[i][j]$ 表示第一个字符串前 i 个字符和第二次个字符规律前 j 个字符的匹配情况。若 $p[j] != \ast$，$dp[i][j] = \begin{cases} false & \text{s[i] != p[j]} \ dp[i - 1][j - 1] & \text{s[i] = p[j]} \end{cases}$
若$p[j] = \ast$, $dp[i][j] = \begin{cases} dp[i][j - 2] &\text{s[i] != p[j - 1]} \ dp[i - 1][j - 2] & \text{s[i] = p[j - 1]} \ dp[i - 2][j - 2] &\text{s[i - 1] = s[i] = p[j - 1]} \ … \end{cases}$ 但显然对于第二种情况，我们不可能无限枚举出所有情况，这样写也很麻烦，因此换个角度，在字母 + 星号的组合匹配过程中，本质上只有两种情况：
- 不匹配 s 末尾的字符，将该组合扔掉，不再进行匹配
- 匹配 s 末尾的字符，而后扔掉该字符，而该组合还可以继续匹配后面的字符串由此可以改进状态转移方程为:

$$ dp[i][j] = \begin{cases} dp[i][j - 2] || dp[i - 1][j] & \text{s[i] = p[j - 1]} \ dp[i][j - 2] & \text{s[i] != p[j - 1]} \end{cases} $$

若$p[j] = .$，那么 $dp[i][j] = dp[i - 1][j - 1]$。故而我们的状态转移方程为： $$ dp[i][j] = \begin{cases} \text{if p[j] != ‘*’} \begin{cases} dp[i - 1][j - 1] & \text{s[i] = p[j] || p[j] = ‘.’} \ false & \text{otherwise} \end{cases} \ \text{otherwise} \begin{cases} dp[i - 1][j] || dp[i][j - 2] & \text{s[i] = p[j - 1] || p[j - 1] = ‘.’} \ dp[i][j - 2] \text{otherwise} \end{cases} \end{cases} \text{for i = 0 to len}_s\text{, j = 1 to len}_p $$

续：另外注意初值 $dp[0][0] = true$。而且 i 的循环下标应该从 0 开始，因为空字符串 s 也可能被非空规律如 ‘a*’ 这种所匹配。

通配符匹配（困难）

链接：题目链接
描述：给定一个字符串 s 和一个字符规律 p，判断 p 能否正则匹配 s 。两个字符串中都仅包含小写字母，而字符规律中还可能 $"?"$ 和 $"\ast"$，前者能匹配任意字符（不包括空），后者可以匹配任意字符串（包括空串）。
自己的动态规划思路：仿照上一题正则表达式匹配的思路，设置状态 $dp[i][j]$ 代表字符串前 i 个字符和字符规律前 j 个字符的匹配情况，则容易进行情况分类：若 $p[j] != “\ast”$，则 $dp[i][j] = \begin{cases} dp[i - 1][j - 1] & \text{s[i] = p[j] || p[j] = “?”} \ false & \text{otherwise} \end{cases}$ 若 $p[j] = “\ast”$，则$dp[i][j] = dp[i][j - 1] || dp[i - 1][j]$
续：但是考虑到字符串 s 的指针 i 会从 0 开始（考虑 "" 和 “*” 的情况），为了避免越界，所以要额外考虑 i = 0 时的匹配情况，略微思考一下，容易得到：

$$ dp[i][j] = \begin{cases} p[j] = “\ast” \begin{cases} dp[i][j - 1] & \text{i = 0} \ dp[i][j - 1] || dp[i - 1][j] & \text{i > 0} \end{cases} \ otherwise \begin{cases} i = 0 \begin{cases} false & p_j != “*” \ dp[i][j - 1] & \text{otherwise} \end{cases} \ i > 0 \begin{cases} false & p_j != “?” & s_i != p_j \ dp[i - 1][j - 1] & \text{otherwise} \end{cases} \end{cases} \end{cases} \text{for i = 0 to len}_s\text{, j = 1 to len}_p $$

再续：再观察状态转移方程，其实不难发现我们还可以进一步压缩状态变量至一维，只要用变量记录 $dp[i - 1][j - 1]$ 和 $dp[i - 1][j]$ 即可，具体方法可以参考编辑距离的滚动数组的方法。翻了下 LC 题解中的动态规划，发现和我的一样，成就感 + 1。
贪心算法：

其他杂

最大整除子集（中等）

链接：链接
描述：给定一个无重复的正整数数组 nums ，求一个最大整除子集，该子集中任意两个元素 i, j 都满足 i % j == 0 或 j % i == 0。
分析：因为只要满足两个条件之一，那么选一个就好。所以直接将原数组排序，然后满足大的能整除小的即可。而后三叶题解。暂时不写自己的看法。
题解：设 dp[i] 表示以 nums[i] 结尾的整除子集的长度，那么如果有 $nums[i] % \ nums[j] == 0$ ，我们就可以更新 dp[i] 的值，即 $dp[i] = max(dp[i], dp[j] + 1)$，即把 nums[i] 接到 nums[j] 结尾的整除子集后面。另外需要注意的是，dp[i] 初始值应当是 1，应为一个数本身就可以构成一个整数子集。之后为了保证添加顺序，我们先要对原数组排序。然后这道题要输出子集的所有数，所以我们要维护一个索引表示最长子集长度和最长子集对应最后一个数的索引，之后回溯加入集合。

索引为 0 的方案数（困难）

描述：给定一个步数 steps 和数组长度 arrLen，数组索引从 0 开始。你从索引 0 出发，每次可以往左或往右或原地不动，但不能走出超过数组左边界 0 和右边界 arrLen - 1，求最后仍然待在索引 0 的走法总数。
思路：设定 $dp[i][j]$ 代表走 step 步后当前位置在索引 j 的方案数，那么容易得到状态转移方程为：$dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j] + dp[i - 1][j + 1]$。因为 dp[i] 只和 dp[i - 1] 有关，因此可以进一步压缩状态变量到一维，而这只需要额外记录 $dp[i - 1][j - 1]$ 即可。另外可以优化的是 j 这里的最大值，即 $arrLen = min(steps, arrLen)$，毕竟走 5 步怎么到不了索引 6。

石子游戏（中等）

链接：题目链接
描述：给定一个数组 nums，数组的每个元素代表了该堆石子的数量，数组的长度 len 是偶数，数组的和 sum 为奇数；现在有两个小孩每次分别从里面取一次数（从头或从尾取），两个小孩均发挥最其最好的水平，求先手的小孩是否能赢？
个人动态规划思路：要想赢，那么拿到的石子数必然大于等于 sum // 2 + 1，那么可以将原问题转化为拿 len / 2 次的情况下，所能拿到的最多石子是否大于等于目标值的问题。那么设状态数组 $dp[拿的次数][拿第一个或最后一个]$，$dp[i][j]$ 对应当前拿 i 次且第 i 次拿第 j 个可以拿到的最大石子数，则容易得到状态转移方程如下：

$$ dp[i][j] = \begin{cases} max(dp[i - 1][0] + nums[i], dp[i - 1][1] + nums[i - 1]) & \text{j = 0} \ max(dp[i - 1][0] + nums[len - (i - 1)], dp[i - 1][1] + nums[len - i]) & \text{j = 1} \end{cases} \text{for i = 1 to len / 2} $$

官方动态规划思路：设状态变量 $dp[i][j]$ 为剩下石子堆为下标 i 到下标 j 时当前玩家与另一个玩家的最大石子差，当前玩家不一定是先手玩家，那么分类讨论下情况，容易得到：

$$ dp[i][j] = \begin{cases} 0 & \text{i > j} \ nums[i] & \text{i = j} \ max(nums[i] - dp[i + 1][j], nums[j] - dp[i - 1][j]) & \text{i < j} \end{cases} \text{for i, j = 1 to len} $$

续分析：如果 i > j，那么显然 $dp[i][j] = 0$，因为没有石子可以拿；如果 i < j，那么这个公式也不难得出；如果 i = j，那么我们可以尝试将 i = j 代入 i < j 的公式中，得到的结果就是 nums[i]。
数学思路：（~~我是傻逼~~）其实先手一定赢。将石子按序号的奇偶分成两组，如果先手取走第一个（第一组），那么后手无论取第一个还是最后一个都属于第二组，反之亦然；接下来也可以依次递推。那么先手总是可以取组的总和大的那组，所以先手一定赢。

不相交的线（中等）

链接：链接
描述：给定两个数组 nums1 和 nums2，现在将两个数组的元素分成两行排列；对于两个数组的元素 nums1[i] 和 nums2[j]，如果二者相等，那么我们可以画一条线连接二者；但这条线不能和其他线相交。求可以绘制的最大连线数。
题解：看了题解才知道这是最长公共子序列啊，我真傻。。。首先给定状态变量 dp[i, j] 代表两个数组前 i 和前 j 个元素可以绘制的最大连线数，那么我们有如下递推公式。容易知道这是正确的

$$ dp[i][j]= \begin{cases} dp[i - 1][j - 1] + 1 & \text{nums1[i] = nums2[j]} \ max(dp[i][j - 1], dp[i - 1][j]) & \text{otherwise} \end{cases} $$

奇怪的打印机（困难）

链接：链接
描述：有台奇怪的打印机有以下两个特殊要求：①打印机每次只能打印由同一个字符组成的序列。②每次可以在任意起始和结束位置打印新字符，并且会覆盖掉原来已有的字符。给你一个字符串 s ，你的任务是计算这个打印机打印它需要的最少打印次数。
解法：知道是 dp ，就是没想出来，一开始状态变量也没设对，或许是太久没做了。设状态变量 dp[i, j] 为打印字符串 s 中第 i 到第 j 个字符需要的最少次数，那么我们有：

$$ dp[i][j] = \begin{cases} dp[i][j - 1] & \text{s[i] = s[j]} \ min(dp[i][k] + dp[k + 1][j]) & \text{otherwise;for k = i to j - 1} \end{cases} \text{for i = len}_s\text{ to 0, j = i to len}_s $$

单词拆分（中等）

链接：链接
描述：给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判断该字符串是否能被拆分成列表中的多个单词。你可以重复使用列表中的单词。
分析：又是 dp，又没想出来。设状态变量 dp[i] 代表长度为 i 的字符串是否能被拆分。那么

$$ dp[i] = dp[j] && \ wordDict.contains(s.substring(j, i)) \ for \ j = 0 \to i - 1 $$

续：其实可以发现 j 不必要从 0 开始，而是从 max(0, i - maxLen(word)) 即可，其中 word 是 wordDict 中的单词。

戳气球（困难）

链接：链接
分析：
- 自己写的记忆化回溯不知道为什么超时了，思路是按照戳气球的方法
- 官方则是将戳改成添加气球的方法（也不知道怎么想到这样做的）。设状态变量 dp[i, j] 表示将开区间 (i, j) 内的位置全部填满气球能够得到的最多硬币数，那么有如下转移方程。然后遍历时候记得逆序就好了。
$$ dp[i, j] = \begin{cases} \mathop{max} \limits_{k = i + 1 \to j - 1} (val[i] \cdot val[k] \cdot val[j] + dp[i, k] + dp[k, j]) & i < j - 1 \ 0 & i \geq j - 1 \end{cases} $$

最大正方形（中等）

链接：链接
分析：
- 关键还是设置好状态变量，dp[i, j] 设置为以 i，j 为右下顶点的最大正方形可比设置为包含该点的正方形要省事多了（哭）。这状态转移方程还真就一点就会，一想就废。
  - dp[i, j] = min(dp[i - 1, j], dp[i - 1, j - 1], dp[i, j - 1]) + 1 if matrix[i, j] = ‘1’

找两个和为目标值且不重叠的子数组（中等）

链接：链接
描述：给定一个正整数数组和一个目标值，求原数组中两个互不重叠且各自和均等于目标值的子数组，返回两个子数组的长度和的最小值。
分析：
- 首先前缀和肯定是要求的。然后朴素思路是两重 for 循环，第一重可以得到前半部分的最短子数组，第二重可以得到后半部分的最短子数组，然后用二分加速搜素，这样时间复杂度大约为 $O(n^2 logn)$ ，然后就超时了。
- 实在没想到这是道动态规划题。。。设状态变量 dp[i] 表示原数组 [0, i) 范围内和为目标值的最短子数组的长度，接下来就很明了了，这样就只要一次遍历即可，照例用二分加速搜素，时间复杂度为 $O(nlogn)$。
变体：链接统计二维数组中全为 1 的正方形子矩阵的个数。前缀和法可以做，但是超级慢。动态规划的话真巧妙。。。设 f(i, j) 表示以 i, j 为右下角的最大正方形的边长，那么通过推理可以得到如果i, j 处数组值为 1，那么有f(i, j) = min(f(i -1, j), f(i - 1, j - 1), f(i, j - 1)) + 1。需要注意的是当min 函数中某些项不存在时，应该用 0 代替。

等差数列划分（困难）

链接：链接
描述：给定一个数组 nums，求其所有为等差数列的子序列的个数，其中等差数列是指长度至少为 3 的序列。
分析：
- $O(n^2)$ 的动态规划：话说太久不做确实也想不到合适的状态变量啊。设状态变量 f[i, d] 代表以 nums[i] 结尾，公差为 d 的**长度至少为 2 **的等差序列的个数，那么可以得到：
  - f(i, d) = f(i, d) + f(j, d) + 1 if nums[i] - nums[j] == d and i > j
  - 简单分析下上面的式子：1 是直接把 nums[i] 加到 nums[j] 所在序列后，f(j, d) 是直接不要 nums[i], f(i, d) 是直接不要 nums[j] 所在项。但 f(i, d) 和 1 二者是否会有重复呢？答案是不会的，因为这次是第一次加。另外注意到 f(j, d) 的长度至少是 2，再加上一个 nums[i] 后就至少是 3，因此最后的答案 res 只要每次累加 f(j, d) 即可
  - 而后注意到公差的数量可能很大，这里偷懒用了哈希表来保存

交错字符串（中等）

链接：链接
描述：给定三个字符串 s1、s2、s3，请你帮忙验证 s3 是否是由 s1 和 s2 交错组成的。两个字符串 s 和 t 交错的定义与过程如下，其中每个字符串都会被分割成若干非空子字符串：s = s1 + s2 + ... + sn; t = t1 + t2 + ... + tm;|n - m| <= 1;交错是指 s1 + t1 + s2 + t2 + s3 + t3 + ... 或者 t1 + s1 + t2 + s2 + t3 + s3 + ...
分析：~~(怎么又是动规题啊)~~ 给定 f(i, j) 状态量表示 s3[0, i + j) 是否由 s1[0, i) 和 s2[0, j) 拼接完成，则容易得到 f(i, j) |= f(i - 1, j) && s1[i - 1] == s3[i + j - 1] || f(i, j - 1) && s2[j - 1] == s3[i + j - 1]

丑数 2 （中等）

链接：链接
描述：给定一个正整数 n，求第 n 个丑数（质因数只有 2，3，5 的数）。
最小堆+哈希：暴力肯定是不行的。但如果我们知道第 k 个数 x 是丑数，那么 2x, 3x, 5x 也是丑数。如果用一个最小堆来维护这些丑数，然后取堆顶不就可以了么。但由于 2*3 = 3*2，所以要用哈希表去重（指哈希表里有了就不往最小堆里加了）。
动态规划：考虑这样一个问题，下一个丑数究竟是由前面的哪一个丑数乘以几得到的呢？因为乘数有限（2,3,5），所以可以维护乘数对应数的索引。令 dp[i] 表示下一个可能的丑数所对应先前已经得到的丑数的索引。若下一个丑数等于 dp[i] 乘以乘数，那么 dp[i] + 1，否则不变。伪代码如下：注意要用 3 个 if 判断而非 if-else，因为存在 2*3 = 3*2 的情况。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

int[n] ugly
int[3] dp 
ugly[0] = 1;
for i = 1 to n - 1:
	a = ugly[dp[0]] * 2;
    b = ugly[dp[1]] * 3;
    c = ugly[dp[2]] * 5;
    next = min(a, b, c);
    if a == next:
        dp[0]++;
    if b == next:
        dp[1]++;
    if c == next:
        dp[2]++;
    ugly[i] = next;

统计作战单位（中等）

链接：链接
描述：给定一个数组 arr，求所有严格单调递增或严格单调递减的长度为 3 的子序列的个数。
分析：因为数组长度最多就 1000，本题暴力可以直接 AC。而后是没想到的动态规划，设f[i, j] 分别在 j = 0, 1, 2, 3时分别代表以 arr[i] 结尾的长度为 2，3，2，3 的上升、上升、下降、下降子序列的个数，那么容易得到转移方程如下：
- $f[i, 0] += 1; f[i, 1] += f[j, 0] \ \text{if arr[i] > arr[j]; i > j}$
- $f[i, 2] += 1; f[i, 3] += f[j, 0] \ \text{if arr[i] < arr[j]; i > j}$

回溯

概要：回溯问题求解在于如果避免重复遍历和如果终止遍历以及结果的记录，遍历方式可以是深度优先也可以是广度优先，一般是定义一个 visited 数组来记录。如果可以修改原数组，改也是可以的。

排列、组合、子集相关问题

全排列（中等）

链接：题目链接
描述：给定一个不含重复数字的数组 nums，返回其所有可能的全排列，返回顺序任意。

回溯思路：还是从暴力 for 循环着手，假设 nums = [1, 2, 3]，那么暴力相当于每次选一个打头，然后递归剩下的子数组 subNums，直到子数组 subNums 为空。这个其实算是一个深度优先搜索，而后除了产生子数组，也可以采用记录某个数是否有被使用过的方法，即定义一个数组 used，而后套上深度优先的壳，应该就 work 了。因为难以表达，这里直接给出伪代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def dfs(List result, boolean[] used, List path, int depth, int maxDepth)
	if depth == maxDepth
		result.add(path)
	else
		for i  = 0 to len_nums - 1
			if !used[i]
				path.add(nums[i])
				used[i] = true
				dfs(result, used, path, depth + 1, maxDepth)
				used[i] = false
				path.remove(len_path - 1)

全排列 2（中等）

链接：题目链接
描述：现在给的数组是有重复的了，继续求全排列
思路：其实基本思路还是有的，就是上一题记录的时候用 Set，最后再转成 List 就好了，不过据说很慢。学习下正统做法是在加的时候就避免重复，即剪枝。
续：很明显，如果某个数和上一个数相等，那么这个数就不应该进入循环，当然我们能这样做得先对数组 nums 进行排序才行。当然剪枝不仅是应该是和上一个数相等，举例 nums = [1, 1, 1, 3]，由于第 2, 3 个数和第 1 个数相等，所以第 2, 3 个数永远不会被使用，导致得不到答案。那么自然的想法是如果上一个数被用了 (used[i - 1] = true)，其实反面也可以 (used[i - 1] = false)。那么这两种方法区别在哪呢：
- 第一种：第一层有 3 种选择，而对于第 1, 2 种选择，由于分别会导致第 2 个和第 3 个没法被选中，因此前两种 1 选择无效，从第三种 1 开始才有效；
- 第二种：第二种由于取反了，因此对于第 2, 3 种选择，分别会导致第 2 个和第 3 个没法选上，因此后两种 1 选择无效。
- 总结：取不取反的区别仅在于保留的是相同元素的顺序索引还是倒序索引而已。

组合总和（中等）

链接：题目链接
描述：给定一个无重复数组 nums 和目标值 target，数组中元素可以取用任意次，求使得元素和为 target 的所有不重复数组（注意：排列不同不算不同）

思路：其实这题思路和全排列相同，但由于排列不同元素相同也算同一种，因此需要设置一个 for 循环的起始量 beginIndex 来避免重复。简单来说，根据回溯树来看，对于一个数，他一定会穷尽所有包含该数的可行方案，那么对于它的下一个数，显然不应该包含它，即循环应该从当前数开始而不是从 0 开始。下面是主要伪代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def dfs(List result, List path, int[] nums, int sum, int target, int  beginIndex)
	if sum == target
		result.add(path)
	else
		for i = beginIndex to len_nums
			if sum + nums[i] <= target
				path.add(nums[i])
				sum += nums[i]
				dfs(result, path, nums, sum, target, i)
				sum -= nums[i]
				path.remove(path.size() - 1)

组合总和 2 （中等）

链接：题目链接
描述：给定一个数组（可能有重复）nums 和目标值 target，数组中元素仅能取用一次，求使得元素和为 target 的所有无重复数组（排列不同不算不同）
自己的思路：刚开始还是想简单了，套个 beginIndex 就开锤，结果就错了，举个例子：nums=[1, 1, 2, 5], target = 8 。那么这样就会导致 [1, 2, 5] 出现 2 次，因此又加了个 used 数组判断，就可以了。

组合（中等）

链接：题目链接
描述：给定两个数 n 和 k，求 1-n 范围内长度为 k 的不同子数组（排列不同不算不同）
自己的思路：还是一般回溯思路，带上一个 begin 避免重复使用前面的数。然后其实还可以剪枝以下，即 n - i + 1 + path.size() < k 时可以直接 return，因为剩余数字不足以构建长度为 k 的子数组

子集（中等）

链接：题目链接
描述：给定一个数组 nums，求它的所有子集（包括空集）
自己的思路：就普通回溯么，用一个 begin 来避免后面的子集重复使用前面的数字。然后每次 dfs 前要加上当前的路径 path 即可。

子集 2（中等）

链接：题目链接
描述：现在给定的数组可能有重复，继续求子集（包括空集）
自己的思路：其实和子集问题没有太大区别，只是有了重复数据，那么参考全排列 2中的做法，再加上一个 used 数组来剪枝即可。

第 k 个排列序列（困难）

链接：题目链接
描述：给定两个数 n 和 k，求 1-n 的所有全排列中第 k 小的排列
自己的回溯思路：其实就是原来求全排列那里截止到第 k 个返回就好了，不过其他可以稍微优化下。但我知道这方法肯定效率感人。
数学思路：看了题解，就是动态算出每位数应该是多少么。举个例子，对于第一位数，它的大小应该是 $num_1 = \lceil k / (n - 1)! \rceil$，然后 $k = k - (num_1 - 1) * (n - 1) !$ 。后面就一次递推就行，公式就是$num_i = \lceil k / (n - i)! \rceil$，$k = k - (num_i - 1) * (n - i)!$ 。

有效的 IP 地址（中等）

链接：题目链接
描述：给定一个全部由数字构成的字符串，求按序使用其所有字符能构成的有效 IPV4 地址，有效指每一位均在 0 - 255 之间，且非 0 打头
简单循环思路：三个 for 循环，每次判断当前那位 IP 地址是否有效（范围内加非 0 打头）即可
回溯思路：其实回溯也能做，只要加上 begin 避免使用前面的数字即可

FloodFill类

建议：这类问题不建议修改输入数据，而是设置 visited 数组（标准做法），抽取私有方法。可能会遇到参数很多，是不是都可以写成成员变量的问题，面试中拿不准的记得问一下面试官

图像渲染（中等）

链接：题目链接
描述：输入一个二维数组 nums，给定一个位置 (sr, sc) 和一个新颜色 newColor，将其和其邻近（上下左右）同颜色节点均设置为 newColor 的值。
思路：没啥可写的，反正就上下左右遍历么。

岛屿数量（中等）

链接：题目链接
描述：给定一个二维数组 nums，其中元素值为 1 或 0，分别代表该处为岛屿或水面，所有连在一起（上下左右）的岛屿视为一个岛屿，求岛屿数 num 。
自己的思路：设置一个数组 visited 代表是否访问过该元素和一个方向数组 directions 代表四个方向。然后两重 for 循环，如果当前元素为 1 且没被访问过，则岛屿数 num 加一，然后四个方向遍历（使用 dfs 函数抽取公共部分），每次遇到没访问过且为 1 的元素，其对应位置 visited 都置为 true。当然也可以原地修改 nums 数组，面试时可以询问是否能修改。

被围绕的区域（中等）

链接：题目链接
描述：给定一个二维数组 board，其中元素为 X 或 O，如果一个 O 四周均被 X 所包围（上下左右连在一起的 O 视为一个 O，那么将其改为 X 。请对输入 board 进行修改

自己的思路：写写改改 10 分钟，结果打败 10%，哭了，基本还是设置一个 visited 数组和一个变量 path 保存相连的 O，然后 dfs 函数返回 true 值代表是否四周被包围，然后二重 for 循环么，下面是伪代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

def dfs(char[][] board, boolean[][] visited, List path, int m, int n, int x, int y)
	if !(0 < x < m) || !(0 < y < n)
		return false
	if board[x][y] = X
		visited[x][y] = true
		return true
	flag = true
	if !visited[x][y]
		path.add([x, y])
		visited[x][y] = true
		// (tx, ty) is up, bottom, left, right neibors of (x, y)
		flag &= dfs(board, visited, path, m, n, tx, ty)
	return flag

for i = 1 to m - 1
	for j = 1 to n - 1
		if !visited[i][j] && board[i][j] = O
			if dfs(board, visited, path, m, n, i, j)
				// (x, y) is the item of path
				board[x][y] = X
			path.clear()

官方思路：看了之后我是傻逼。其实我想到了和最外圈相连的 O 一定没有被包围，但思路没转过来。其实可以先对边界的 O 进行 dfs 或 bfs 查找，然后将对应的 O 替换为一个其他字母比如 A ，最后 for 循环整个数组，将 A 替换为 O，将 O 替换为 X。

单词搜索（中等）

链接：题目链接
描述：给定一个字符数组 board 和一个单词 word，求字符数组中是否存在构成 word 的排列，排列是指一串字符，其中前后两个字符在字符数组中的位置是上下或左右相连的。
简单思路：我寻思着这不就是暴力 for 循环么，两重循环遍历数组的两维，然后每一个元素检查四周看是否符合对应的字符，并利用 visited 避免重复寻找，一看官方解答也是这样的，CV一下得了。

字符串中的回溯问题

提示：字符串的问题的特殊之处在于，字符串的拼接生成新对象，因此在这一类问题上没有显式「回溯」的过程，但是如果使用 StringBuilder 拼接字符串就另当别论。

电话号码的字母组合（中等）

链接：题目链接
描述：数组一个仅包含 2 - 9 的字符串，每个字符对应着手机九格输入法的对应几个字母，求由这些字符串可以映射出的所有字母字符串，即模拟手机输入
思路：我寻思着这不就是 for 循环么

字母大小写全排列（中等）

链接：题目链接
描述：给定一个字符串，里面仅包含字母或大小写字母，现在你可以将原先字符串中的字母由大写改为小写或小写改为大写，求所有可能的变换方式。

自己的思路：原本想直接用 StringBuilder 上的，然后一个 begin 避免重复，但失败了。最后利用一个 path 记录变换点的位置，然后每次就重新构造输出字符，当然慢了。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

def dfs(List res, List path, StringBuilder sb, String s, int begin)
	for i = begin to len_s
		if !('0' <= s[i] <= '9')
			path.add(i)
			sb.append(s, 0, path.get(0))
			for j = 0 to len_path
				sb.append(s[path.get(j)] + ('A' - 'a') / ('a' - 'A'))
				if j = len_path
					sb.append(s, path.get(j) + 1, len_s)
				else
					sb.append(s, path.get(j) + 1, path.get(j + 1))
			res.add(sb.toString())
			sb.delete(0, sb.length())
			dfs(res, path, sb, s, i + 1)
			path.remove(path.size() - 1)

res.add(s) // origin s is not included in dfs function
dfs(res, path, sb, s, 0)

更加好的做法是记录下字母的位置，然后对这些位置进行回溯，这道题就变成了子集问题。另外建议把 String 变成 char[]，然后直接改对应位置更加方便。

括号生成（中等）

链接：题目链接
描述：给定一个整数 n ，判断利用 n 个左括号和 n 个右括号可以生成的所有有效括号；

思路：仔细思考后我们可以回溯每次选用的左括号数量和右括号数量，但回溯这个比较烦，所以采用回溯剩余左括号数量和剩余右括号数量，然后回溯函数中 for 循环可选左右括号数即可。但这里需要注意两点：

当可选左括号数等于剩余左括号时，右括号的数量仅可能只有一个，就是所有剩余右括号。因为左括号没了，后面右括号怎么分都是一样的。
为满足有效括号的定义，则已用左括号数应该不小于已用右括号数，即剩余左括号数应该不大于剩余右括号数

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def dfs(List res, StringBuilder sb, int lnum, int rnum)
	for i = 1 to lnum
		for j = 1 to rnum - (lnum - i)
			if i == lnum
				j = rnum
			sb.append('(' * i + ')' * j)
			if i != lnum
				dfs(res, sb, lnum - i, rnum - j)
			else
				res.add(sb.toString())
			sb.delete(sb.length() - (i + j), sb.length())

其他杂

统计子岛屿（中等）

链接：链接
描述：给定两个二维只包含 0 或 1 的数组，一组连在一起的 1 代表一片岛屿，求数组 2 中被数组 1 岛屿完全包含的岛屿的数量。
分析：一开始想复杂了，其实也很简单，只要回溯一遍就够了，只不过回溯过程要返回标志符来表征数组 2 的岛屿是否被数组 1 的对应岛屿完全包含。简单来说，我们回溯数组 2 的岛屿数量，同时判断数组 2 中为 1 处是否有数组 1 对应处非 1。如果有，说明数组 2 当前岛屿没有被数组 1 的对应岛屿完全包含，反之则说明完全包含。

串联字符串的最大长度（中等）

链接：链接
描述：给定一个字符串数组，求一个最长的字符串，该字符串由原字符串数组中的字符串拼接而成，且字符串中的所有字符仅出现一次，返回该字符串的长度。
分析：
- 看到长度我就该想到是回溯的。。。嘛因为只要长度，而且只有小写字母，那就位运算处理一下先，然后记得预先计算下有效数字元素的二进制 1 的个数，因为后续会频繁用到。
- 然后就是回溯问题了，这里用带 begin 的回溯就好，另外判断两个数对应原字符串是否有交集可以用与运算轻松判断。

游戏问题

提示：回溯算法是早期简单的人工智能，有些教程把回溯叫做暴力搜索，但回溯没有那么暴力，回溯是有方向地搜索。「力扣」上有一些简单的游戏类问题，解决它们有一定的难度，大家可以尝试一下。

N 皇后问题（困难）

链接：题目链接
描述：给定一个 n * n 大小的棋盘，你需要在上面摆放 n 个皇后棋子，摆放规则是任意两个皇后不能处在同行、同列或同一斜线，求所有可能摆放方案。
自己的思路：因为任意两个皇后不同行，所以我们只要求解每个皇后能摆放的列的可能就好了，这就是一个普通的回溯问题。其中判断是否可能的同一斜线为判断两个皇后的行数差是否等于列数差的绝对值（因为反斜线列数差是负数）。
续：另外这道题要求返回一个 List = res，List的内容为包含字符串的 List = path，则可以用一个数组 locs 记录皇后所在的列数，另外一个字符数组 s[] = {’.’, ‘.’, ‘.’, ‘.’} 方便用于修改对应皇后位然后添加到 path，最后 res 添加 path 即可。
官方思路补充：官方主要提供了如何在 O(1) 时间复杂度上判断当前皇后位置是否合理的解法，分为基于集合的回溯和基于位运算的回溯两种。

解数独（困难）

链接：题目链接
描述：编写一个程序来解数独，部分空格已经填入空格。除去一般规则，1 - 9 在每 3 * 3 个框内也只能出现一次。

祖玛游戏（困难）

链接：题目链接

扫雷游戏（中等）

链接：题目链接

位运算

概要：位运算题大部分不难，但得想到规律。一般可以考虑异或、前缀和。

异或

异或的几大定律：交换律：a ^ b = b ^ a 结合律：a ^ b ^ c = a ^ (b ^ c) 自反性：a ^ a = 0 a ^ 0 = a 推导出的对称：a ^ b = c ${\to}$ a ^ c = a ^ a ^ b = b

不用临时变量交换两个值

异或解： C 语言不是常用的么，三次异或就够了，这里利用了异或的自反性

1
2
3

a = a ^ b
b = a ^ b // b = a ^ b ^ b = a
a = a ^ b // a = a ^ b ^ a = a ^ a ^ b = b

其实还可以加减法，比如：

1
2
3
4
5
6
7

a = a + b
b = a - b // b = a
a = a - b // a = b

a = a - b
b = b + a // b = a
a = b - a // a = b

找出重复或丢失数据（简单、中等、困难）

描述：1 - 1000 放在含有 1001 个元素的数组里，除了 1 个元素出现 2 次，其他元素都出现两次
虽然 for 循环记录 count 自然能找出，但异或也能做。下面说下简要思路：

$$ \begin{cases} T1 = 1 \oplus 2 \oplus … \oplus n \oplus n \oplus … \oplus 1000 = 1 \oplus 2 \oplus … \oplus 1000 \oplus n \oplus n = 1 \oplus 2 \oplus … \oplus 1000 & \text{T1 为不包含 n 的所有值的异或} \ T2 = 1 \oplus 2 \oplus … \oplus 999 \oplus 1000 = T1 \oplus n & \text{T2 为包含 n 的所有值的异或} \ n = T1 \oplus T2 = T1 \oplus T1 \oplus n = n & \text{n 即为 T1 和 T2 的异或值} \end{cases} $$

变体（简单）：链接现在知道有 1 个出现 1 次，其他均出现 2 次。一样考虑不用额外空间的解法（~~放弃 for 循环吧~~）其实就是全部异或一遍么。
变体（简单）：268, 剑指 53, 面试 17.04 现在知道有一个数没出现，且给定了范围。其实做法和重复数据是一样的。
变体（中等）：链接现在知道有1 个出现 1 次，其他出现 3 次，同样考虑不用额外空间的解法。
- 第一种做法：其实是统计每一位 1 出现的次数（通过右移 k 位后与 1 得到）。对于出现 3 次的数，为 1 的次数要么 3 要么 0；反之出现 1 次的数只可能为 1 或 0。因此对每次得到的出现 1 的次数取余 3 就是只出现 1 次的那个数当前位的值，然后重构就好了。
- 第二种做法：数字电路设计的思想。
变体（中等）：链接这次只出现 1 次的数有 2 个了，其他出现 2 次，同样考虑不用额外空间的解法。
- 解法：诶又没转过弯来。先循环异或整个数组，得到要求的两个数的异或值。因为两个数不相等，所以其异或值必然 0 和 1 混杂，因此只要找到一位为 1（说明这两个数在这一位不同），就可以根据这一位的值对原数组进行分组，那么就变成原题目了么。
变体（困难）：链接这次给出一个少了 2 个数的元素范围在 1 - N 间的数组 nums ，求缺少的两个数，要求时间复杂度 O(N)，空间复杂度 O(1)
- 思路：其实很简单的，凡尔赛一波。首先 N = nums.length + 2。然后分别对 nums 所有元素和 1 - N 所有元素异或得到两个异或值，这两个一异或就是缺少元素的异或值。接上一题的思路，找到第 k 位使得这个异或值该位为 1，然后根据这个分别对 nums 数组和 1 - N 分组异或，就是答案
变体（简单）：链接现在一个 1 - N 的数组其中一个数变成了另外一个数，导致一个数重复一个丢失，要求按序返回重复的数和丢失的数。
- 思路：其实可以用额外空间方法很多么，不用额外空间就异或么；按照上一题的思路可以得到这两个数，不过顺序是随机的，所以要再遍历一遍数组确定顺序。

格雷码（中等）

链接：题目链接
描述：输入 n 代表格雷码的位数，生成一种所有格雷码的排列方案。格雷码是指前后两个数只有一个二进制位不同的码。
思路：别说了，背吧。grayCode(i) = i ^ (i / 2)

两整数之和（中等）

链接：题目链接
描述：不用加减乘除运算符实现加法运算
思路：两整数 a, b, a ^ b 得到每一位无进位相加；a ^ b 得到每一位的进位。定义两个变量 result 和 carry，从第 0 位开始递归，对于第 k 位有 :result = (bit_a ^ bit_b ^ carry) « k + res; carry = bit_a & bit_b | Math.max(bit_a, bit_b) & carry

移位

配对交换（简单）

链接：题目链接
描述：依次交换某个数的二进制位的奇偶位上的值，尽量操作最少
解法：除了直接 and 两个固定数的魔术，可能就是依次移位算连续 2 位上的值然后构造解了吧

替换指定位（简单）

链接：题目链接
描述：给定两个数 N 和 M，给定两个位置 i 和 j (i < j)，从最低位数起，将 N 第 i - j 位替换成 M 对应的 j - i 位二进制表示
解法：一样的依次移位算出各位，然后构造解

颠倒二进制位（简单）

链接：题目链接
描述：颠倒给定的无符号二进制位
解法：逐位颠倒就行，注意 Java 右移应当使用 »>，避免负数右移时左端补 1 。同时可以用分治加速。

下一个数（中等）

链接：题目链接
描述：输入一个数 num，它介于[1, 2^31 - 1] 之间，分别求出大于它中最小的和小于它的最大的两个数，且这两个数的二进制 1 的个数和原数字一样，如不存在，返回 -1。例如输出 2，返回 [4, 1]。
解法：第一种就暴力循环么，从 num + 1 和 num - 1 依次循环，判断当前数和 num 的 1 的是否一样。然后就是比较机智的位运算

总的解释：较大的数是指将第一个非拖尾 0 替换为 1，而后将其后面的连续 1 从最后一位开始填起；较小的数是指将第一个非拖尾 1 替换为 0，而后将末尾的连续 1 填到 0 的后面。

先求出二进制最右边的 1 的位置 (lowbit = num & -x ) (计算机内部使用补码表示，正数补码就是其本身，负数的补码是其绝对值的补码的按位取反再加 1)
求出二进制最左边的 1 也就是消去连续 0 (toZero = lowbit + num)
把 (最右连续 1 长度 - 1) 个 1 搬到全局最优 (num & ~toZero) / lowbit » 1
ps: ~toZero 与 x 进行或运算得到最右连续 1 部分除以 lowbit 后把 1 搬到右边，这里因为进位，所以要右移去掉一个 1

1
2
3
4
5
6
7

def nextOne(int x)
	long lowbit = x & -x
	long toZero = x + lowbit
	return (int)((x & ~toZero) / lowbit >> 1 | toZero)

int mx = nextOne(num), mi = ~nextOne(~num)
return mx > 0 ? mx : -1, mi > 0 ? mi : -1

布赖恩·克尼根（Brian Kernighan）算法

汉明距离（简单、中等）

链接：题目链接
描述：计算两个输入数的汉明距离（二进制位不同的数量）
解法：就两个数异或一下求二进制位为 1 的个数么（异或会保留不同的位为 1）
变体（中等）：链接现在要计算输入数组的所有元素间的汉明距离。其实不还是一样的，只要知道所有数在某一位上为 1 的数量，那么 $result = \sum_{i = 0}^{31} {num_1 \cdot len_{nums} - num_1}$

数字范围按位与（中等）

链接：题目链接
描述：给定两个数，返回两个数表示区间范围内所有数与的结果。
思路：啊没有想出来。。。看了题解，其实就是求所有数字范围内的数字的公共前缀，而所有数字的公共前缀和最大最小两个边界的公共前缀是一样的。那么就依次右移直到两个数相等，然后把公共前缀左移前面右移的位数回去就可以了。
Brian Kernighan 算法：它用于清除字符串最右边的 1 。给定一个数 n ，则 n & (n - 1) 操作会清除 n 二进制位表示最右边的 1。那么我们可以依次清除右边界较大数右边的 1 使得右边界至少不大于左边界。然后两个边界与运算就是答案。

其他

*数组中两个数的最大异或值（中等）

链接：题目链接
描述：给定一个整数数组 nums，返回 nums[i] XOR nums[j] 的最大运算结果，其中 $i\leq j$
思路：首先是一个比较重要的性质，如果 $nums_i \bigoplus nums_j = x$，那么可以得到 $nums_i \bigoplus x = nums_j$ 。而因为异或运算是逐位进行的，设 $nums_{i, j}$ 代表 $nums_i$ 第 j 位二进制位上的数，那么有 $nums_{i, k} \bigoplus x_k = nums_{j, k}$ 。假设 $x_k$ = 1，那么将 x 与 nums 所有元素异或运算，每次运算时判断 $nums_{i, k}$ 是否与异或运算结果相同。如果相同，说明有 $nums_{i, k} \bigoplus x_k = nums_{j, k}$ ，那么 $x_k$ 可以取到 1，反之只能取 0 。再考虑异或运算和取第 k 位，如果用除法加取余则必然计算量繁重，反之用右移则比较便捷。另外每次要记录 nums 元素每一位的结果，同时要方便查找，因此这里有两种方法，分为哈希表法和字典树法。

哈希表法：伪代码如下

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

// x 为目标值，初始值为 0 
int x = 0 
// 最大 2 进制位数
int MAX_LENGTH = 31
HashSet kBit
for i = MAX_LENGTH to 1
	for num in nums
		kBit.add(num >> (k - 1))
	// 从第 MAX_LENGTH 位开始每一位置1，然后往后递推
	next_x = 2 * x + 1
	boolean found = false
	for bit_k in kBit
		if kBit.contains(next_x ^ bit_k)
			found = true
			break
    // 因为每次 next_x 都是继承的，所以每次比较的是到 k 为止的所有位
    // 而非第 MAX_LENGHT - (k - 1) 位
	if found
		x = next_x
	else
		x = next_x - 1
return x

字典树法：暂且没看

找出第 K 大的异或坐标值（中等）

链接：链接
描述：给定一个数组 nums，其大小为 m * n。现在定义一个运算更新数组里的所有值：坐标 x, y 的新值为所有原数组 中坐标 i <= x 和 j <= y 的原始值异或得到的值，求更新后数组中第 K 大的值。
解法：看了题解，原来是我题目没读懂，官方这翻译和示例着实诶。那么问题就变成如果快捷求出每一位的异或值了。定义 f(i, j) 为 (i, j) 处的异或值，那么 f(i + 1, j + 1) = f(i, j + 1) ^ f(i + 1, j) ^ f(i, j) ^ nums[i + 1, j + 1] 然后不就是排个序的事么，散了散了。

形成两个异或相等数组的三元组数（中等）

链接：链接
描述：给定一个数组 nums，求所有三元组 0 <= i < j <= k，使得 nums[i] 到 nums[j - 1] 的异或值等于 nums[j] 到 nums[k] 的异或值
解法：知道了前缀和，然后不就是三重 for 循环的事么，但 $O(n^3)$ 的解法怎么可能最优呢哈哈。设到索引为 i 为止的异或值为 $S_i$
- 二重循环：当 $S_i = S_k$ 时，[i + 1, k - 1] 范围内的任意 j 都是符合要求的（这里用了异或的性质 (a ^ b = c, a = c, -> b = 0, b1 ^ b2 = b, -> b1 = b2)，对应的三元组个数为 k - i - 1，因此只需要枚举 i 和 k 即可。
- 一重循环：从上一方法可以计算得出所有符合条件的 $i_j, k$ 对答案的贡献为： $$\sum_{j = 1} ^ m {k - i_j - 1} = m * k - \sum_{j = 1}^m {i_j}$$ 也就是说遍历下标 k 时，需要知道所有满足条件的下标 i 的出现次数 m 以及他们的和，二者可以用两个哈希表来实现

字符串篇

概要：这里需要注意学习下字符串的读入，因为可能要求自己处理输入输出。
字符串如果都是大写或者小写，可以类似计数排序思路，定义数组计算出现次数。

字符串排序

字符串的排列（中等）

链接：链接
描述：给定两个字符串 s1 和 s2，判断 s2 中是否包含 s1 的排列，即变化后的 s1 是否是 s2 的子串。原字符串只包含小写字母。
滑动窗口法：好吧确实没往这方面想。因为元字符只包含小写字母，也没说是否有重复，所以仿照计数排序定义数组来记录各个字母出现次数，然后划窗，判断两个数组是否相等（好慢啊），当然一个也可以。
双指针法：其实看着和滑动窗口也没啥区别，也是用数组记录各个字母出现次数，然后定义两个指针代表左右区间，再判断区间长度是否和 s1 相同。

自定义字符串排列（中等）

链接：链接
描述：给定两个只由小写字母构成的字符串 s1 和 s2, 其中 s1 中无重复字符。将 s2 中所有在 s1 中出现过的字符按照 s1 中的排列规律排列
解法：就定义数组记录各字符出现个数，然后依次加就好了。

验证外星人词典（简单）

链接：链接
描述：老谜语题了。给定一个字符串代表字典序，给定一个字符串数组，判断字符串数组中的字符串间是否符合字典序（不需要考虑字符串本身是否符合字典序）
解法：首先当然是定义数组方便获得字典序啦。然后我犯傻了，首先小于具有传递性，因此只需要依次判断相邻字符串是否符合即可，不用全部判断。然后我又犯傻了，对于 app 和 apple 这种组合的判断没想到方法，其实定义一个布尔量判断前面是否一样即可。最后的最后，我还是犯傻了，其实不用比较所有位，只要前面的字符串有一位比后一个小，那么这对比较可以直接跳过。

根据字符出现频率排序（中等）

链接：链接
解法：就一个 HashMap 记录次数，然后对 HashMap 排序，最后输出么。

重新排列日志文件（简单）

链接：链接
解法：又是谜语题，描述看链接，题解看官方题解不说了。注意：不需要对每个日志本身进行排序。

字符串匹配

实现 strStr()（简单）

链接：链接
解法：暴力循环或者 KMP 算法

单词规律（简单）

链接：链接
描述：给定两个字符串 pattern 和 S，其中 S 是由一系列单词构成，单词间用空格隔开。判断 pattern中的每个字母是否与 S 中的字母对应规律一致。
解法：就是 HashMap 构建对应关系，然后判断是否有对应关系不一样的么。注意要判断是否存在 key 不一样但 value 一样的情况。另外也可以构建两个 HashMap 来求解。
变体（中等）：链接现在 S 中的单词没有用空格分隔了，但 pattern 只由 a 和 b 组成，另外 pattern 中相同的字母不能表示相同的字符串。思路：其实就是 for 循环 a 能匹配的字符串长度（根据个数判定），从而得出 b 能匹配的字符串长度，然后确定两者匹配的具体字符串，最后不断从原字符串删去对应匹配字符，看看最后能否删完。需要注意的是只存在 a 或 b 的情况应该额外判断。

多次搜索匹配（中等）

链接：链接
描述：给出一个长字符串和一个短字符串数组，求解短字符串数组中所有字符串在长字符串出现的位置
解法：KMP 多次匹配或者字典树或者有限状态机。
字典树：

重复叠加字符串匹配（中等）

链接：链接
描述：给定两个字符串 a 和 b，判断最少重复叠加 a 多少次可以使得 b 变为 a 的子串，若不存在则返回 -1。注意叠加 a 0 次是 “”。
思路：自己想了蛮久的，但没有分好类，诶。首先应该判断 a 和 b 的长短。
- 若 a 不比 b 短，那么要么 b 是 a 的子串，要么 b 是 2a 的子串，要么 b 不是 a 的子串。
- 若 a 比 b 短，那么 a 至少要叠加 $\lceil len_b / len_a \rceil$ 次，因为 a 至少要和 b 一样长，
而 a 最长只能叠加到 $\lceil len_b / len_a \rceil + 2$ 次，因为 b 只可能在两端有额外字母需要叠加来匹配，那么循环就好了。
解法 2 - Rabin-Karp：

回文

最长回文串（简单）

链接：链接
解法：各个字符计数，然后偶数直接加，奇数则加减一，最后判断是否有奇数，有则结果加一
变体（简单）：链接验证回文串，双指针么
变体（简单）：链接验证是否是回文串的排列，统计次数就好了。
变体（简单）：链接验证经过最多一次修改后是否是回文串，一样的套路，只是不相等的时候两种可能都验证下

最长回文子串（中等）

链接：链接
解法 1 ：动态规划。自己想到的解法，但是漏了一点点。设 dp[i, j] 代表 [i, j] 范围的子串是否是回文串，那么有

$$ \begin{cases} dp[i, i] = true \ dp[i, i + 1] = s[i] == s[i + 1] \ dp[i][j] = dp[i + 1][j - 1] \wedge s[i] == s[j] & \text{i != j} \end{cases} $$

解法 2 ：中心拓展算法，就是枚举所有可能作为回文串中心字符（包括两个中心和一个中心两种可能）的可能，然后按照动态规划的转移方程拓展。
解法 3 ：Manacher 算法
变体（中等）：链接求回文子串的数量。一样可以套之前的 3 种解法，不过动态规划好慢啊。
变体（中等）：链接求最长回文子序列的长度。又没彻底想出动态规划的全体，难受。设 dp[i, j] 代表 [i, j] 范围的子串的最长回文子序列的长度，那么有

$$ \begin{cases} dp[i, i] = 1 \ dp[i, j] = dp[i + 1][j - 1] + 2 & \text{s[i] = s[j]} \ dp[i][j] = max(dp[i][j - 1], dp[i + 1][j]) & \text{otherwise} \end{cases} $$

最短回文串（困难）

链接：链接
描述：给定一个字符串 s，你可以在其前面添加任意量的字符使其变成回文串，求添加后变成回文串中最短的那个回文串
解法：第一反应是 dp，毕竟上面两道用了 dp，然后发现自己太 naive 了。然后就莫得思路。看了大佬的思路，次最短的一个回文串应该是将 s 逆序加到 s 前面，但这个肯定不是最长的，因为第一个字母就重复了，比如 “ab” -> “baab”，所以我们要想办法去掉重复，很明显这里去掉逆序或者原序字符串打头/打尾开始的最长回文串就好了。
- 对此一种方法是动态规划（本题二维动规超出内存限制，一维超时）。
- 另一种方法是 KMP，好家伙没想到吧。将原序 s 作为模式串求出 next 数组，然后将逆序字符串与原序进行匹配，当匹配完时，容易知道此时模式串的指针 k 之前的所有字符串就是要删去的字符串。

字符串运算

概要：主要包括字符串加法和字符串乘法或者模拟计算器，乘法就是 Karatsuba 算法或者 FFT 方法，模拟计算器就是栈，转逆波兰式

字符串加法（简单）

链接：链接
解法：就模拟加法么

字符串乘法（中等）

链接：链接
模拟加法：对于乘数，每次选一位对被乘数做乘法，然后每个结果一次做字符串加法
模拟乘法：直接模拟乘法，设两个字符串长度分为 len1 和 len2，那么字符串乘法结果长度不超过 len1 + len2。然后仿照解法一，每次取乘数 1 位与被乘数所有位相乘，每次运算结果直接填到结果数组的对应位置（应该很容易算），需要注意的是每次乘完后进位可能非零。
- 很明显，模拟乘法相比模拟加法少了字符串相加的过程，因此要快不少
Karatsuba 分治算法：分治懂得都懂，主要是复用 ac 和 bd 的结果来达到 $O(n^{log_2 3})$ 的时间复杂度。

$$ \begin{cases} x = a \cdot 10^{p} + b \ y = c \cdot 10^{p} + d \ xy = ac \cdot 10^{2p} + (ad + bc) \cdot 10^{p} + bd \ ad + bc = (a + b) \cdot (c + d) - ac - bd \end{cases} $$

Toom-Cook 分治算法：参考学习链接很显然，既然分成 2 份能够节省时间，我们明显可以分得更多份。常用的是 Toom_3 ，即分成 3份，对应时间复杂度 $O(n^{log_3 5})$ 。对于通常性方法，假设分成 m 份，即

$$ \begin{cases} x = x_{m - 1}|x_{m - 2}|…|x_0 \ y = y_{m - 1}|y_{m - 2}|…|y_0 \ \end{cases} $$

FFT 算法：如果把两个数写成多项式形式，设两个数的系数分别为 $\vec a$ 和 $\vec b$，对应长度分别为 $len_a$ 和 $len_b$ 。对于两数相乘的第 i 位系数，可以得到 $c_i = \sum_{k = 0}^i {a_{k}b_{i - k}}$ ，拓展到全体系数，其实 $\vec{c} = \vec{a} \cdot \vec{b}$，因此可以用 FFT 算法来加速计算它，将时间复杂度降低到 $O(clogc)$，这里的 c 是不小于 $len_a + len_b$ 的最小 2 的整数幂。
Java 中的实现方法：
- Java 7 中，就是用二重循环实现的。源代码：BigInteger - Java7（见 1165 行）
- Java 8 中，根据两个因数的大小，有三种方法实现。源代码：BigInteger - Java8（见 1464 行）
  - 当两个因数均小于 $2^{32 \times 80}$ 时，用二重循环直接相乘
  - 否则，当两个因数均小于 $2^{32 \times 240}$ 时，采用 Karatsuba 算法。
  - 否则，采用 Toom_Cook 算法，时间复杂度为 $O(n^{log_3 5}) \approx O(n^{1.465})$

括号

概要：除去栈，考虑针对平衡问题可以设置两个变量分别表示已遇到左括号和右括号的数量，这样比单设差值能保证有效性

有效的括号（简单）

链接：链接
描述：给定一个只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字符串，判断字符串是否有效。
解法：栈

括号的分数（中等）

链接：链接
描述：给定一个有效括号字符串 S，按规则计算分数：() 得 1 分；两个连在一起的有效括号串得分相加， AB 的得分是 A + B；(A) 得 2A 分。
解法：定义一个倍数 bal，遇到左括号加一，右括号减一，并且判断前者是否为左括号，若是则加上 $2^{bal}$ 的个数，不难证明。

连续最长有效括号（困难）

链接：链接
解法：模拟栈来做。一个栈记录未匹配括号的下标，另一个栈记录已匹配右括号的下标，然后依次比较每个连续区间的括号长度。（有效区间是指另一个栈栈顶下标均大于第一个栈栈顶下标的区间）看了题解计算连续区间时可以在一个栈上做，果然太久没做栈了。
动态规划：其实自己也想过，但状态变量没设好诶。设 dp[i] 为 0 - i 范围内的最长有效括号长度，然后判断的时候每两个一组，但遍历还是逐一进位，那么：

$$ dp[i] = \begin{cases} dp[i - 2] & \text{s[i] = ‘(’} \ dp[i - 2] + 2 & \text{s[i] = ‘)’ & s[i - 1] = ‘(’} \ dp[i - 1] + dp[i - dp[i - 1] - 2] + 2 & \text{s[i] = s[i - 1] = ‘)’ & s[i - dp[i - 1] - 1] = ‘(’} \end{cases} $$

优化的栈模拟：

移除无效的括号（中等）

链接：链接
解法：感觉都是栈的题嘛。还是模拟栈，存储下标，然后依次删除栈中下标对应的元素。

删除无效的括号（困难）

链接：链接
描述：给定一个由小写字母和括号构成的字符串，删除最少数量的括号使得原字符串的括号都有效，求所有可能的结果。
dfs 回溯解法：艰难 debug 出了回溯解法，就是效率呵呵，打败 30% 。关键在于我回溯既没有去重，也没有保证删除最少数量的括号。
- 自己的想法：先把左右侧无效括号删了，然后遍历，遇到括号可加可不加（保证已添加左括号数不小于右括号数），并更新当前已添加左右括号数，遇到字母一定要加，当遍历到字符串末尾且左右括号等额时添加当前路径并返回。这样做无法保证删除最少，所以最后还要处理。
- 官方改进：其实可以事先记录应该删除的最少左右括号数，通过 for 循环么。遇到左括号就加一，遇到右括号时，如果有左括号就左括号减一，否则右括号加一，然后把这两个参数也作为回溯参数放进去遍历，就没有删除不是最少的问题。但是同样没有保证去重。
- 更巧妙的英文站的解法：没看懂。。。
bfs 回溯：看速度还没 dfs 快。。。甚至没我写的垃圾回溯快

唯一字符

概要：面试时要问清楚输入范围，比如是小写字母还是 ASCII 表范围还是 Unicode 字符，当然是用哈希表对这个并无影响。

第一个只出现一次的字符（简单）

链接：链接
描述：给定一个字符串，返回里面第一个只出现一次的字符，不存在则返回单空格。字符串仅包含小写字母。
解法：感觉更像脑经急转弯。。。先计数，然后按照字符串的下标遍历，返回第一个计数为 1 的就好了。
变体（简单）：链接这次找下标，就是同一道题么
变体（简单）：链接这次判断所有字符是否都不同，还是同一道题么

子串（待补充）

计数二进制子串（简单）

链接：链接
描述：给定一个字符串 s，计算具有相同数量 0 和 1 的非空连续子字符串的数量，并且这些子字符串中的所有 0 和所有 1 都是连续的。重复出现的子串要计算它们出现的次数。
傻逼解法：说是中心拓展法，实质上就是 for 循环么
按字符分组：可以将字符串按照连续的 0 和 1 分组，并记录各个分组的 0 和 1 的数量。对于这个计数数组中的两个相邻元素，他们一定代表不同的字符。那么我们只要遍历每一对，然后取每一对中的最小值加上去，那就是最终答案。

重复的子字符串（中等）

链接：链接
描述：给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。
暴力解：原谅我第一个想到暴力 for 循环
字符串匹配：设 S = Ns, $N \geq 2$ ，S + S = 2Ns, 减去开头和末尾的 s，-s + S + S - s = 2(N - 1)s ，$2(N - 1) \geq N$，所以只要判断 S 是否在 -s + S + S - s 中就好了，虽然不知道 s，但取最小值 1 就好了。
KMP解：上一个题解都变成字符串匹配了，那用 replace 不若用 KMP 匹配？甚至还有优化的 KMP方法，想了下，我的 KMP 不配使用优化。

无重复的最长子字符（中等）

链接：链接
描述：给定一个由 ASCII 码组成的字符串，求其中不含有重复字符的最长子串的长度
解法：（原来我的解法叫做滑动窗口么）设定一个计数数组 cnt 和一个当前子串长度值 temp 和一个循环开始点 begin ，每次遇到一个新的字符，根据计数数组判断该元素是否存在。若不存在，则计数数组当前字符处加一；反之更新答案 res（比较 res 和 temp），然后从 begin 开始直到索引处字符为当前字符（循环中对应字符处计数值减一， temp 减一）；最后再把 temp 和 res 比较得到答案即可。

至少有 K 个重复字符的最长子串（中等）

链接：链接
描述：给定一个字符串 s 和一个整数 k，找出 s 中的最长子串，要求该子串中的每一字符出现次数都不少于 k，返回该子串的长度。
解法（分治）：该思路的想法是先统计所有出现次数少于 k 的字符，那么可能的最长字符应该被他们所分割开来，故而只要递归地分割掉每一个出现少于 k 的字符，那就可以求得可能的最长子串的长度。
解法（滑动窗口）：（说实话我是想过的）竟然是枚举最长子串中的字符种类数目！

最长重复子串（困难）

链接：链接
描述：给出一个字符串 S，考虑其所有重复子串。返回任何具有最长可能长度的重复子串。（如果 S 不含重复子串，那么答案为 “"。）
题解：（反正我整不来）

替换字符串（中等）

链接：链接
描述：给定一个字符串 s，你可以替换其中的任意 K 个字符为任意字符，求这样替换后可能的最长子串的长度。
解法：（没想出来呜呜呜）看提示是双指针 + 滑动窗口，但想来想去想不到高效地更新剩余不同字符数的方法。看了题解，原来不同的字符数是窗口的长度减去最大频次数（确实），然后另一个关键点来了。如果这个大于 k ，只要右移左指针并减去对应计数就好了。我的理解是，因为右指针始终在右移，那么左指针右移相当于丢弃当前字符，因为剩余不同字符数一样，虽然这样无法得到真实替换后最大子串的下标索引。

单词

字典中最长的单词（简单）

链接：链接
描述：给出一个字符串数组words组成的一本英语词典。从中找出最长的一个单词，该单词是由words词典中其他单词逐步添加一个字母组成。若其中有多个可行的答案，则返回答案中字典序最小的单词。若无答案，则返回空字符串。
解法（暴力）：for 循环没啥好说的
解法（前缀树 + dfs）：经典了

最长单词（中等）

链接：链接
描述：给定一组单词words，编写一个程序，找出其中的最长单词，且该单词由这组单词中的其他单词组合而成。若有多个长度相同的结果，返回其中字典序最小的一项，若没有符合要求的单词则返回空字符串。
简单思路：先按照单词长度对原数组进行排序（相同时则按照字典序排序），然后依次判断当前单词是否是复合单词即可。
前缀树：做也不是不能做，就是感觉没必要，和简单思路一样，写起来还麻烦，哭了。关键还慢

单词替换（中等）

链接：链接
描述：在英语中，我们有一个叫做词根(root)的概念，它可以跟着其他一些词组成另一个较长的单词——我们称这个词为继承词(successor)。例如，词根an，跟随着单词 other(其他)，可以形成新的单词 another(另一个)。现在，给定一个由许多词根组成的词典和一个句子。你需要将句子中的所有继承词用词根替换掉。如果继承词有许多可以形成它的词根，则用最短的词根替换它。你需要输出替换之后的句子。
解法：startsWith 谢谢
前缀树：确实也能做，不写

单词距离（中等）

链接：链接
描述：给定一个字符串数组和两个字符串，寻找两个字符串在字符串数组中的索引下标间的最小距离。如果寻找过程会重复多次，且每次寻找的单词不同，你可以对此优化么？
解法：一个解法当然是一次遍历，然后比较两个字符串的所有索引间的每个距离啦。但如果考虑到多次寻找，那还是要用哈希方法（建立一个 map 保存索引位置，然后二重循环所有索引）

二叉树

熟练掌握中序遍历、先序遍历、后序遍历的迭代版本，手撕二叉搜索树，掌握神奇的 Morris 遍历。

二叉树的公共祖先（中等）

链接：链接
解法1：我们可以将原问题转化为判断某个节点是否是二叉树的公共祖先的问题。设 $f_p$ 代表节点 f 是 p 的祖先，则两个节点的最近公共祖先 f 满足为：$(f_p \ and \ f_q) \ or \ ((f = p \ or f = q) \ and \ (f_p \ or \ f_q))$ 。那么只需要进行 DFS ，找到的就必然是最近公共祖先。

把二叉树搜索树转换为累加树（中等）

链接：链接
描述：给出二叉搜索树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。
分析：
- 一个方法是反中序遍历（右、根、左），然后维护一个变量 adder，每次弹出的时候给当前节点加上 adder，adder 变为当前节点值。因为这是二叉搜索树，所以弹出节点值在原树中一定是从大到小的。
- 还有神奇的 Morris 遍历。

其他标签题记录

单调栈

子数组最小乘积的最大值（中等）

链接：链接
描述：给定一个正整数数组，求一个子数组，使得其有最大的最小乘积，最小乘积是指该子数组的最小值与子数组元素和的乘积，返回该最小乘积。
分析：
- 针对这个问题，先从暴力来说，我们可以枚举子数组和，也可以枚举最小值，但很显然，枚举子数组和比较复杂，我们选择后者
- 而后对于枚举最小值，我们需要一个最长子数组，使得该子数组的最小值为该最小值
- 而针对这个问题，我们可以利用单调栈来得到，由于要得到两侧，所以要左右都遍历一次，得到所有索引位置处的左右两侧位置
- 最后遍历所有元素即可，同时为了快速得到子数组和，利用个前缀和即可。

去重重复字母（中等）

链接：链接
描述：给定一个字符串，试对所有字符进行去重，并保证输出得到的字符串字典序最小（保证相对位置不变）

分析：

首先思考一个问题，给个一个字符串，如何去掉一个字符 ch ，使得其得到的字符串字典序最小？容易想到是找到最小的 s[i] > s[i + 1]，然后删除 s[i]，我们称其为关键字符

那么一个直观的思路是不断删除这样的字符，这可以用单调栈来实现。但我们需要保证被删除的字符删除后后面还有对应字符，因此引入计数数组和布尔数组 visited ，先得到每个字符的数量，遍历时如果当前字符已经在输出答案中，则计数数组中对应值减一即可；反之判断是否为关键字符且后续是否还有关键字符，若有则不断删除关键字符，反之什么也不做。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

int[] cnt = new int[26]
boolean[] added = new boolean[26]
for ch in str
	cnt[ch - 'a']++
for ch in str
	if !added[ch - 'a']
		while(!stack.isEmpty() && result[-1] > ch)
			if cnt[result[-1] - 'a'] > 0
				added[result[-1] - 'a'] = false
				result.remove(result[-1])
			else
				break
		added[ch - 'a'] = true
		result.append(ch)
	cnt[ch - 'a']--

移掉 K 位数字（中等）

链接：链接
描述：给定一个非负字符串数字，而后移除掉 K 位数字，若数字不够则返回 “0”；另外数字不能包含前导零，例如 “10200” 移除 1 位应该是 “200”。返回最小的数字。
分析：因为给定是正数，那么怎么移除后会最小呢？当然是移除第一个 s[i] > s[i + 1] 中的 s[i]，然后去除前导零。每次移除 k 减一，遍历完后如果 k 不为 0 且 result 长度非 0，则倒着继续删除（因为我们的 result 是单调递增的）。最后注意如果 result 长度为 0，本题应该返回 “0” 。

最大宽度坡（中等）

链接：链接
描述：给定一个整数数组，求一个二元组 (i, j) ，满足 i < j && A[i] <= A[j]，求最大的 j - i 。
分析：
- 结果是单调递减栈诶。首先找到以 A[0] 为栈底的单调递减栈，然后倒序遍历数组，求最大的坡。为什么从 0 开始 $\to$ 因为要让 i 尽量小；为什么没有考虑不在单调栈里的数 $\to$ 假设某个数 j 不在单调栈中，那么必然有 k < j 且 A[k] < A[j] ，那么这样得到的宽度坡必然是 A[k] 这边更大，因此不用考虑

表现良好的最长时间段（中等）

链接：链接
描述：给定一个数组 hours，求一个子数组，使得子数组中大于 8 的元素个数多于不大于 8 的元素个数，返回该子数组的最大长度
分析：
- 单调栈法：首先自然是将其转化一下，同时变为一个前缀和数组。那么原问题就变成了求 i, j，其中 hours[i] < hours[j]，并使得 j - i 最大。由于这里已经是前缀和数组了，所以可以直接用最大宽度坡的方法。但需要考虑下边界情况，因为我们这样求是左开右闭的，为了将左边也包括进去，需要先在栈里放入一个 -1 元素作为栈底才对。
- 哈希表法：同样是利用前缀和的思路。我们维护一个 sum 变量，如果 sum > 0，那么 res = i + 1，因为从 0 开始的必然是最长的。反之如果 sum <= 0，若表中无该 sum 值则置入（因为我们要求最长的，已经有了再放入只会减少长度），而后看表中是否有 sum - 1 存在（为什么选 sum - 1，根据我们无则更新原则，更小的数对应的索引必然更大，因此选 sum - 1 得到的长度最长），若有则比较二者间的长度和当前最大长度。

子数组的最小值之和（中等）

链接：链接
描述：给定一个数组 nums，求 $sum(min(subArray(nums)))$，即其所有子数组最小值之和。
分析：
- 左右边界法。这个是想到了，但又被重复缠住了手脚。为了避免重复，我们要求取以 nums[i] 为当前子数组中最右且最小的元素，这样就不会重复了，即求 min(j), 使得 A[j] $\to$ A[i] >= A[i] 和 max(k)，使得 A[j + 1] $\to$ A[k] > A[i]。那答案即为 $sum_{i = 0}^{len_{nums} - 1} {(k - i) * (i - j + 1) * nums[i]}$ 。
  - 对于左边界，因为是大于等于，所以采用倒序遍历和单调递增栈即可，而当遍历完数组后，栈内剩余索引对应的左边界显然就是栈顶值。
  - 对于右边界，因为是大于，所以采用正序遍历和严格单调递增栈即可，而当遍历完数组后，栈内剩余索引对应的右边界显然就是栈顶值加一。
- 维护最小值栈法。考虑 min(nums[i : j + 1] = min(nums[i : j], nums[j + 1]))。我们维护一个严格单调递增栈，栈内记录了以当前元素为最右且最小值的子数组的最长长度，并维护一个 dot 变量代表以该元素结尾的所有子数组的最小值之和，那么：
  - dot = dot + nums[j + 1] * count(nums[j + 1]) if nums[j + 1] > stack.peek().value
  - dot = dot - nums[k] * count(nums[k]) + nums[j + 1] * count(nums[j + 1] + … + nums[k]) if nums[j + 1] <= stack.peek().value; k is where nums[k] >= nums[j + 1]
  - 那么最后的答案 res = sum(dot)
  - 分析一波，如果当前值比栈内值大，那么以当前值结尾的所有子数组的最小值之和就是当前值加上之前所有子数组的最小值之和，比如[1, 7]，dot[0] = 1, dot[1] = 1 + 7 * 1 = 8
  - 而如果当前值比栈内值小，注意到我们求得的是以该元素结尾的所有子数组最小值之和，而dot恰好也代表这个，因此对于前面几个不比他它的栈内元素，我们要把它们的dot部分减掉，然后在当前值的数量上加上对应数量再加，比如[1, 7, 9, 4]，dot[0] = 1, dot[1] = 1 + 7 * 1, dot[2] = 1 + 7 * 1 + 9 * 1, dot[3] = 1 + 7 * 1 + 9 * 1 - 7 * 1 - 9 * 1 + 4 * 3

找出最具竞争力的子序列（中等）

链接：链接
描述：给定一个整数数组 nums 和一个正整数 k，返回长度为 k 的最具竞争力的子序列。给定两个同样长度的子序列 a 和 b，如果在 a 和 b 第一个不同的元素处 a 的元素更小，则 a 比 b 更有竞争力。
分析：稍加分析就可以得知利用一个严格单调递增栈即可。依次遍历数组，维护单调栈，需要注意的是不要让栈的元素和剩余所有元素总数小于 k，同时最后栈的长度偏长时依次出栈到只有 k 个。

132 模式（中等）

链接：链接
描述：给定一个整数数组 nums，判断数组中是否存在三元组 (i, j, k)，使得 i < j < k 但 nums[i] < nums[k] < nums[j]。
分析：这种有多个参数需要枚举但时间复杂度又有要求的，往往采用枚举两个，然后优化枚举其他参数的方法。
- 自己超时的枚举 k 的方法。首先求出以 nums[k] 为最大值的左右边界，这个可以通过单调栈遍历两遍得到。然后判断如果 left[k] < k and right[k] > k，二重循环 i 和 j，这样做会在最后一个贼长的用例超时。
- 能过的枚举 k 的方法。实际上我们可以倒过来思考，既然 nums[j] > nums[k]，那么我们能否在枚举 k 的同时得到 j 呢？答案是可以的，比如使用单调递减栈，让被弹出来的数当做 k，那么一定满足 nums[k] < nums[j]，同时 k > j，最后便只需要满足 nums[i] < nums[k] 即可。所以整的流程是初始 nums[k] 为极小值，然后倒序遍历，维护一个单调递减栈，每次遍历先判断 nums[i] 是否小于 nums[k]，而后维护更新单调栈和 nums[k] 的值即可。

最短无序连续子数组（中等）

链接：链接
描述：给定一个整数数组 nums，找出一个最短无序子数组，使得对其进行升序排序后整个数组都是升序排序的，返回该子数组的长度；
分析：我是傻逼，甚至没看懂 11 天前的代码，笑死了。
- 直接排序确定左右两端么，这真的不是脑筋急转弯么？更快点可以用计数排序。
- 第二个也是通过两次遍历确定左右两端，算是用了单调栈的思想吧。
- 另外也是一次遍历，除去特殊情况（要删除的子数组在两端），可以将原数组分成 3 份，A, B, C，容易知道 $A[i] \leq B/C[j] $，而 $C[i] \geq A/B[j]$。设左右端点分别是 left, right, 对应值分别是 min, max。为了得到 left 和 min，可以倒序遍历数组，如果 nums[i] >= min, left = i；反之 min = nums[i]，因为到了左端有序区后不会再更新 left。类似的，对于 right 和 max，可以正序遍历数组，如果 nums[i] <= max, right = i；反之 max = nums[i]，因为到了右边后也是不会再更新 right。

二叉搜索树的后序遍历序列（中等）

链接：链接
描述：给定一个整数数组，判断它是不是某个二叉搜索树的后序遍历结果，约定二叉搜索树中没有相同的两个元素。
分析：
- 单调栈分析。后序遍历是 left -> right -> root，倒过来是 root -> right -> left，我们可以维护一个单调递增栈，那么当遍历到 left 时出栈的就是右侧或根节点，因此可以通过判断当前元素是否大于出栈的这个元素（我们维护一个变量）来判断。这个变量初始为最大值，如果是正确顺序，那么 right 节点会先顺利入栈，然后在遇到 left 节点时不断弹出 right 节点并更新该变量。而从宏观来看该节点必然是后续节点的根或右侧节点，因此总会比后续节点大。这便是判断依据
- 简单递归分析。由于后序遍历末尾是 root，前面是 left 和 right，而 left 比 root 小，right 比 root 大，因此可以找到分界点，然后判断两侧的 left 和right 是否合理。

叶值的最小代价生成树（中等）

链接：链接
描述：给定一个正整数数组 nums，其值为某二叉树的中序遍历中的叶节点结果，同时该二叉树的所有节点要么是叶节点，要么有 2 个子节点，同时所有非叶节点的值为左右子树的叶节点的最大值的乘积。求所有可能二叉树中非叶节点值的累加和最小的那个，返回最小累加和。
分析：
- 考虑一个区间 i - j，我们可以将其分成根节点的左子树节点 i - k 和右子树节点 k+1 - j，因为数组中的数都是叶节点的值。设所求值为 dp[i, j]，显然有 dp[i, j] = dp[i, k] + dp[k + 1, j] + max(i, k) * max(k + 1, j)，三个部分分别代表左子树非叶节点值的和和右子树非叶节点值的和，以及根节点的值。max(i, j) 可以通过二重循环得出，而 dp[i, j] 可以根据三重循环得出，但要注意倒序遍历。
- 任选两个相邻的数对进行合并，相当于加上它们对应根节点的值。而当计算其他叶节点或子树与该子树的根节点的值时，显然该子树提供的乘子是这两个数的最大值。换句话说，我们计算累积和就是不断选两个相邻的数，累加乘积到答案，然后删去较小的那个。那么，显然让小的和小的相乘最好，因此可以维护一个单调递减栈。每次遇到大于栈顶的数时，弹出栈顶，并判断新栈顶和当前数的大小（如果有的话），取小的那个数和旧栈顶相乘累加到答案上。这样只需要一次循环，但不要忘记遍历完后若栈内元素大于 2 还要继续累加。

双指针问题

A + B + C + … + N = target 问题总结

针对这类问题，暴力必然是不行的，常用的做法是转换为 A + B + C + … + N - 2 = target - (N - 1 + N) 的问题，而后针对右边部分进行双指针，这样原本暴力循环的 $O(n^N)$ 时间复杂度就可以近似为 $O(n^{N - 2})$ 时间复杂度。

三数之和（中等）

链接：链接
描述：给定一个整数数组，求所有不重复且和为 0 的长度为 3 的子序列，返回所有的子序列。

分析：

照例是先排序数组。暴力来说是 $O(n^3)$ ，而且还要去重。那首先要去重，这个可以程序实现，简而言之就是三个数字都不能重复使用

1
2
3
4
5
6
7
8

for first = 0 to n - 2
    if first = 0 or nums[first] != nums[first - 1]
        for second = first + 1 to n - 1
            if second = first + 1 or nums[second] != nums[second - 1]
                for third = second + 1 to n
                    if third = second + 1 or nums[third] != nums[third - 1]
                    	if nums[first] + nums[second] + nums[third] = target
                            add to result list

但这样还是 $O(n^3)$ 的时间复杂度。注意到我们排序过数组，所以当 second 选了更大的元素后，third 元素一定会更小，因此 second 和 third 可以用双指针来整，近似复杂度为 $O(n^2)$

1
2
3
4
5
6
7
8
9

for first = 0 to n - 2
    third = n
    if first = 0 or nums[first] != nums[first - 1]
        for second = first + 1 to n - 1
            if second = first + 1 or nums[second] != nums[second - 1]
                while third > second && nums[first] + nums[second] + nums[third] > 0
                    third--
                if third > second && nums[first] + nums[second] + nums[third] = target
                    add to result list

四数之和（中等）

链接：链接
描述：给定一个整数数组，求所有不重复且和为 0 的长度为 4 的子序列，返回所有的子序列。

分析：

照例是先排序数组，然后仿照三数之和的做法，可以写出三个 for 循环的题解，注意这时候 forth 应当定义在 second 的循环而非 first 的循环下，因为我们是对 third 和 forth 进行双指针，而 forth 是随 third 变化的，因此要固定其他变量 first 和 second。这个方法能过，就是有点慢，打败 30% 不到。

其实真正的双指针是直接只 for 循环 first 和 second，然后对 third 和 forth 进行双指针，即 third = second + 1, forth = n - 1。另外其实有些循环可以避免，理解起来并不难。这种方法算是主流方法吧，打败 98% 左右。

1
2
3
4

1 nums[first] + nums[first + 1] + nums[first + 2] + nums[first + 3] > target   --> break
2 nums[first] + nums[n - 1] + nums[n - 2] + nums[n - 3] < target   --> continue 
3 nums[first] + nums[second] + nums[second + 1] + nums[second + 2] + nums[second + 3] > target --> break
4 nums[first] + nums[second] + nums[n - 1] + nums[n - 2] < target  --> continue

延伸拓展：其实从三数之和和四数之和问题不难拓展到 n 数之和问题，核心在于对于最后两个数字采用双指针遍历来减少 $O(n^2)$ 的时间复杂度至 $O(n)$ 的时间复杂度。

四数之和 II（中等）

链接：链接
描述：现在给定的是四个数组，求所有索引四元组 (a, b, c, d)，使得 A[a] + B[b] + C[c] + D[d] = target，返回四元组的数量。
分析：
- 刚做了四数之和，上来就是一个排序 + 双指针，又因为是索引，所以用了 TreeMap，理论渐进时间复杂度为 $O(n^3)$，然后就超时了。。。
- 然后看了题解，原来是转换为 A + B = -(C + D) 子问题的做法。直接整个HashMap记录 A + B 的结果，那么只要两个 $O(n^2)$ 的过程就好了。

隐式二分问题

可移除字符的最大数目（中等）

链接：链接
描述：给定一个模式串 p 和一个匹配串 s 和一个数组 r，给出一个最大的 k $\in$ [0, len_r]，使得删除 p 中 k 个索引为 r 中前 k 个元素的情况下 s 仍然是 p 的子序列。
分析：
- 首先是删除方面，直接该字符串显然很烦很难写，其实可以采用定义一个布尔数组的方式表示对应索引处的字符是否被删除，这样可以免去很多判断逻辑。
- 然后是要想到这个删除是个二值问题。简单来说，给定满足条件的 k , 那么删除前 k - 1 个的情况下 s 也是 p 的子序列， k - 2, k - 3, … 也同理；另一方面， k + 1, k + 2 则不满足 s 是 p 的子序列。所以我们可以用二分的方法加速搜索。
- 另外二分需要注意的是，边界可能出现在两端的情况。

最小体力消耗路径（中等）

链接：链接
描述：给定一个正整数二维数组 heights，你需要从左上方走到右下方，试寻找一条最小体力消耗路径，体力消耗是指当前路径所有相邻值之间的差的绝对值的最大值，返回该最小体力消耗。
分析：
- 又没看出这是二分问题。。。可以看出，给定一个体力消耗，每次都走体力消耗小于该阈值的路径，要么能走到目的地，要么不能，那么这就是个二分搜索问题。而判断是否能走到则用 DFS 即可。需要注意 left = -1，right = max(heights)
- 并查集做法：这道题也可以看成左上角和右下角的连通问题。我们先计算得到所有两两相邻元素间的体力消耗，而后对其进行排序。再根据体力消耗对这些元素进行并查集操作。而后每次合并时，如果右下元素和左上元素在同一集合了，那当前的体力消耗即为答案。本题并查集并没有二分快。
- 另外也可以用 dijkstra 方法。

最长重复子串（困难）

链接：链接
描述：给定一个字符串，求其所有重复子串中最长的子串；
分析：又没看出这是二分问题啊。。。给定最长重复子串长度为 l，则必然存在长度为 l - 1 的重复子串，那么可以进行二分搜索。之后关键就是如何尽量快的判断是否存在长度为 l 的重复子串问题。

前缀和问题

环形子数组的最大和（中等）

链接：链接
描述：现在连续子数组可以从数组末端链接到前端了，但每个子数组最多包含原数组中的每个元素一次。
自己的解法（就是好慢啊）：
- 既然是环形，那么我在原数组 nums 后面叠加 $len_{nums} - 1$ 个数（实际并不需要创建新数组，只要遍历时索引取余数组的长度就好了）然后仿照之前的非环形数组进行遍历么，但是为了避免重复使用单个元素，定义一个 start 变量表示当前子数组的起始点。另外注意更新 start 时应当保证 start < $len_{nums}$ 。这是因为如果 start 大于 $len_{nums}$ ，后续的遍历就重复了。
- 如果遍历时索引 $i \ % \ len_{nums} \neq start$ ，那么正常更新就好了。
- 反之则把 start++，相当于把原本位于左边的数挪到右边而已。但可能存在这个数是负数需要舍弃的情况，但又不一定是当前负数舍弃，比如 [-3, 4, …] 这种的，所以我们的状态变量 dp 设置为 2 维，第 2 维的第一个表示可能舍弃当前数的状态，第二个代表一直拿着当前数的状态。另外要设置一个状态表示是否扔过，因为如果扔过，那么就只能沿着当前状态一直扔或没扔状态的第一次扔。
- 设状态变量 dp[i, j]。dp[i, 0] 代表以 nums[i] 结尾的最大子数组和，dp[i, 1] 代表在 $i > len_{nums}$ 且有重复后一直不扔掉当前数的最大子数组和，那么：

$$ dp[i, j] = \begin{cases} \begin{cases} max(dp[i - 1, j] + nums[i \ % \ len_{nums}], nums[i \ % \ len_{nums}]) & j = 0 \ dp[i][0] & j = 1 \end{cases} & i \ % \ len_{nums} \neq start \ \begin{cases} dp[i - 1][1] & j = 1 \ max(dp[i - 1, 0], dp[i - 1, 1]) - nums[i \ % \ len_{nums}] & thrown = true \ dp[i - 1, 0] - min(0, nums[i \ % \ len_{nums}]) & thrown = false \end{cases} & otherwise \end{cases} $$

第一种思路：
- 环形数组最大值分两种情况，一种是不跨越边界的，另一种是跨越边界的。
- 第一种不用多说，第二种因为是环形数组，其实可以转换成比较数组总和 - 连续子数组最小值的问题（真是奇妙）和连续子数组最大值的问题，需要注意的是当连续子数组最大值为负数时应该直接返回，举个例子 [-1, -2, -3]，max = -1, min = -6, total = -6 ，我们不能比较 total - min 和 max 而是应该直接返回 max 才是正确答案。
前缀和 + 优先队列：好像跑偏了哈哈。

装包裹的最小浪费（困难）

链接：链接
描述：给定一个一维包裹数组 packages 和一个二维箱子方案数组 boxes，其中每种方案的一维箱子数组 box中的箱子大小各不相同。你需要从 boxes 数组中选出一组方案，使得能装下所有包裹的浪费空间最小。规定一个箱子只能装一个包裹，因此浪费是指对应箱子的大小减去包裹的大小。
分析：本来都是顺着思路做遍历包裹么，这样做只能过 30 个用例就超时了。但注意到题目中说明箱子大小各不相同，因此会联想到二分，从而顺带联想到遍历箱子并二分查找比他小的包裹。另外为了优化计算，可以进一步引入包裹数组的前缀和，进一步减少时间。另外这里二分要注意 packages 数组可能会有重复，因此不能直接用原来的二分。

使二进制字符串字符交替的最少反转次数（中等）

链接：链接
描述：给定一个长度为 n 的只由 0 和 1 组成的字符串，你可以任意顺序执行以下两种操作任意次：
- 操作一：删除某个字符并将其添加到末尾
- 操作二：将某个字符反转，即 0 变 1，1 变0
求使得输入字符串是交替的（即 1 的两侧都是 0 ，0 的两侧都是 1）的最少次数。
分析（据说这种题就是要逆向思维）：
- 当输入字符串长度为偶数时，最后结果一定是 101010… 或 010101… 。对于前者，即便把首位 1 放到末尾也是正确的，因此我们只需要考虑通过第二种操作的变换，然后取最小值
- 而当输入长度为奇数时，进行操作一会导致两个 0 或 1 连在一起，因此需要考虑通过交换一次位置来得到最小的交换次数，故而这里联想到前缀和数组与后缀和数组。
- 设 l[i, 0] 和 l[i, 1] 分别代表左边以 0 和 1 开头时坐标 0 ~ i 的反转次数；r[i, 0] 和 r[i, 1] 代表右边以 0 和 1 开头时坐标 n ~ n - i 的反转次数。那么可得：
$$ res = \begin{cases} min(l[n][0], l[n][1]) & n = 2k \ min(l[i][0] + r[n - i - 1][1], l[i][1] + r[n - i - 1][0]) & n = 2k + 1 \ & \ i = 0 \to n \end{cases} $$

向下取整对和（困难）

链接：链接
描述：给定一个数组 nums，返回数组中所有元素对（两个元素的索引不同即算不同，即便元素值一样，例如 [0, 1] 和 [1, 0]）两两相除后向下取整的结果。
分析：
- 暴力法就是双重 for 循环么，稍微改善一点就是先用 TreeMap 记录下，这个超时，通过了 18 个用例。
- 另一个方法是用二分来优化，首先排序，然后二分查找每一项的倍数（当大于最大值时结束）所在的最大小标，这个更好点，通过了 48 个用例。那继续用空间换时间，避免二分查找的 log n 时间。
- 首先利用计数排序那一套整出个计数数组，之后遍历所有数，对于每个数 num ，判断 [num, num * 2 - 1], [num * 2, num * 3 - 1] … [num * k, max] 间的倍数关系并累加。

表现良好的最长时间段（中等）

链接：链接
描述：给定一个数组，定义元素值大于 8 为类型一，反之为类型二。求数组的一个最长连续子数组，使得其中类型一的数量严格大于类型二。
分析：
- 首先考虑求平均值，但可能出现 [0, 9] 这样的，所以改为将大于 8 的变为 1，其他变成 0，那么判断的时候只要判断 pre[i] - pre[j] > ? (i - j) / 2 即可更新。就是速度好慢，甚至没有暴力快（哭）。
- 发现题解里都是用的 1 和 -1，思考一会确实比 1 和 0 方便，改了之后确实和暴力一个量级了。
- 另外因为是 $O(n^2)$ 的时间复杂度，那就考虑空间换时间，用一个 HashMap 记录值对应的下标，就能只扫描一趟了。注意为了获得最大值，我们应当只在 Map 中不存在对应 key 的时候放入对应 key-value 而不应该更新 value。具体逻辑即：如果 sum > 0，result = i + 1，否则判断有无 sum - 1 这个 key，有则判断 max(result, i - map.get(sum - 1))；
- 还有一种单调栈做法。我们维护一个单调递减栈，然后倒序遍历数组，如果当前元素比栈顶大，则判断更新 result，并出栈栈顶元素，直到栈为空或栈顶元素比其大。

每个元音包含偶数次的最长子字符串（中等）

链接：链接
描述：给定一个字符串，求其的一个最长子字符串，使得其中所有元音字母的个数都是偶数，返回这个最长子字符串的长度。
分析：
- 一开始想着 5 个这不是为难我么，然后想到可以用二进制位来表示，进而联想到异或运算。具体来说，5 个元音字母每人一位，遇到相同的则异或对应位为 1 的数（1 ^ 1 = 0, 0 ^ 1 = 1），然后就是标准前缀和问题了。如果 sum = 0 就更新 result，反之则判断 HashMap 是否包含 sum，包含则判断更新 result，反之则放入 sum - i 键值对。
- 看评论区第一竟然是动态规划，惊了。但其实和前缀和的做法是一样的么。

最长的超赞字符串（困难）

链接：链接
描述：给定一个字符串，求其的一个最长子字符串，使得其的排列是回文字符串，返回这个最长子字符串的长度。
分析：
- 上来还是前缀和 + 哈希表那套，一样的二进制位和异或运算。只不过更新 result 改为：如果奇数位数量少于 2 就更新 sum，反之则枚举哈希表中所有奇数位比当前 sum 多 1 个或少 1 个的数（其实就是让 sum ^ (1 « i), i in [0, 9]），然后判断更新 result = max(result, i - map.get(subSum))。而对 map 的更新，与上面不同的是，只要 map 中不包含 sum，就放入 sum - i 键值对。话说我的解法还是慢。
- 看了官方题解发现自己理解还是不够透彻，其实没必要计算奇数位的数量。与之前一样，如果哈希表包含则更新 result= max(result, i - map.get(subSum))，否则将 sum - i 键值对放入 map。然后继续枚举哈希表中所有奇数位比当前 sum 多 1 个或少一个的数，再判断更新 result 即可。官方的题解耗时是我的一半，还是牛啊。

构建回文检测串（中等）

链接：链接
描述：给定一个字符串 s 和一个 query 数组，让你判断 [query[i, 0], query[i, 1]] 范围的字符串子串重新排列后替换至多 query[i, 2] 个字符后是否是回文串。给定的都是小写字母。
分析：
- 可以重排的检测回文串很简单，就统计出现次数为奇数的个数么。另外可以发现替换的最大次数 k 不会大于奇数的一半。那么只需要想到一种能快捷统计出现次数为奇数的方法就好了。
- 由于给定的是一个范围，所以我们期望的一种运算应该是具有传递性的，那么首先想到了异或运算。另外需要找到一种比较好的映射函数将小写字母映射到数字。单纯减去 ‘a’ 的映射容易验证难以使用，因此这里采用 $f(x) = 2^{x - a}$ 的映射，这样只要统计位为 1 的个数即可，统计次数也是常数时间。

和为 K 的子数组（中等）

链接：链接
描述：给定一个可能包含负数的数组，求其所有和为 K（可正可负）的连续子数组的数量
解法一： for 循环就别说了，话说这题竟然能过
解法二（前缀和 + 哈希）：也不算什么高明方法，看了下，就是用一个 HashMap 保存了 sum(0 - j) 的个数，扫描时只要判断 map 中是否包含 sum(j) - k，包含则加上其对应的个数。故而一次扫描即可，典型的空间换时间。

统计优美子数组（中等）

链接：链接
描述：给定一个数组，返回数组中所有包含奇数个数为奇数的子数组的数量。
分析：还是前缀和么，本质和上面那道题一样，奇数为 1，偶数为 0。我甚至怀疑 for 循环也能过。

跳跃游戏 IV（中等）

链接：链接
描述：给定一个仅由 0 和 1 组成的字符串 s，你一开始位于索引 0 的位置，每次你可以跳 [min, max] 步，如果对应索引处字符为 0，则你可以跳到那里去。判断你是否能跳到最后一个索引处。
分析：我以为是 DP，结果还是前缀和问题。主要思想是利用前缀和数组 pre 保存当前位置之前总共有多少个可以到达的位置。那么对于索引 i ，能到达该位置的条件是：
- s[i] != ‘1’ && pre[i - min] - pre[i - max - 1] > 0 即当前位置非 1，且其前一跳区域中有可到达的点。

查询差绝对值的最小值（中等）

链接：链接
分析：
- 这里的前缀和 pre[i, j] 定义为原数组前 i 个数中包含数字 j 的个数，因为本题限定了原数组元素范围为 1~100，所以可以这么整，然后就是暴力了。
- 另外暴力时需要注意，因为我们只关心差绝对值的最小值，因此不需要遍历所有元素对，而是按一个方向轮询遍历即可，因为答案一定出自这里。

同时需要前缀后缀信息

寻找数组的中心下标（简单）

链接：链接
描述：给定一个数组，求一个索引，使得其左边（不包括该索引）和右边（不包括该索引）的子数组值相等，返回最小的那一个，若不存在则返回 - 1。
分析：就标准前后缀和就能过么。当然也可以先求数组总和，然后利用左数组和等于右数组的特性，只遍历前缀和，这样更快一点点。

字符串的好分割数（中等）

链接：链接
描述：给定一个字符串，求所有分割方案，使得分割后两侧的字符串的不同字符的数量相等，返回分割的数目。
分析：
- 就从前后缀和角度考虑，利用两个数组分别记录 [0, i) 和[i, last] 中不同字符的数量，然后遍历即可得到答案，不同字符的数量计数可以使用 Map 来实现。不知道为什么才打败10%，玄学。

三个无重叠子数组的最大和（困难）

链接：链接
描述：给定一个数组和一个长度 k，求三个互不重叠且长度为 k 的子数组的最大和，返回三个子数组的开头索引值。如果有多个相同的组合，选择字典序最小的那个。
分析：
- 首先是自己的朴素解法。设状态变量 dp[i, 3] 分别表示前 i 个元素中 1 个子数组、2个子数组和 3 个子数组的最大值，然后容易推出状态转移方程，只不过是三重循环，感觉和暴力没啥区别，哭，勉强过了，打败 5% 。
- 然后看了评论区大神，更好的做法是固定中间的数组位置，然后找两边。具体做法是先分别求出前缀 left和后缀 right和数组，left[i] 代表 [0, i] 范围内以该索引值开始的子数组具有最大值和最小字典序，right[i] 代表 [i, len - 1] 范围内衣该索引值开始的子数组具有最大值和最小字典序。然后遍历中间子数组的开始索引，判断更新答案数组和最大和，即可得到最终答案。（时间比我快了400倍。。。）

前缀积

概述：主要考虑做除法时除以 0 的问题

和可被 K 整除的子数组（中等）

链接：链接
描述：给定一个可能包含负数的数组，返回数组中所有和可以被 K 整除的子数组的数量。
分析：一开始我就是普通前缀和，但我发现这样没法处理负数的情况。看了题解发现可以保存前缀和取余 K 的数量（负数则加 K），因为有同余定理，这样确实就一下子开朗了。

使数组和能被 P 整除（中等）

链接：链接
描述：给定一个正整数数组 nums ，给出一个最短子数组，使得移除该子数组后剩余数组的和能被 P 整除，返回被移除子数组的长度。
分析：同样是利用前缀和 + 哈希表 + 同余定理，如果 sum(nums) % p = k，那么我们只需要找到一个最短子数组 A，使得 sum(A) % p = k 即可，这就是上一题的问题了。

最后 K 个数的乘积（中等）

链接：链接
分析：这道题主要难点在于可能会除以 0，当然我们可以判断是否除 0，但更巧妙的方法是：如果遇到 0，那就清空前缀积数组，反之则加入前缀积。那么在返回时只要判断前缀积数组长度是否大于 K，大于则按照一般思路返回，小于则说明包含 0，故而返回 0。为了计算方便，可以每次清空前提前加入个 1 。

前缀异或

和为奇数的子数组（中等）

链接：链接
描述：给定一个整数数组，返回所有和为奇数的子数组的数量。
分析：同样是前缀和题，但是因为要求和是奇数，所以我们将奇数映射为 1，偶数映射为 0。然后容易想到 1 ^ 0 = 0，1 ^ 1 = 0（做多了就有感觉啊哈哈），故而维护一个异或前缀和 sum ，也不用哈希表了，因为只有 2 个数，用数组 cnt 就够了，每次 result += cnt[sum ^ 1] 即可。另外这题有些坑啊，res 的值甚至超过了 Long 的最大值，还是乖乖取余吧。

形成两个异或相等数组的三元组（中等）

链接：链接
描述：给定一个数组，求出所有的三元组 (i, j, k)，(i < j <= k)，使得 [i, j - 1] 和 [j, k] 范围的数组异或值相等，返回三元组的数量。
分析：这道题还是要活用异或的性质：a ^ a = 0，那么我们只要遍历三元组的起始点 i 和结束点 k，如果当前异或值为 0，那么 result += k - i（根据 i, j, k）的关系可得。

二维前缀和

二维前缀和一般出现在求矩阵和大于或等于或小于某个值的矩阵个数或大小问题上。而这里关键在于怎么枚举矩阵，总的来说可以分为三个方面：

第一个朴素想法是枚举左上和右下四个点，这就是$O(n^4)$ 的时间复杂度，许多困难题下基本是在超时的边缘。
第二个想法是枚举边 + 有序集合或字典，比如固定上下两条边，然后移动右侧边，并且把每次右侧边下对应的矩形面积加入其中（比如 TreeSet），那么下次查找前面的边时就只要 logn 的时间复杂度。设原矩阵维度分别是 m 和 n，那么时间复杂度就是$O(min(m, n)^2 max(m, n)log(max(m, n)))$。

前面两个想法都需要先计算前缀和，这就要消耗 $O(mn)$ 的时间复杂度和 $O(mn)$ 的空间复杂度。计算前缀和无法减少时间复杂度，但我们可以优化空间复杂度到 $O(max(m, n))$ 。具体来说，就是下放计算前缀和到计算目标值过程中。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

// let nums be the input matrix, m, n is the two dimension of nums
boolean isRight = n > m
int[] sum = isRight ? new int[n + 1] : new int[m + 1]
for i = 1 to isRight ? m : n
    Arrays.fill(sum, 0)
    for j = i to isRight ? m : n
        // 根据情况选择合适的集合
        TreeSet<Integer> set = new TreeSet<>()
        // 添加 0 来方便计算
        set.add(0)
        int area = 0
        for k = 1 to isRight ? n : m
            // 实质上是计算最长维度上的一维前缀和
            sum[k] += isRight ? nums[j - 1][k - 1] : nums[k - 1][j - 1]
            // 所以 area 要叠加这个一维前缀和得到二维前缀和
            area += sum[k]
            // do something related to task
            // 将当前二维前缀和添加到有序集合中
            set.add(area)

矩阵区域不超过 K 的最大数值和（困难）

链接：链接
描述：给定一个二维数组和一个目标值 K，返回所有子数组中和小于 K 中 和最大 的那个子数组的和。
分析：
- 如果使用前缀和的做法，那就是前面介绍的三种枚举思路，最优时间复杂度和最优空间复杂度都和第三种思路一致，但这个方法并不是最优的。时间仅打败 5%。
- 下面介绍一种动态规划的方法。

元素和为目标值的子矩阵（困难）

链接：链接
描述：给定一个二维数组和一个目标值 K ，求所有和等于 K 的子数组的数量。
分析：
- 这道题也是可以采用前缀和的做法，有序集合选用为 HashMap，因为要计数。时间上打败 30% 左右，慢应该是因为我做了行列长度判断吧（为了避免行和列长度大大失衡），另外数据量可能不够大。

最大子矩阵（困难）

链接：链接
描述：给定一个二维矩阵，返回其和最大的子矩阵的左上和右下点的坐标。
分析：
- 还是前缀和，这道题就不用有序集合了。可以采用最大子数组和的思想，也可以维护一个最小子数组的位置和值来做。时间上打败20%左右。慢应该是因为我做了行列长度判断吧（为了避免行和列长度大大失衡），另外数据量可能不够大。因为我看时间差距并不是特别大。

元素和小于等于阈值的正方形最大边长（中等）

链接：链接
描述：给定一个二维数组，返回其和小于阈值的正方形中边长最长的那个的边长。
分析：
- 惯例的前缀和，然后定义 i, j, k 为以 i, j 为右下顶点, k 为边长的正方形，三重 for 循环就能过了。时间上打败约 30% 左右。
- 更好的方法是定义 i, j, k 为以 i, j 为左上顶点 , k 为边长（递增枚举）的正方形的做法，也是三重 for 循环，但 for 循环时可以提前结束（尽管这听着并不靠谱，但确实很 work）：如果当前边长的正方形和大于阈值即停止。这个时间上打败 97 %。

矩阵区域和（中等）

链接：链接
描述：给定一个输入二维矩阵 nums ，返回一个同等大小的答案矩阵 ans，其中每个元素的值应当为$ans[i, j] = \sum_{r = i - k} ^{i + k} \sum_{c = j - k} ^{j + k} nums[r, c]$ 。原题目描述确实不太清楚。
分析：就普通前缀和解法，只不过要判断越界而已。

最大的以 1 为边界的正方形（中等）

链接：链接
描述：给定一个二维数组 grid ，返回其一个最大的以 1 为边界的正方形的面积。
分析：
- 普通二维前缀和能做，就判断四条边么，虽然不是很快，但也差不了多少时间。主要注意判断边的左上角坐标要写对，比如对于 i, j 为右下顶点，k 为边长的正方形，其四条边的左上、右下顶点分别为：
  - [i -k , j - 1, i , j], [i - 1, j - k, i, j], [i - k, j - k, i - k + 1, j], [i - k, j - k, i j - k + 1]
- 还有也可以用动态规划来做，设 dp[i, j, k] 代表 i, j 点向上和向左的连续 1 的个数，k 区别向上和向左。那么当 grid[i, j] 不为 0 的时候枚举边的长度，还要判断另外两条边的长度是否符合条件。

差分前缀

航班预订统计（中等）

链接：链接
描述：给定一个航班数，和一个二维数组 bookings 代表预订历史，二维数组每二维有 3 个元素，第 3 个元素代表预订座位数，前 2 个元素表示编号位于这两个元素间（包括这两个元素）的航班都预订了这么多座位。返回一个数组，表示所有编号的航班的预订数。
分析：
- 暴力遍历勉强能过，就是效率感人。。。
- 更好的方法是利用前缀和的思想。定义 res[i] 表示从 i - 1 编号的航班开始每个航班预订的座位数，那么对于每个 booking，显然 res[booking[0] - 1] += booking[2]。而由于这个增量会累加到 booking[0] - 1 后的所有航班，所以我们要判断 booking[1] 是否为最大的航班编号，如果不是就要对 res[booking[1]] 减去 booking[2] 的座位数，从而避免后续航班的重复累加。

贪心

绝对差值和（中等）

链接：题目链接
描述：给定两个等长正整数数组 nums1 和 nums2，你可以至多修改 nums1 中的任一元素为nums1 中其他的任一元素一次。求$argmin\sum_{i = 0}^{len_{nums}} {|nums1[i] - nums2[i]|}$
分析：
- 要求对应的最小值，那么可以对应转化为求$argmax\mathop{|nums1[j] - nums2[i]| - |nums1[i] - nums2[i]|} \limits_{0 <= i < len_{nums1}}$
- 那么自然只要先求出所有绝对差值和，然后贪心遍历最大差值就好了么

减小和重新排列后数组后的最大元素（中等）

链接：题目链接
描述：给定一个正整数数组，你可以对其中任意元素进行排列或减小操作，而后使得该数组以 1 打头，且相邻元素间的绝对值差不大于 1。
分析：仔细想想其实就是先把第一个数置为 1，然后 for 循环遍历么，如果当前数和前一个数相差超过 1，那就设为前一个数加 1，反之不管。最后返回最后一个数即可么。

蓄水池抽样

蓄水池抽样算法能解决总的样本数量未知，从所有样本中抽取若干个，要求每个样本被抽到的概率相等的问题，常用于大数据流的随机抽样问题，即当内存无法加载全部数据时，如何从包含未知大小的数据流中随机选取k个数据，并且要保证每个数据被抽取到的概率相等。
举例说明：
- 遇到1，概率为1，保留第一个数。
- 遇到2，概率为1/2，这个时候，1和2各1/2的概率被保留
- 遇到3，3被保留的概率为1/3，(之前剩下的数假设1被保留)，2/3的概率 1 被保留，(此时1被保留的总概率为 2/3 * 1/2 = 1/3)
- 遇到4，4被保留的概率为1/4，(之前剩下的数假设1被保留)，3/4的概率 1 被保留，(此时1被保留的总概率为 3/4 * 2/3 * 1/2 = 1/4)
- 以此类推，每个数被保留的概率都是1/N。
- 证明使用数学归纳法即可

当 k = 1时，只需抽样总数据量次即可，伪代码如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

// 假设数据用list保存
List<Integer> data;
Random random = new Random();
int ans = 0;
for(int i = 0; i < data.size(); i++){
    // 这里的 0 可以改成 [0, i)范围内的任何数
	if(random.nextInt(i) == 0){
        ans = data.get(i);
    }
}

当 k > 1 时：

无标签

整数转罗马数（中等）

链接：题目链接
描述：给定一个整数 num，将其按照规则转化成罗马数表示，其中 I = 1, V = 5, X = 10, L = 50, C = 100, D = 500, M = 1000。如果不在这里面，则根据下面规则：①IV = 4, IX = 9, XL = 40, XC = 90, CD = 400, CM = 900 ②对于不在①中的数，则根据倍数叠加，如 20 = XX, 300 = CCC 。另外输入 num 范围在 [1, 3999]

模拟思路：自己想复杂了，然后看了题解，就一目了然，下面是伪代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

values = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]
strs = [M, CM, D, CD, C, XC, L, XL, X, IX, V, IV, I]
res = ''
for i = 0 to len_values
	if num == 0
		break
	else
		while num > values[i]
			res += strs[i]
			num -= values[i]
return res

硬编码思路：

罗马数转整数(简单)

链接：题目链接
描述：类似上题，不过方向变了一下
模拟思路：其实和上题一样的么，每次遇到字母就依次判断，然后整数值 sum 往上加对应的数值即可。

三数之和（中等）

链接：链接
描述：给定一个数组，求出数组中所有长度为 3 且和为 0 的不重复的三元组（排列不同也算重复）
题目分析：
- 首先因为是要求所有可能，第一时间想到了回溯 + dfs，为了去重，使用了 used 数组加上 begin 索引，同时 nums[i] == nums[i - 1] && !used[i - 1] 来剪枝去重。另外因为正数不可能加和为 0，所以又判断了 sum >=0 && nums[begin] > 0 的情况来进一步剪枝，但还是超时了。最后想到用 Map 优化为二重索引，但这里同样要注意去重（避免一个数的使用次数多于实际次数且新加进来的数至少比前一个数大） map.getOrDefault(-sum, 0) > 0 && -sum >= path.get(pa 吧th.size() - 1)，这个版本就 AC 了，虽然时间上只打败 5%
- 另外发现其实可以用 HashMap 双 for 循环来做，为了避免重复只需要保证每次取的时候后面取的数总是不小于前面取的数。同时每次取的时候应当把对应的 value 减一来避免多取，这样稍微快点，但也仅打败 6%。
- 官方题解使用的是双指针法。首先惯例地对数组排序，在回溯中也进行了。然后设立三个指针，其索引应当从小到大，且要注意去重，即 ptr = ptr_before or nums[ptr] != nums[ptr - 1]。这样是 $O(n^3)$ 的时间复杂度。但实际上对于第二个指针的循环时，我们可以并列搜索第三个指针，且第三个指针应该从数组最右端开始且大于第二个指针，这样均摊下来时间复杂度近似为 $O(n^2)$，虽然感觉还是三重循环。

跳跃游戏（中等）

链接：链接
描述：给定一个数组，数组中每个元素代表当前可以往前走的最大步数，一开始你位于索引 0 的地方，判断是否能够走到最后一个索引处。
题目分析：
- 首先是一个简单的暴力法，采用 dfs 实现，不出意料的超时了。然后分析发现许多位置存在多次被遍历的情况，故而使用了一个 visited 数组避免重复访问，然后 AC 了，虽然比较慢，时间上仅打败 14.7 %。
- 官方题解是贪心法，for 循环整个数组，维护一个变量 rightmost 代表能到达的右侧最大值，每次比较 i + nums[i] 和 rightmost 来更新 rightmost，而后判断其是否到了最右侧。其实是隐式的BFS

找到所有数组中消失的数字（简单）

链接：链接
描述：给定一个数组 nums，其中所有数都位于 [1, len_nums] 范围内，求缺失的那些数。进阶要求是否能够在 O(n) 时间内且不使用额外空间。
分析：
- 使用额外空间自然简单，Set 保存 [1, len_nums]，然后依次除掉数组里出现在 Set 中的元素，剩下的就是答案了。
- 不用额外空间的解法：因为 n 个坑位 n 个数字，那么我们可以根据数组里已有的数字对其对应的坑位做一些改变来标识这个坑被占了，那么没被占的坑自然是少的数。这里介绍两个方法：
  - 一个方法是将其对应的坑位置为负数。如输入 [4, 3, 2, 2]，置为[4, -3, -2, -2]
  - 另一个方法是将其对应的坑位加上数组长度。如输入[4, 3, 2, 2]，置为[4, 11, 6，6]
  - 实验发现后者更快点

编写 LRU 缓存（中等）

链接：链接
描述：实现一个 LRU（最近最少使用）缓存机制
分析：下面只讨论 LRU 中的 O(1) 时间复杂度实现的 get() 和 put() 方法（自己写的垃圾玩意打败 10% 不到，哭了）。
- 其实就是 LinkedHashMap 的源码重新造轮子（诶我没看过还）。实现方式是哈希表 + 双向链表，然后哈希表中记录的是键值 - 链表节点对。注意链表的成员变量应该同时包括 key 和 value，因为后续查找要用到。
- LRU 应该拥有这样几个成员变量，一个 Map，一个 capacity 和两个双向链表哑结点 head 和 tail，以方便后续添加节点到头部 (addToHead)、删除节点 (removeNode) 、移动节点到头部 (moveToHead) 和删除并返回尾结点 (removeTail)。括号内是需要实现的函数，均是基本链表操作，后面两个函数可以利用前两个来简易实现。
- 对于 get，首先通过 map 获取到对应节点，然后判断是否为 null。是则返回 -1，否则返回对应的 value，然后将当前节点移到头部 (moveToHead)。
- 对于 put ，首先通过 map 获取到对应节点，然后判断是否为 null。不是则更新节点对应的 value，然后移动到头部 (moveToHead)，否则以当前的 key 和 value 创建新的节点，添加到 map 并添加到头部 (addToHead)；之后判断是否超容量，超出则删除尾部节点 (removeTail) 并移除 map 中对应的键值对 (因为节点里有 key 成员，所以移除很便捷)

验证二叉搜索树（中等）

链接：链接
分析：
- 不要记混了二叉搜索树的定义，其定义是当前节点的左子树的所有节点值均小于当前节点，右子树的所有节点值均大于当前节点，同时左右子树也必须是二叉搜索树。
- 我们可以维持两个变量 min 和 max 来表示当前节点 node 的值所应处的范围区间。如果遍历左子树，那么就用 node.val 替代当前 max，反之则用 node.val 替换当前 min。容易验证这样遍历符合二叉搜索树的定义。

前 K 个高频元素（中等）

链接：链接
描述：给定一个数组 nums，找出其前 K 个出现最多的元素。注意 len_nums 可达到 $10^5$。进阶要求设计的算法时间复杂度不大于 O(nlgn)。
分析：
- 考虑时间复杂度的情况下，可以采用维持一个大小为 K 的小根堆的策略。在不使用系统库的情况下，可以创建一个对象来保存某个元素的属性（包括元素值，出现次数，和所在堆（数组实现）的位置），而所有不重复元素都用 Map 来保存元素值 - 对象类的键值对。而后遍历整个数组，如果堆没满，就直接加入当前元素；反之比较堆顶最小值并更新堆（写写还是蛮烦的，自己写的还慢，时间上只打败 20%）。
- 官方使用 PriorityQueue 当做堆的实现就比我快多了（打败50%）。不过官方并没有在填充 Map 的同时维持堆，而是先填满 Map 再填堆。然后将自己的方法也改成这样后，打败了99%。

完全平方数（中等）

链接：链接
描述：给定一个正整数 n，求至少需要多少个完全平方数（1, 4, 9, …)的和才等于它，返回需要的最少个数。n 最大可达 $10^4$。
分析：
- 看到这道题，首先就是动态规划么。一开始我还担心 n 这么大爆内存，没想到竟然过了，还挺快的，打败了 64%。
- 官方方法二：贪心枚举。它这里使用这个一个递推式来获得答案。
  - numSquare(n) = $\mathop{arg min} \limits_{count \in [1,2,…,n]}$(is_divided_by(n, count))
  - is_divided_by(n, count) 返回布尔量，表示 n 是否能由 count 个数的平方和表示。
  - 那么我们可以预先定义一定大小的平方和 list，然后 count 从 1 开始贪心求解，而在 is_divided_by(n, count) 中对所有平方和 for 循环，而后递归 is_divided_by(n - k, count - 1)
  - 根据分析，时间复杂度为 $O(\frac {{\sqrt n}^{h + 1} - 1} {\sqrt n - 1}) = O(n^{\frac {h} {2}})$ ，其中 h 是可能发生的最大递归数。
- 官方方法三：贪心 + BFS。上面的贪心枚举其实是 DFS 的方式，但其实这里用 BFS 会更好。因为在用尽固定数量的完全平方数分解数字 n 的所有可能性之前，我们不会探索任何需要更多元素的潜在组合。
- 官方方法四：四方数定理
  - 四平方和定理：任意正整数都可以表示为 4 个非负整数平方的和，这说明答案的上界为 4 。
  - 三平方定理：$n \neq 4^{k}(8m + 7) \iff n = a_{0}^{2} + a_{1}^{2} + a_{2}^{2}$ 。由三平方定理可以得知，如果 n 不满足三平方定理，那么 n 必然只能分解为 4 个平方和。（假设 n 可以分解成 2 个平方和，那么完全可以在后面补上 0 的平方从而满足三平方和定理，而这与假设矛盾）
  - 所以我们只要依次检验是否为平方和、是否不满足三平方定理，而后枚举是否是 2 个平方和，就可以得到最终答案。

除自身以外数组的乘积（中等）

链接：链接
描述：给定一个数组，返回一个和其等长的数组，其中每个元素值是原数组除去该元素外的乘积。题目要求不能使用除法。
分析：
- 其实使用除法也就需要考虑下存在几个 0 的问题，包括不存在、存在 1 个和多个的情况。
- 不使用除法的做法：感觉就是脑筋急转弯么。方法是分别计算两个数组 L 和 R，其中 L[i] 代表 i 以左所有元素的乘积（不包括索引 i 处），R[i] 类似。那么 result[i] = L[i] * R[i] 。但其实可以用 result 作为 L 来一遍，然后再作为 R 来一遍。

找到字符串中所有字母异位词（中等）

链接：链接
描述：给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。字符串中只包含小写字母。
分析：
- 普通做法就是划窗 + 数组么，搞两个计数数组记录当前窗的情况，然后比较两个计数数组是否相等就好了。话说用 Arrays.equals() 属实有点作弊，但也确实慢（时间打败 50%）。
- 而除了用作弊的 Arrays.equals()，实际上可以维护一个 diff，每次移除或加入字符时更新 diff，然后判断 diff 是否为 0。不过这个用数组实现的还比原来 equals 慢。
- 除去划窗 + 数组，还可以划窗 + 双指针，然后用上 diff ，时间上能打败 99% 。

统计字符串的唯一字符（困难）

链接：链接
描述：给定一个字符串，求其所有子字符串中仅出现一次的字符的个数，例如 f(AB) = f(A) + f(AB) + f(B) = 4
分析：
- 感觉就是套路题。朴素暴力法会超时，其实是有规律的。对于某个位置 i 的字符，分别向左和向右找到两个位置 h 和 j 使得该位置上的字符是第一次和 i 位置上字符相等的位置，那么 i 位置字符的贡献为 (h - i) * (j - i)

根据身高重建队列（中等）

链接：链接
描述：给定一个二维数组，其第二维维度为 2，分别代表身高和排在它前面且不低于它的人的数量。现要求对其进行排序，使得排序后，对于某个人，排在它前面且不低于它的人的数量恰好和当前人的对应数量一样。
分析：感觉脑筋急转弯。首先是先根据身高降序而人的数量升序排列，然后依次将对应人插入到比他高的人的数量的地方。

天际线问题（困难）

链接：题目链接
描述：给定一个二维数组，其第二维是有 3 个元素，分别代表建筑物的左右边界以及高度（每个建筑为可视为一个二维矩形），现将其绘制于一个二维坐标轴上，求其天际线（一个二维数组，其第二维包括天际点的坐标和对应高度）。下面是一张示例：

分析：
- 首先从图中可以看到，天际点是由原建筑的左右端点构成。
  - 对于左端点，它有一条向右延伸的边，但不一定是需要被记录的边，因为在同一矩形中我们只考虑最高的那个。
  - 对于右端点，它代表了某条延伸边的结束。
  - 综合这两个我们可以利用优先队列来存储遍历过的高度，然后先对原建筑物构建高度数组，并按照先坐标后左端点高度排序方式排序，并维护一个变量代表当前高度。
  - 当遍历到左端点时，将当前高度入队列，右端点则出队列。同时左端点入队时判断左端点高度是否比当前高度高，若是则为天际点。
  - 另外由于天际点钟存在 0 ，所以我们要预先加入一个 0 到队列中。

删除最短的子数组使剩余数组有序（中等）

链接：链接
描述：给定一个整数数组 nums，请你删除一个子数组，从而使得剩余的数组为单调递增数组，返回删除的子数组的最短长度。
分析：
- 首先看题，只能删除一个子数组。所以要么删左边，要么删右边，要么删中间。对于左右边情况，直接遍历一次就能得到答案了。而对于中间情况，其最长情况一定是左右两个有序数组合并后删除一定元素的结果（假设中间能留下一些数，那么必然要删除两个）。所以双指针走一波，左边从 0 开始，右边从右边界开始即可，每次符合情况即判断。

阶乘末尾 0 的个数（中等）

链接：链接
描述：给定一个数 n ，求其阶乘后 0 的个数。
分析：首先 0 是怎么来的，很明显只有 5 乘以偶数才能得到，而出现了 5，其前面必然有比它小的偶数。因此我们可以把阶乘分解成一系列质数的乘积，那么 0 的个数就是 5 的个数了。因为 5 本来就是质数，所以只要不断累加 n / 5 的结果即可。

得分最高的最小轮调（困难）

链接：链接
描述：给定一个数组 nums，其中 nums[i] < nums.length，现在你可以将数组整体循环左移一次，求循环左移的最小长度 k，使得左移后 nums[i] <= i 的个数最多。
题解：
- 首先分析一个数 nums[i] 左移 k 位后所在的位置，容易得知其为 (i - k + n) % n，那么即可推出使得 nums[i] = i 的左移位数为 (i - nums[i] + n) % n。此时若继续左移，则会使得 i < nums[i]（除去左边界的情况）
- 那么我们可以维系一个数组 loc，loc[i] 表示左移 i 位时 nums[i] 中元素恰好满足 nums[i] = i + 1 的元素的个数，显然我们有 $(x - nums + 1 + n) % n = i \to loc[i]++$ 。
- 已知当 k = x 时有 loc[i] 个元素不得分，那么当 k = x + 1 时，k = x 中的 loc[i] 个元素依旧不得分，但 k = x 时位于 nums[0] 处的元素开始得分（因为它被移到右边界，而 nums[i] < nums.length），所以我们可以得到递推式：loc[i] += loc[i - 1]。
- 那么我们只需要维护一个答案 k，然后遍历递归 loc 数组，并判断更新使得 loc[k] 是整个 loc 数组中最小的即可。

算法导论记录

中位数和顺序统计量

最大值和最小值

基本思路：想要找到一个数组的最大或最小值，最小也需要 n - 1 次比较；而同时找则需要 2n - 2 次比较；而事实上，我们最大仅需要 3[n / 2] 次比较即可同时找到最小值和最大值。对于有 n 个元素的输入数组，若 n 为奇数，则最大值和最小值初值均为「第一个元素」的值，反之根据「前两个元素」的大小关系分配；而后每次「成对地」输入元素，先将输入元素对进行比较，然后把较小元素与最小值比较，较大元素与最大值比较。这样，对每两个元素就只需要 3 次而非4次比较。

散列表

直接寻址表

直接寻址表直接给每个关键字分配一个槽，当实际关键字的范围跨度较大而数量较小时，会造成空间的极大浪费；

散列冲突

当两个关键字被映射到同一个槽中时，称这种情况为冲突。解决冲突的方法主要有：链接法、开放寻址法。

链接法：在链接法中，把散列到同一槽中的所有元素都放在一个链表中。为了保证删除一个元素的时间复杂度也是 O(1)，最好在实现链表时采用双向链表来实现。用链接法的平均时间复杂度为 $O(1 + \alpha)$，其中$\alpha$ 称为装载因子，其值为总元素个数 n 和散列表长度 m 的比值。

散列函数

好的散列函数应（近似地）满足简单均匀散列假设：每个关键字都被等可能地散列到 m 个槽位中的任何一个，并于其他关键字已散列到哪个槽位无关。遗憾的是，我们很少能得知关键字散列所满足的概率分布，并且各关键字可能并不是完全独立。

除法散列法：$h(k) = k % m$。通常 m 是一个不太接近 2 的整数幂的素数。比如我们要存放 2000 个数，如果我们不介意一次不成功的查找需要平均检查 3 个元素，这样分配散列表的大小为 701。
乘法散列法：$h(k) = \lfloor m(kA%1) \rfloor$。第一步，用关键字 k 乘上常数 A(0 < A < 1)，并提取 kA 的小数部分。第二步，用 m 乘以这个值，而后往下取整。乘法散列法的一个优点是对 m 的选择不是特别关键，一般选择它为 2 的某个幂次$(m = 2^{p}, p \in Z)$，这是因为我们可以在大多数计算机上按下面所示方法散列函数。其中 A 被限制为形如 $s/2^{w}$的一个分数。虽然该方法对任何 A 值都适用，但对某些值更好，比如 Knuth 认为 $A \approx (\sqrt{5} - 1) / 2$是一个比较理想的值

字符串匹配篇

设原字符串为 ts , 长度为 n ;待匹配字符串为 ps , 长度为 m 。

纯字符串匹配（不包含通配符等）

朴素匹配

两个 for 循环，时间复杂度为 O(mn)

KMP(Knuth-Morries-Pratt)算法

复杂度：时间复杂度 O(m + n)，空间复杂度 O(m);
思路：主要是借鉴了人为进行辨别的过程。假设我们用两个指针 p 和 q 代表在原字符串上和待匹配字符串上的指针。当人为辨认时，如果匹配到第 $j(j < m)$ 个字符时两个字符串不匹配，显然我们不会将指针 p 也往回移动 k 个位置，因为我们知道这并没有什么意义，如下图：

$$ \begin{matrix} A & B & C & A & B & C & D & H & I\ A & B & C & A & B & D & & & \ & & & A & B & C & A & B & D \end{matrix} $$

以上图为例：当我们匹配到 C 时（第 1 和第 2 行），因为两个字符不匹配，按人为匹配来说我们显然会根据 C 前面的情况只移动短的待匹配字符串来使得新位置下两个字符串的已匹配字符数最多来缩短匹配时间（第 1 行和第 3 行）。那么如何获得这个新的位置呢，仔细观察后**容易**发现 j 应当移动到的位置 k 应当满足这个条件：$ps[0 , k - 1] == ps[j - k , j - 1]$。下面给出这样的 k 为什么会使得 ts 和 ps 的指针往前 k - 1 个字符相匹配

$$ \begin{cases} ts[i] \neq p[j] \to ts[i - j, i - 1] == ps[0 , j - 1] \ ps[0 , k - 1] == ps[j - k , j - 1] \to ts[i - k , i - 1] == ps[0 , k - 1] \end{cases} $$

有了这样的证明，我们只要定义一个 next 数组并保存每个 j 的下一个位置 k 即可，下面为伪代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

int[] next = new int[ps.length]
next[0] = -1
int j = 0, k = -1
while j < ps.length - 1
    // k = -1 时 j 最小也是 0， 即 ++k
	if k == - 1 or ps[j] = ps[k]
		// ps[0 : k - 1] = ps[j - k : j - 1]
		// ps[j] = ps[k] -> ps[0 : k - 1] + ps[k] = ps[j - k : j - 1] + ps[j]
		// -> ps[0 : k] = ps[j - k : j] -> next[j + 1] = k + 1 = next[j] + 1 
		next[++j] = ++k
	else
		k = next[k]

next数组的优化：回到原来的案例，其实可以发现变成第 3 行后还是不匹配，接下来才变成第 4 行，那其实第 3 行的匹配也是无效的。这个问题发生在于 ps[j] == ps[next[j]]，那么我们只要加个判断来优化这个过程即可。

$$ \begin{matrix} A & B & C & A & B & C & D & H & I & J \ A & B & C & A & B & D & & & & \ & & & A & B & C & A & B & D \ & & & & & A & B & C & A & B & D \end{matrix} $$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

int[] next = new int[ps.length]
next[0] = -1
int j = 0, k = -1
while j < ps.length - 1
  if k == - 1 or ps[j] = ps[k]
  	if ps[++j] == ps[++k]
  		next[j] = next[k]
  	else
  		next[j] = k
  else
  	k = next[k]

最后容易写出双指针的主体伪代码如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

int i, j = 0
get next[] use codes above
while i < ps.length and j < ts.length
	if j == -1 or ts[j] == ps[i]
		i++
		j++
	else
		// i 不需要回溯
		j = next[j]
if j = ts.length
	return i - j
else
	return -1

BM(Boyer-Moore)算法

亚线性串匹配算法，很多文本编辑器的查找中常用的算法

复杂度：时间复杂度 O(n / m) ~ O(mn)（最好和最坏情况）

Sunday算法

针对BM算法进行一些改动，实际使用中略优

复杂度：时间复杂度 O(n / m) ~ O(mn)（最好和最坏情况）

Horspool算法

-复杂度：平均时间复杂度 O(n), 最坏情况下时间复杂度 O(mn)

其他学的数据结构和算法

哈希树

介绍：哈希树的每个叶节点均以数据块的哈希作为标签，而除了叶节点以外的节点则以其子节点标签的加密哈希作为标签。哈希树能够高效、安全地验证大型数据结构的内容。

字典树（前缀树）

介绍：哈希树的一种变种，典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。
下面给出只针对小写字母的常见写法：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

class Trie{
    // 针对小写字母集的写法，如范围更广可类似写作
    // Map<Character, Trie> children;
    Trie[] children;
    // 代表首节点到当前节点是否构成一个单词
    boolean isEnd;
    
    public Trie(){
        this.children = new Trie[26];
        this.isEnd = false;
    }
    
    public void insert(String word){
        Trie node = this;
        for(char ch : word.toCharArray()){
            int index = ch - 'a';
            if(node.children[index] == null){
                node.children[index] = new Trie();
            }
            node = node.children[index];
        }
        node.isEnd = true;
    }
    
    public Trie searchPrefix(String prefix){
        Trie node = this;
        for(char ch : word.toCharArray()){
            int index = ch - 'a';
            if(node.children[index] == null){
                return null;
            }
            node = node.children[index];
        }
        return node;
    }
    
    public boolean contains(String word){
        Trie node = searchPrefix(word);
        return node != null && node.isEnd;
    }
}

实现 Trie（中等）

链接：链接

单词拆分（中等）

链接：链接
描述：给定一个字符串 s 和一个字符串数组 t，判断该字符串是否可以由字符串数组中的字符经任意排列（单个字符串可不选也可重复选）组成。
字典树解法：简单来说就是先用字符串 s 构造前缀树，而后针对字符数组 t 中的字符串，不断dfs 利用 searchPrefix 来查找，直到 node.isEnd = true 也就是全部找到为止。但这样直接做会超时，实际上对于原字符串 s 的子串 s1，dfs 中重复找了很多次。故而可以构造一个 visited 数组，visited[i] 表示剩余长度为 i 的子串 s1 是否可以由字符串数组 t中元素组合而成。
动规做法：其实感觉很暴力。假设 dp[i] 表示字符串前 i 个字符是否可以由字符数组 t 中的字符串组成，那么很显然 dp[i] = dp[j] && s[j, i] in t。那么对 i 和 j 来两重 for 循环，最后返回 dp[len(s)] 即可。而实际上由于 t 中的字符串长度已知，我们可以进一步优化循环范围，其中 i 的范围应为 [min_len, n]，j 的范围应是 [max(0, i - max_len), i - min_len]，其中 max_len 和 min_len 分别代表 t 中字符串的最大和最小长度。

键值映射（中等）

链接：链接

实现一个魔法字典（中等）

链接：链接

并查集

并查集主要用于解决一些元素分组的问题，它管理一系列不相交的集合，并支持两种操作：
- 合并（Union）：把两个不相交的集合合并为一个集合
- 查询（Find）：查询两个元素是否在同一个集合中
通常我们用一个数组 fa 来表示当前元素的父元素，并初始化各元素的父元素为自身，即：

1
2
3

int[] fa = new int[n]
for i = 0 to n - 1
	fa[i] = i

查询：这里采用递归方式返回当前元素所在集合的根元素而非父元素，因为前者可以用来判断两个元素是否属于一个集合，下面是递归版

1
2
3
4
5

def find(int[] fa, int x)
	if(fa[x] == x)
		return x
	else
		return find(fa[], x)

合并：只需要把当前节点所在集合的根元素设为新节点所在集合的根元素即可，当然也可将后者的根元素设置为前者的根元素。

1
2

def merge(int[] fa, int x, int y)
	fa[find(fa, x)] = find(fa, y)

路径压缩：注意到当某个集合很大时，我们对末端元素查找根元素将非常耗时。而既然我们只关心一个元素对应的根元素，那么我们希望每个元素到根元素的路径尽可能短，最好为一。按照这个思想，我们很容易给出对应的 Find 函数更改版，下面是递归版。

1
2
3
4
5
6

def find(int[] fa, int x)
	if(fa[x] == x)
		return x
	else
		fa[x] = find(fa[], x)
		return fa[x]

按秩合并：上面我们合并时是随机选择合并方向的，但究竟选择什么合并方向是最好的呢？回到路径压缩的初始目的来，我们期望搜索路径尽可能的短，那么自然期望合并后的集合（类似多叉树）能尽可能的浅（类比树的高度），因此我们应该把简单的树往复杂的树上合并，这样合并后到根元素距离变长的节点个数比较少。

我们可以用另一个数组 rank 记录以当前元素为根元素对应的树的深度，初始时均为 1，合并时则比较两个根节点，把 rank 较小者往较大者上合并。
路径压缩和按秩合并如果一起使用，时间复杂度接近 O(n)，但是很可能破坏 rank 的正确性。比如选择树高作为秩时，合用会破话秩的准确性。也可以采用树的元素个数，因为元素多的元素倾向于比较高。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

def init(int n)
	int[] fa = new int[n]
	int[] rank = new int[n]
	for i = 0 to n - 1
		fa[i] = i
		rank[i] = 1

def merge(int i, int j)
	int x = find(fa, i), y = find(fa, j)
	if(rank[x] <= rank[y])
		fa[x] = y
	else
		fa[y] = x
	if(x != y && rank[x] == rank[y])
		rank[y]++

连通网络的操作次数（中等）

链接：链接
分析：
- 首先是自己的分析。除去路径压缩和按秩合并，额外定义了一个 size 表示当前集合的边的个数（每个元素本身的自环不算），然后对于每个集合，其多余的边的个数为总边数减去最少需要边数（集合元素个数减 1）。加和这些多余的边，而对于连接这些集合，需要的最小边数为集合的个数减 1，那么只要判断二者大小即可。
- 然后是官方题解的 DFS 。思路是定义了一个点集合 List<List> edge，然后遍历连通数组，使得每个点均包含了其连通的边。最后定义一个变量 visited，DFS 遍历所有点集，每次遍历最终答案 res 加一，并将当前点的连通点的 visited 对应处置 1。这实际上计算了不连通的点集的数量，那么最后返回 res - 1 即可。
- 最后是更简化版的并查集。首先最小边数为元素个数减一，那么如果 connections 数组长度不够长，可以直接返回 -1；反之我们可以维护一个变量为需要添加的最小边数 res ，初始值为 n - 1 。每当有不同根元素的集合合并时，说明这个 res 可以减一，最后返回即可。

连接所有点的最小费用（中等）

链接：链接
描述：给定一个二维数组，表示一系列二维平面坐标点，现要求所有点两两连通（直接或间接连通），两个点的连通代价为二者坐标的曼哈顿距离，求最小总连通代价。
分析：就是并查集，首先把所有边枚举出来，然后按边的代价排序，最后并查集合并即可。需要注意的是，判断所有点是否连通可以事先定义一个连通的点数，每次合并时加一，然后判断连通点数是否等于总点数即可。

检查网格中是否存在有效路径（中等）

链接：链接
分析：可以把原问题看成左上角和右下角的连通性问题，那么就可以用并查集，虽然这题并查集并不快。另外也可以考虑使用 DFS 。

树状数组

树状数组的提出是为了找到一种数组结构，既能快速更新元素值，又能快速对区间求和。传统的数组更新值快但区间求和慢；前缀和数组求和快但更新元素值慢。而树状数组就是一种均能以$O(lgn)$的时间复杂度进行更新元素值和区间求和的组。
首先定义 lowbit(x) 为 x 的二进制表示从右边开始直到遇到第一个 1 为止的所有数。由于计算机中使用补码表示，根据补码定义，很容易得知 lowbit(x) = x & -x。同时 x + lowbit(x) 会不断将 x 右边连续的 1 变为 0，同时连续 1 前的一个 0 变为 1，类似进位；减法则相反。
树状数组，英文名二进制下标树，就是利用了二进制的一种巧妙结构。假设原数组为 A，对于索引 i，它不是表示 A[i] 而是表示 A(i - lowbit(i), i] 范围内数的累加和。下图是一个示例，很明显如果我们以 lowbit(i) 作为循环累加量，那么循环次数不会超过 lgn 。对应的区间求和也是类似。但要注意索引下标应当从 1 开始。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

int origin[N], tree[N];

// init tree
for(int i = 1; i <= N; i++){
    treeUpdate(i, origin[i - 1]);
}

// update num value
void update(int pos, int num){
    int origin = query(pos + 1, pos);
    treeUpdate(pos + 1, num - origin)
}

// pos starts from 1,same with below
void treeUpdate(int pos, int num){
    for(; pos <= N; pos += pos & -pos){
        tree[pos - 1] += num;
    }
}

// pos start from 1
int query(int pos){
    int sum = 0;
    for(; pos > 0; pos -= pos & -pos){
        sum += tree[pos - 1];
    }
    return sum;
}

// pos start from 1
int query(int posA, int posB){
    return query(posB) - query(posA - 1);
}

数组中的逆序对（困难）

链接：链接
描述：给定一个数组，求数组中的逆序对的数量。逆序对是指两个数字，前面的数字比后面的大。

解题思路：原题描述可转换为：对于数组 nums 和给定的索引 j，我们希望找到所有满足 i < j 且 nums[i] > nums[j] 的 i 的个数。for 循环自然可以找到，但对于第二个循环的查找可以用其他数据结构优化，比如线段树、树状数组等。

树状数组：首先一个循环遍历原数组，然后在插入当前数前，先通过树状数组找到比他大的数的个数（时间复杂度O(lgn)），再插入。由于我们是顺序插入的，因此找到的必然是符合要求的。

需要注意的是，由于 nums 的数据范围可能较大，通常需要先对原数组中的元素进行离散化。即将原数组的数据根据一定规律（如递增）映射成离散紧凑的数据以减少树状数组或线段树的大小。下面是一个离散化的例子：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

int[] nums;
TreeSet<Integer> set = new TreeSet<>();
for(int num : nums){
    set.add(num);
}

Map<Integer, Integer> map = new HashMap<>();
int idx = 1;
// 将nums中元素按升序映射到1...n
for(int num : set){
    map.put(num, idx++);
}

...
// 后续取用元素时要从map中获得索引
map.get(num);
...

变体：翻转对现在要求 i < j 且 nums[i] > 2 * nums[j]。这题同样可以用树状数组做。一样先离散化，然后插入 nums[i] 前查找 (2 * nums[i], max_value] 的元素个数即可。

计算右侧小于当前元素的个数（困难）

链接：题目链接
描述：给定一个数组 nums，求一个数组 smaller，其中 smaller[i] 表示 nums[i] 右侧小于 nums[i] 的元素的个数。
分析：只要倒序插入，就能保证前面插入的数一定在当前数的右侧。然后结合树状数组，即可解题。
归并排序法：

区间和的个数（困难）

链接：题目链接
描述：给定一个数组 nums 和一个区间 [lower, upper]，求所有满足 sum(i, j) $\in$ [lower, upper] 且 i <= j 的元素对(i, j) 的个数。
分析：首先肯定前缀和得到前缀和数组，然后对于 preSum[i]，我们要求的是前面已经插入的前缀和中 (preSum[i] - upper, preSum[i] - lower] 部分的数量，这自然可以用树状数组来优化。
归并排序法：

快速幂

引入：求一个数 k 的 n 次方，你会怎么求？朴素求必然是小白做法，一般必然是 $k^n = k^{n / 2} * k^{n / 2}$。这样原本求 n 次方就变为求 n / 2 次方本身的自乘，无限递归下去，时间复杂度就为 $O(lgn)$。
但换个角度，如果我们将 n 表示为 2 进制表示（$n = (10110)_2$假设），并采用如下方式计算：

1
2
3
4
5
6
7
8
9

int k, n;
int t = k, res = 1;
while(n > 0){
    if((n & 1) == 1){
        res *= t;
    }
    t *= t;
    n >>= 1;
}

上面算法中 t 可以看做 $k^m, m \in[0, bitlen(n)]$，而 n & 1 == 1 则是判断当前位 n 是否为 1；那么如果当前位 n 二进制为 1，显然最终答案应该乘以 t；而 t 则是通过自乘来更新；那么最终更新条件是什么呢，显然就是到 n 的二进制位最右的 1 时，因此我们每次右移 n 一位。
上面所述的都是整数的快速幂，但其实，在算 $k^n$ 时，只要 k 的数据类型支持乘法且满足结合律，快速幂的算法都是有效的。矩阵、高精度整数，都可以照搬这个思路。注意，较复杂类型的快速幂的时间复杂度不再是简单的 $O(lgn)$ ，它与底数的乘法的时间复杂度有关。

拓扑排序

拓扑排序是对有向无环图进行的一种线性排序，它满足：如果图 G 包含边 (u, v) ，那么节点 u 将排在节点 v 前面。举个例子，比如穿衣服过程，各个衣服穿衣是有顺序要求的，那么我们排出来的就是穿衣的优先顺序。如果图包含环，那么不可能得到线性排序。

拓扑排序的实现：

BFS ：我们根据输入构造一个邻接链表表示边 edges ，并构造一个数组统计各个点的入度。而后构造一个队列，先将入度为 0 的节点加入队列。而后当队列不为空时，每次取出一个元素，根据题目要求可对该元素做适当操作（比如加入最终结果），而后对以该元素为起点的边，其终点的入度均减一（因为相当于我们移除了当前元素）。若终点入度为 0 ，则加入队列。如此循环，得到的便是拓扑排序结果。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

List<List<Integer>> edges
int[] indeg
// fill edges and indeg with input informations
Queue<Integer> queue
List<Integer> result
for elem in indeg
    if elem == 0
        queue.offer(indeg.index(elem))
while !queue.isEmpty()
    int i = queue.poll()
    result.add(i)
    for dst in edges.get(i)
        indeg[dst]--
        if indeg[dst] == 0
            queue.offer(dst)

DFS ：同样先根据输入构造一个邻接链表表示边 edges，而后构造一个数组 visited 表示以当前元素为起点的深度遍历状态：0 代表还未遍历， 1 代表遍历中但未遍历完，2 代表遍历完了。那么对于所有元素，如果它尚未遍历，则我们对以其为起点的边进行深度遍历，开始时 visited 改为 1，遍历完后 visited 改为 2 ，然后在其 visited 为 2 后加入以倒序方式插入结果（我们最先得到的 visited = 2 的必然是依赖较多的，放在最后一定没问题），则得到的便是拓扑排序。

课程表（中等）

链接：链接
描述：给定一个二维数组表示两门课间的依赖关系（修前者就必须先修后者）和所有课程数，判断是否能修完所有课程。
分析：这算是标准的拓扑排序，BFS 和 DFS 均可。但为了加速，DFS 中我们可以设置一个变量 isValid 代表是否存在环（因为存在环则无法拓扑排序）。然后在进行深度遍历时，如果遇到 isValid 为 false 或 visited[dst] 为 1 的情况，则说明存在环，可以提前得到结果。而 BFS 则是判断最终得到的结果课程数是否够。

课程表 2（中等）

链接：链接
描述：现在要求给出修课的顺序，其实就是给出拓扑排序的结果。
分析：其实还是和上一题做法一样，只是输出变了。

课程表 4（中等）

链接：链接
描述：现在是额外输入一个二维查询数组，让你判断前面的课是否为后面的课的先修课，即前者能否到达后者。
分析：
- flyod 算法：$O(n^3)$ 的动态规划算法，可以求出有向图任意两点的连通性。
- 拓扑排序：这里用 BFS 较为方便。直接正向统计从某一点到其他点的边集比较麻烦，这里我们逆向构造一个逆边集表，表示对于某个点，有哪些点可以达到它。那么按照 BFS 的套路，在遍历的时候依次取出元素，对于当前元素的所有终点，终点的入度减一，逆边集表中对应集合加上当前元素和以当前元素为终点的所有元素（可以直接查逆边集表）。最后对于输入的查询，判断是否起点可以到终点即可。

找到最终的安全状态（中等）

链接：链接
描述：给定一个 n 维图数组，数组中的每个元素代表当前索引对应元素能到达的其他元素索引。试求所有满足条件的点，使得无论选那条路走，都能达到一个出度为 0 的点。
分析：乍一看和拓扑排序没啥关系，但这里需要逆向思维。依旧套用 BFS 的模板，不过我们这次构造出度数组，同时边也逆向构造。那么最后拓扑排序出来的就是符合要求的点（思考为什么）。

喧嚣和富有（中等）

链接：链接
描述：给定一个二维数组代表 n 个人间的富裕关系，同时给定一个数组代表 n 个人的安静程度，返回一个数组 ans，使得 ans = y ，其中 y 是不穷于 x 的所有人中最安静的。
分析：
- 拓扑排序。也是逆向思考，因为是考虑不穷于某个人的所有人中最安静的，那么我们构建有向无环图时应该以穷的人为起点，富的人为重点，然后这里用 DFS 比较方便。深度遍历时比较当前点和其终点的安静程度，因为安静有递推性，所以最后就能得到正确结果。

最小生成树

Kruskal算法

Kruskal 算法属于贪心策略，其找到安全边的方法是，在所有连接两棵不同树的边中，找到权重最小的边加入生成树中。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

MST-KRUSKAL(G, w)
A = []
for v in G.V
	MAKE_SET(v)
sort the edges of G.E into nondecreasing order by weight w
for edge(u, v) in G.E
	if FIND_SET(u) != FIND_SET(V)
		A.add((u, v))
		UNION(u, v)
return A

简单来说，就是利用并查集数据结构保存所有顶点，而后根据边的权重对所有边进行升序排序。之后遍历所有边，如果某条边的两个顶点不在同一集合，则将其加入当前最小生成树，并合并该点到当前集合。其时间复杂度近似为$O(ElgV)$。

Prim算法

Prim 算法的思想与 Kruskal 类似，也属于贪心策略。由于最小生成树总是一棵树，因此每次添加一条与当前生成树相连且权重最小的边，同时它需要一个随机起点作为根。其伪代码如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

MST-Prim(G, w, r)
A = []
Q = []
for v in G.V
	MAKE_SET(v)
while A.V != G.V
  for v in edge(r, v)
  	if FIND_SET(r) != FIND_SET(v)
  		Q.add(r, v, w)
  if Q is not []
  	sort Q by the w with nondecreasing order
  	remove all edges in Q whose second element is in the same set with r
  	A.add(Q[0])
  	start = Q[0][1]
  	Q.remove(0)
  else
   	set start to a value not in G.V
return A

从伪代码可见，我们需要对 Q 进行快速排序，因此最小优先队列是不错的选择。而 Prim 的整体思路其实和 Kruskal 算法大同小异。随机选取一个起点，而后将与其连通的不在同一集合的点加入队列，之后选取权重最小的那个作为下一个起点，如此往复。采用最小优先队列实现时，其时间复杂度近似为$O(ElgV)$。

单源最短路径

Bellman-Ford 算法

Bellman-Ford 算法属于贪心策略，它解决的是一般情况下的单源最短路径问题，边的权重可以是负值，适用于有向图。对于给定的输入，它返回一个布尔值，以表明是否存在从一个源节点可以到达的权重为负值的环路。如果存在，算法告诉我们不存在解决方案，反之则返回最短路径和它们的权重。Bellman-Ford算法的总运行时间为 $O(VE)$。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

INITIALIZE-SINGLE-SOURCE(G, s)
	// v.d means the distance from s to v
	// v.π means the prev node of v in the shortest path from s to v
	for v in G.V
			v.d = ∞
			v.π = NULL
	s.d = 0

RELAX(u, v, w)
	if v.d > u.d + w(u, v)
		v.d = u.d + w(u, v)
		v.π = u

BELLMAN-FORD(G, w, s)
	INITIALIZE-SINGLE-SOURCE(G, s)
	for i = 1 to |G.V| - 1
		for each edge(u, v) in G.E
			RELAX(u, v, w)
	for each edge(u, v) in G.E
		if v.d > u.d + w(u, v)
			return FALSE
	return TRUE

实际实现中，可以利用两个数组分别表示 v.d 和 v.π，而后更新两个数组即可

Dag-Shortest-Paths算法

根据节点的拓扑排序次序来对带权重的有向无环图进行边的松弛操作，即可在$O(V+E)$时间内求出单源最短路径。它相比 Bellman-Ford 方法，区别仅在于先对节点进行拓扑排序，而后按照拓扑排序中节点的顺序进行遍历而已。

1
2
3
4
5
6

DAG-SHORTEST-PATH(G, w, s)
	topologically sort the G.V
	INITIALIZE-SINGLE-SOURCE(G, s)
	for v in G.V and in topologically sorted order
		for u in G.Adj(v)
			RELAX(u, v, w)

Dijkstra 算法

Dijkstra 算法属于贪心策略，它解决的是带权重的有向图上单源最短路径问题，它要求所有边的权重非负。如果采用的实现方式合适，它的运行时间要低于 Bellman-Ford 算法。
Dijkstra 的主要流程如下：首先初始化图 G 中每个顶点到起始点 r 的距离以及最短路径上它的前一个节点。而后初始化最短路径集 A 和剩余集合 Q，其中 A 初始包含起始点 r，A + Q = G。而后当 Q 非空时，寻找 Q 中到 s 距离最小的一个点 u，将其加入 A 中，并对 u 所连接的点进行松弛操作。

1
2
3
4
5
6
7
8
9

DIJKSTRA(G, w, s)
	INITIALIZE-SINGLE-SOURCE(G, s)
	A = {s}
	Q = G.V - A
	while Q != Ø
		find u whose distance to s is the minium in Q
		A.add(u)
		for v in G.Adj[u]
			RELAX(u, v, w)

如果采用数组来维持最小优先队列，即第 6 行，其近似时间复杂度为 $O(V^2)$，而如果用二叉堆来实现最小优先队列，则为 $O((V+E)lgV)$。而如果用菲波那切堆，则可以进一步优化到$O(VlgV + E)$。

多源最短路径

Floyd-Warshall算法

Floyd 算法的运行时间为 $O(V^3)$，它适用范围为：负权重的边可以存在，但负权重的环路不能存在，其转移方程为：

$$d_{ij}^{(k)} = \begin{cases} w_{ij} & k = 0 \ min(d_{ij}^{(k-1)}, d_{ik}^{k-1} + d_{kj}^{k-1}) & k \geq 1 \end{cases}$$

1
2
3
4
5
6
7
8
9

FLOYD-WARSHALL(W)
	n = W.rows
	D_(0) = W
	for k = 1 to n
		let D_(k) = (d_ij_(k)) be a new n * n matrix
		for i = 1 to n
			for j = 1 to n
				d_ij_(k) = min(d_ij_(k-1), d_ik_(k-1) + d_kj_(k-1))
	return D_(k)

Floyd 对于中等稠密图效果较好。

后缀数组

概念说明

首先给定几个概念：字符串 s，其长度为 n，后缀 suffix(i)，后缀数组 sa[i]，名次数组 rank[i]
后缀 suffix(i) 表示 s[i:len(s)]，即字符串 s 从索引 i 开始到末尾的子串。
后缀数组：定义后缀索引数组 sindex，sindex[i] 对应 suffix(i) ，容易得知 sindex[i] = i。对所有的后缀字符串按照字典序排序，并将排序后的索引填到原来的后缀索引数组 sindex后，即为后缀数组。
名次数组：名次数组 rank[i] 表示 suffix(i) 在排序后的索引，即 sa[ra[i]]=i; ra[sa[i]] = i。
LCP 最长公共前缀：定义 LCP(i, j) 为 suffix(sa[i]) 和 suffix(sa[j]) 的最长公共前缀，下面是一些性质
- LCP(i, j) = LCP(j, i)
- LCP(i, i) = len(sa[i]) = n - sa[i] + 1
- LCP Lemma：LCP(i, k) = min(LCP(i, j), LCP(j, k)) 对于任意 i <= j <= k
  - 证明：设 p = min(LCP(i, j), LCP(j, k)), suffix(sa[i]) = u, suffix(sa[j]) = v, suffix(sa[k]) = w，则我们有 LCP(i, k) >= p。设LCP(i, k) = q > p，则 q >= p + 1，故有 u[p + 1] != v[p + 1] 或 v[p + 1] != w[p + 1]。但又有 u[p + 1] = w[p + 1]，这与前者矛盾，所以 LCP(i, k) <= p，故而 LCP(i, k) = p = min(LCP(i, j), LCP(j, k))。
- LCP Theorem：LCP(i, k) = min(LCP(j - 1, j)) 对于任意 i < j <= k。这个由 LCP Lemma 容易推出，只需设 j = i + 1，而后不断拆即可。
height 数组：定义 height[i] = LCP(i - 1, i)，定义 h[i] = height[rank[i]]
- 定理：h[i] >= h[i - 1] - 1
简单来说，后缀数组表示排第几的是谁，名次数组表示你排第几，二者互为逆运算。下面是一个简要图例：

$$ \begin{matrix} index= & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \ string= & a & a & b & a & a & a & a & b \ sa[0]=3;ra[0]=3 & a & a & a & a & b \ sa[1]=4;ra[1]=5 & a & a & a & b \ sa[2]=5;ra[2]=7 & a & a & b \ sa[3]=0;ra[3]=0 & a & a & b & a & a & a & a & b \ sa[4]=6;ra[4]=1 & a & b \ sa[5]=1;ra[5]=2 & a & b & a & a & a & a & b \ sa[6]=7;ra[6]=4 & b \ sa[7]=2;ra[7]=6 & b & a & a & a & a & b \ \end{matrix} $$

如何得到后缀数组

先说最暴力情况，快排 n 个后缀，但比较任意两个后缀字符串的时间复杂度为O(n)，故而总体时间复杂度为$O(n^2lgn)$，在数据量较大时会有很大问题。

倍增算法：依次对每个字符开始的长度为 $2^k$ 的子字符串进行排序，求出排名，即 rank 值。k 从 0 开始，每次加 1，当 $2^k > n$ 后，每个字符开始的长度为 $2^k$ 的子字符串便相当于所有的后缀。并且这些子字符串都一定比较出大小，即 rank值中没有相同的值，那么此时的 rank 值就是最后的结果。每次排序都利用上次长度为 $2^{k-1}$ 的字符串的 rank 值，那么长度为 $2^k$ 的字符串就可以用两个长度为 $2^{k-1}$ 的字符串的排名作为关键字表示，不够的用 0 填充，然后进行基数排序，便得出了长度为 $2^k$ 的字符串的 rank 值。下面是一个排序示例：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95

public static int[] getSuffixArray(String str){
    char[] arr = str.toCharArray();
    int n = arr.length, m = Math.max(26, n - 1); // m 是计数数组的长度，它统计的对象是 rank[i]，其范围是 [0, n - 1]

    int[] rank = new int[n + 1]; // 名次数组，表示 suffix(i) 排第几位，设立长一位避免越界判断
    int[] sa = new int[n]; // 后缀数组，表示排在第 i 位的是 suffix(sa[i])
    int[] cnt = new int[m];// 计数数组
    int[] sa2 = new int[n + 1]; // 第二关键字 sa 数组
    int[] temp; // 用于快速交换 rank 和 rank2 的临时数组

    // 初始化名次数组
    for(int i = 0; i < n; i++){
        rank[i] = arr[i] - 'a';
    }

    // 对各后缀字符串第一位进行计数排序得到后缀数组
    for(int i = 0; i < n; i++){
        ++cnt[rank[i]];
    }
    for(int i = 1; i < m; i++){
        cnt[i] += cnt[i - 1];
    }
    for(int i = n - 1; i >= 0; i--){
        /*
         * 根据原本计数排序，output[--cnt[rank[i]]] = input[i]，即 rank[i] = --cnt[rank[i]]
         * 再根据 sa[rank[i]] = i，有 sa[rank[i]] = sa[--cnt[rank[i]]] = i
         */
        sa[--cnt[rank[i]]] = i;
    }

    /*
     * 每次取各后缀后 j = 2^k 作为第二关键字，先前的 rank 值作为第一关键字，进行基数排序
     * p 代表上次排序中不同后缀字符串的数量，说明 rank[i] 的取值在 [0, p - 1]，所以更新计数数组的计算范围 m = p
     */
    for(int j = 1, p = 0; p < n && j <= n; j <<= 1, m = p){
        /*
         * suffix(i), i >= n - j 的后缀字符串不存在相隔 j 位后的第二关键字，需要后续补 0 作为第二关键字
         * 而 0 在第二关键字中最小，故插在最前面
         */
        p = 0;
        for(int i = n - j; i < n; i++){
            sa2[p++] = i;
        }

        /*
         * 这里的 sa2 表示对第二关键字进行排序的结果，由于 sa 是有序的，因此遍历得到的 sa2 也是有序的
         * 如果 sa[i] >= j，说明 suffix(sa[i]) 可以被选为第二关键字，而它会被前移到 sa[i] - j 位置作为第二关键字
         * 所以 sa2[p++] = sa[i] - j
         */
        for(int i = 0; i < n; i++){
            if(sa[i] >= j){
                sa2[p++] = sa[i] - j;
            }
        }

        // 合并两个关键字的基数排序
        Arrays.fill(cnt, 0);
        for(int i = 0; i < n; i++){
            ++cnt[rank[i]];
        }
        for(int i = 1; i < m; i++){
            cnt[i] += cnt[i - 1];
        }
        for(int i = n - 1; i >= 0; i--){
            /*
             * 先根据第二关键字对第一关键字排序，我们有 rank_out[sa2[i]] = rank[i], output1[sa2[i]] = input[i]
             * 而后根据计数排序，我们有 output2[--cnt[rank_out[i]]] = output1[i]
             * --> output2[--cnt[rank_out[sa2[i]]]] = output1[sa2[i]]
             * --> output2[--cnt[rank[i]]] = input[i]
             * --> output2[--cnt[rank[sa2[i]]]] = input[sa2[i]]
             * --> rank[sa2[i]] = --cnt[rank[sa2[i]]]
             * --> sa[rank[sa2[i]]] = sa[--cnt[rank[sa2[i]]]] = sa2[i]
             */
            sa[--cnt[rank[sa2[i]]]] = sa2[i];
        }

        /*
         * 利用空 temp 数组交换 rank 和 sa2，因为接下来要计算 rank 数组，但还需要原 rank 数组的信息，同时这样能节省内存
         * sa2[n] 设为 -1，因为上次排名的最小值从 0 开始，空串（补零）的排名应该比 0 小
         * p 代表后缀字符串中不同字符串的个数
         * 这里的 rank 值是基于两个关键字排序的 rank 值，可能存在重复，所以不能直接 rank[sa[i]] = i
         * 而后缀数组 sa 上面已经计算完成，所以判断两个关键字是否相同并更新 p 即可
         */
        temp = rank;
        rank = sa2;
        sa2 = temp;
        sa2[n] = -1;
        p = 1;
        rank[sa[0]] = 0;
        for(int i = 1; i < n; i++){
            rank[sa[i]] = sa2[sa[i]] == sa2[sa[i - 1]] && sa2[sa[i] + j] == sa2[sa[i - 1] + j] ? p - 1 : p++;
        }
    }
    return sa;
}