Skip to content
知识库

线形常用算法

双指针

双指针算法可以处理以下问题

快慢指针

  1. 查找链表倒数第 K 个节点（中间节点）
  2. 判断链表是否存在环
  3. 对有规律的数进行处理。例如删除有序数组中的重复数组，将数组的 0 都移动到最前面等等

头尾（左右）指针

  1. 数组的二分查找
  2. 判断回文字符串
  3. 反转数组

前缀、后缀和

主要用于计算差值，例如可以快速计算出一个区间的数据之和。需要注意的是，想计算前缀积、后缀积的时候，需要考虑 0 的影响

差分数组

前缀和可以很方便计算出区间之和，但是无法对一个区间进行快速修改，例如将 [i,j] 区间全部加上 3，此时可以使用差分数组

以数组 diff 来计算前后差值，即 i === 0 ? diff[0] = 0 : diff[i] = nums[i] - nums[i-1];，特殊处理第 0 位

后续数组可以使用差分数组 + 数组的初始值进行还原

nums[0] = initValue;
for (let i = 1; i < diff.length; i++) {
  nums[i] = nums[i - 1] + diff[i];
}

如果想对[i,j]区间的数进行修改，则可将查分数组的 diff[i] += k; diff[j+1] -= k

滑动窗口

滑动窗口核心便是维护该窗口，那么满足如下判断

  1. 在某个条件下，可以扩展窗口
  2. 在某个条件下，可以收缩窗口

并且，不能出现模糊的情况，例如此时扩展窗口和收缩窗口都可以满足条件

固定窗口

窗口中元素个数确定。

举个例子，固定窗口可以用来求字符的排列情况，例如在字符 S 中，寻找字符 P 的排列。在匹配方面有些技巧

  1. 可以使用数组存储字符 P 的每个位数，每一次比较需要遍历整个数组
  2. 可以使用数字来表示目前匹配上的个数，当匹配个数 === P.length 时，完成匹配

伸缩窗口

窗口中元素个数不确定。在字符 S 中，寻找一个连续的子字符串，使其包含字符 N，求最短的子字符串

二分法

有序数组的二分

山峰数组的二分

矩阵

矩阵旋转 90°

[123456789]\begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \\ \end{bmatrix} 将矩阵旋转 90°，即将上述矩阵旋转为如下矩阵。 [741852963]\begin{bmatrix} 7 & 4 & 1 \\ 8 & 5 & 2 \\ 9 & 6 & 3 \\ \end{bmatrix}

螺旋矩阵

矩阵的二分

其他解法

优势洗牌（田忌赛马）

田忌赛马的核心就是拿自己的劣等马去送，以消耗优等马，那怎么判断该硬拼还是送呢，总结起来就是“打得过就打，打不过就送”

  1. 如果此次对拼，可以获胜，则拿一个可以略胜的马对拼
  2. 如果此次对拼，无法获胜，则拿一个最弱的马送

按照如下步骤思考

  1. 将 A 组降序排序，好马在前
  2. B 组
    1. 如果无需按 B 组的出场来输入顺序，可以将 B 组依旧降序排序，通过 A、B 双指针比较
    2. 如果需要排序，则按照 [value, index]，并按照 value 降序排序，通过 A、B 双指针比较

如何在数组中以 O(1)删除或添加数

对数组来说，末尾的插入和删除是不需要数据移动的，即满足 O(1)，当对数字没有顺序的前提下，可以将数移动到末尾，进行删除