WRY

Where Are You?
You are on the brave land,
To experience, to remember...

0%

算法题目分类归纳（题库版）

Posted on Edited on In
算法题目的分类整理，包括了自己见过的所有题目，但目前还是比较乱，之后回顾的时候会继续梳理。

说明

本篇内容主要是包含了见过题目的收集，内容过多而且存在很多重复，不利于复习，只适合查询。内容的归纳可参考算法题目分类归纳（目录版）博客。

题目来源

题目来源为

关于标签

在归类策略中，会尽量根据题目最突出的特点进行归类，十分经典的多解法题目也会被重复放到不同的目录下。但其中一些稍微复杂的题目中，会有很多不同的基础部分来支持或者其他解法没有那么有特色的情况，对此将会采用标签的方式进行说明，可以通过搜索标签来发现一些基础组件在更复杂题目中的应用场景。下面是标签集合：

双端队列 动态规划 中心扩展 Manacher KMP BFS DFS 双向BFS 边界二分 双指针 单调栈 优先级队列 归并排序 滑动窗口 四边形不等式 数学归纳 约瑟夫问题 累加和 并查集 Kruskal Tarjan 前缀和 最接近目标 循环数组 最短路径 状态机

实现代码

参见 Github，最开始的很多题目缺少必要的注释和清晰的代码结构，再后续添加的过程中，正逐步改正该问题。

数据结构及其应用

栈

普通栈

单调栈

单调栈的逻辑切入点是：我遍历到当前列的时候，我能给栈中那些列赋予什么信息；去掉栈中这些列之后，栈中剩下的元素能给当前列什么信息。根据上述的逻辑判断在while循环中弹出元素时使用的大于小于号。

堆

优先级队列

集合

队列

双端队列

链表

单向链表

遍历链表
反转链表
删除链表节点
重排链表

双向链表

相交链表

成环链表

快慢指针的形式，从head开始走，如果相遇了，说明有环路。设非环路长为\(l\)，环路长度为\(q\)，相遇位置是从环路起点之后又走了\(k\)。那么
fast指针的走的路长是：\(len_{fast}=l+a \cdot q+k\)，
slow指针走的路长是：\(len_{slow}=l+b \cdot q+k\)，
而且他们之间的关系是：\(len_{fast}=2 \cdot len_{slow}\)，
处理之后\(2 \cdot l+2 \cdot b \cdot q+2 \cdot k=l+a \cdot q+k\)，化简得，\(l=(a-2 \cdot b-1) \cdot q+(q-k)\)，
此时让slow指针和头指针一起一个一个的走，直到相遇就是环形节点的头节点，因为他们第一次相遇的时候，满足上面的化简公式。

复杂链表

数组

数组操作

矩阵操作

子数组累加和

最优子矩阵

子矩阵问题从暴力求解开始思考，简化遍历步骤，优化算法。

头疼还未分类

并查集

哈希

树

二叉树

二叉树的遍历

二叉树的遍历方式有先序遍历、中序遍历、后序遍历以及层次遍历。前三种方式都以通过递归的方式有效的实现，但是非递归的方式会显得复杂很多，这里简单记录一下非递归实现先中后序遍历的方式。（注释总结的感觉还是比较乱）

  • 先序遍历

    一个栈先压头节点，然后每次取中栈顶元素，按照打印其值，压入右孩子，再压入左孩子的方式进行实现

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    stack<node *> sta;
    sta.push(head); // 压入头节点
    // 对于每个节点的遍历顺序：父节点 --> 正序所有左孩子 --> 右孩子
    // 压栈顺序正好反过来，（正序反过来就是压一个）
    while(sta.size()){
      node *t = sta.top(); sta.pop();
      doSomething(t); // do something
      if(t->right) sta.push(t->right);
      if(t->left) sta.push(t->left);
    }

  • 中序遍历

    1. 把头节点及其所有左孩子压入栈中；
    2. 取中栈顶元素cur， dosomthing; cur=cur.right;
    3. 重复步骤2，3。直到栈为空
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    stack<node *> sta;
    node *cur=head;
    // 遍历顺序
    // 逆序所有的左孩子 --> 父节点 --> 右孩子的所有左孩子
    // 压栈顺序正好反过来，（逆序反过来就是压所有）
    while(cur||sta.size()){
      while(cur){sta.push(cur); cur=cur->left;} // 压入cur及其全部的左孩子
      cur=sta.top(); sta.pop(); // 取出栈顶元素
      doSomething(cur); // do something
      cur=cur->right;
    }

  • 后序遍历

    • 使用两个栈来实现，最终s2的弹出顺序就是后序遍历的结果

      栈分别命名为s1和s2；

      1. 将头节点压入s1
      2. 取中s1的栈顶元素cur，然后依次压入其左、右孩子到s1中，然后将cur压入s2
      3. 重复步骤2，直到s1为空
      4. 弹出s2，就是遍历的结果
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      stack<node *> s1, s2;
      s1.push(head);
      // 和下面用一个栈的思路反过来，后序遍历的反序，总是
      // 父节点 --> 正序所有右孩子 --> 正序所有左孩子 压栈的时候反过来压（正序只压一个）
      while(s1.size()){
        node *cur=s1.top(); s1.pop();
        if(cur->left) s1.push(cur->left);
        if(cur->right) s1.push(cur->right);
        s2.push(cur);
      }
      while(s2.size()){
        node *cur=s2.top(); s2.pop();
        doSomething(cur);
      }

    • 使用一个栈来实现

      一个栈sta，两个指针h，c；h指向最近一次弹出打印的节点，c指向栈顶的节点

      1. 先将头节点压入到栈中，初始化h为head，c为null
      2. 先令c等于栈顶元素，但不弹出
        1. c的左孩子不为null，且h和c的左右孩子都不相等：压入c的左孩子
        2. c的右孩子不为null，且h和c的右孩子不相等：压入c的右孩子
        3. 弹出并打印c，另h=c
      3. 重复步骤2，直到栈为空
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      stack<node *> sta;
      // h=head只是为了让h有个初始值，不和head的左右孩子以及空指针相等
      sta.push(head); node *h=head, *c=nullptr;
      while(sta.size()){
        c=sta.top();
        // 核心要义，左右孩子都打印完了，再打印父亲
        // 打印父节点的之前，一定刚刚打印过了他的孩子（如果有的话）。注意这里的顺序
        // 逆序所有左孩子 --> 逆序所有右孩子 --> 父节点 （针对所有节点都成立（若孩子不存在就顺位））
        // 反过来是 父节点 --> 左孩子 --> 右孩子（注意这里一次只压入一个，和上面的都不同）
        if(c->left&&c->left!=h&&c->right!=h) sta.push(c->left);
        else if(c->right&&c->right!=h) sta.push(c->right);
        else{
          sta.pop();
          doSomething(c);
          h=c;
        }
      }
二叉树的重建
二叉树的查找
二叉搜索树
平衡二叉搜索树
完全二叉树
其他

线段树

前缀树（字典树 Trie Tree）

有序表

字符串

基础操作

翻转

编辑 & 匹配

这两类字符串题目的主要解题思想都是 递归 和动态规划

括号

回文

回文类型的题目有四大类：

  • 问题一：判断字符串是不是回文
  • 问题二：找出最长回文子串
    • 穷举子串，转化成问题一
    • 动态规划，dp[i][j] 代表str[i:j]是否是回文子串
    • 中心扩展法，从每个中心出发，暴力计算
    • Manacher，在中心扩展的基础上，利用存储的信息，加速判断
  • 问题三：添加最少字符让字符串变成回文
    • 动态规划，dp[i][j] 代表str[i:j]需要添加的字符
    • 在找到最长回文序列之后，剥洋葱
  • 问题四：最长回文子序列

子串

翻译

阿拉伯数字、英文表示、中文表示的翻译

阿拉伯数字转中文数字，参考解读。简单记录一下

  1. 将阿拉伯数字按万进行划分成节
  2. 节内划分为“”、“十”、“百”、“千”
  3. 节之间划分为“万”、“十万”、“百万”、“千万”、“亿”、“万亿”...
  4. 关于零的使用：
    1. 若小节之后都是0，则不加零，例如1,0000，中文为一万
    2. 小节之内的两个数字要加零，例如101，中文为一百零一
    3. 若千位是0，且前一小节无其他数字，则不用加零，否则加零，例如1,0100，中文为一万零一百；1,1000，中文为一万一千

其他

图

转换路径

无环图

联通图

最小生成树

最小生成树有两种解法：逐个添加最优边的Kruskal和逐个添加最优顶点的Prim算法。

最短路径

最短路径有两种思路：

  • Dijkstra 计算所有点到某个点的最短路径和距离，可以有环，权值需要为正，时间复杂度\(O(ElogV)\)
  • Floyd 计算所有点到所有点的最短路径和距离，不可以有环，权值可为负数

拓扑排序

三角形

  • 1761 5679 一个图中连通三元组的最小度数 困难

    • 审题：节点数量较少的时候，应该优先考虑使用矩阵来存储边
    • 暴力枚举三角形的三重循环，起始位置递增
      for(i=1;i<=n;++i) for(j=i+1;j<=n;++i) for(k=j+1;k<=n;++i)
    • 竞赛题目，十分遗憾，也暴露出了自己爱钻牛角尖，缺乏充分思考的致命弱点
    • 新年之后第一场竞赛，祝福大家一切顺利！

算法思想及其应用

暴力

搜索

BFS

DFS

二分

基础二分
基础二分的应用
边界二分
有旋数组
其他

尺取（双指针）

滑动窗口

状态机

排序

倒排索引

递归 & 动态规划

动态规划类型的问题，在《程序员代码面试指南--刷题小结》中也有粗略的总结，但是缺少了整体思想的分析。根据《labuladong的算法小抄》中的解释，做点补充。

最开始的思路应该是，如何穷举所有的情况？ 在能穷举出所有的情况的时候，找去其中存在的“重叠子问题”（需要找出其中存在的“状态”，争取尽量简单）来减少重复的计算量，同时需要保证具有“最优子结构”，即子问题间必须相互独立，最后确定状态转移方程。

递归

斐波那契

背包

背包问题根据labuladong的整理，可以分为0-1背包、子集背包和完全背包

涂颜色

丢鸡蛋

非常经典的题目，有三种不同时间复杂度的解法

  1. dp[k][n] \(k\)个鸡蛋\(n\)层楼，状态转移方程：

    1
    2
    for i in range(1, n+1):
      res=min(res, max(dp(k-1, i-1), dp(k, n-i))+1)

    base case：

    1
    2
    if k==1 return n
    if N==0 return 0

  2. 在上述方法中，因为dp(k, n)若\(k\)是定值，\(n\)是变量，则函数是单调的，因此可以使用二分查找最佳i的位置

  3. 重新定义状态dp[k][m] \(k\)个鸡蛋，最多扔\(m\)次可以检查到的最高楼层，状态转移方程如下

    1
    dp[k][m]=dp[k-1][m-1]+dp[k][m-1]+1 # 注意是相加的关系

    base case：

    1
    2
    dp[0][:]=0
    dp[:][0]=0

戳气球

经典动态规划问题，定义状态

dp[i][j]为打破\((i, j)\)气球，同时气球\(i\)和\(j\)还在时候的最大得分。在原来的气球序列的两侧添加上值为1的两个虚拟气球，dp[0][n+1]就是最终的答案，状态转移方程：

1
2
for k in range(i+1, j):  # 枚举最后打破的位置k
  dp[i][j]= max(dp[i][j], dp[i][k]+dp[k+1][j]+dp[i]*dp[j]*dp[k])

石子游戏

两人博弈问题，本质上还是动态规划

给定数组，每次取左侧一个元素或者右侧一个元素，使用动态规划进行解决，首要问题是提取状态，在5687题目中，学习到了一种非常巧妙的状态表示方法，如下：

1
dp[i][j] // 表示从数组前面取了i个数字，从后面取了j个数字。

屠龙勇士

正确解法：反向思考从每个位置到终点需要最少的血量。正向思考难以权衡最少需要的血量和剩余的最大血量，会陷入局部最优。
可以尝试关联一下 CD53 加油站良好出发点问题，感觉有种微妙的联系

打家劫舍

买卖股票

买卖股票模型中最复杂的是带交易次数限制的。在动态规划中状态的定义是：dp[k][i][0/1] 表示在i天最多k次交易时持有或者不持有的最大收益；在状态转移方程中的体现是：第k次的持有状态不能由第k次未持有状态转移得到。

最长公共子序列

回溯

数独

子集

全排列

有效括号

贪心

最长递增子序列

最长公共子序列问题也可以使用动态规划来解，但动态规划的时间复杂度是\(O(n^2)\)，而贪心算法的时间复杂度是\(O(nlogn)\)。

加油站良好出发点

算是贪心的思想吗？

从一个盈余大于等于0的位置start出发，负债为0，走到最远位置end（没有剩余或者已走一圈），若走够了一圈，该起始点是一个良好出发点；否则该位置不是良好出发点。然后回退到上一个位置：
若盈余大于等于负债， 将（盈余-负债）送到end，负债改成0，继续向前走到最远位置，判断该点是否是良好出发点
否则，计算新的负债，因为有负债，所以该位置不是良好出发点
继续回退上一个位置，开始上述判断，直到所有点都检查一遍。

分治

  • 1755 5675 最接近目标值的子序列和 困难 最接近目标

    不能暴力穷据所有的，但是可以分两部分暴力穷举，然后再结合查找

  • 395 至少有 K 个重复字符的最长子串 中等 1763 5668 最长的美好子字符串 简单 分治

    计算字符串中不满足要求的字符，根据这些字符对字符串进行切割，从子串中寻找最优答案

    切割算法

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    string s;
    unordered_set<char> st;
    int i, j, start, end; // 在[start, end)范围中，根据在st中的字符对字符串进行切分
    i=start;
    for(j=start;j<=end;++j){
      if(j==end||st.count(s[j])){
        func(s, i, j); // 找到一个切分段[i,j); 可能会出现i==j和i+1==j的无穷递归，需要在func最开始的位置进行拦截
        i=j+1;
      }
    }

    优秀题解

    滑动窗口

    可以知晓最终答案中字符的类型数量是1-26中的一个值，通过穷举来获取答案。针对每次假设最终有k中类型字符，通过滑动窗口的思想去找每个位置能允许的最左位置

空间利用

数学问题相关

数字边界

计算

计算器

  • 字符串处理类型的题目，先考虑好基本的处理模块，每个模块从哪一位开始处理，结束的时候在哪一位。
  • 计算器类型的题目，只有加减的：先设置基数为0，默认加法，然后按照读数，读符号的循环开始处理
  • 计算器类型的题目，加减乘除的：默认算术符号是'+'，读数字，运算，更新符号

算术优先级表格法

定义如下的表达式的文法，是没有二义性的，开始符号为\[E\].（大写字母均是非终结符号） \[ \begin{array}{l} \mathrm{E} \rightarrow \mathrm{E}+\mathrm{T} \mid \mathrm{T} \\ \mathrm{T} \rightarrow \mathrm{T} * \mathrm{~F} \mid \mathrm{F} \\ \mathrm{F} \rightarrow(\mathrm{E}) \mid \mathrm{id} \end{array} \]

FirstVt的查找规则如下

  • \(A\rightarrow a...\)，将a加入A的Firstvt中
  • \(A \rightarrow Ba...\)，将a加入A的Firstvt中
  • \(A\rightarrow B...\)，将非终结符B的Firstvt加入A中

LastVt的查找规则如下，和FirstVt的规则正好相反

  • \(A \rightarrow ...a\)，将a加入A的LastVt中
  • \(A \rightarrow ...aB\)，将a加入A的LastVt中
  • \(A \rightarrow ...B\)，将非终结符B的LastVt加入A中

由此我们得出

FirstVt LastVt
\(E\) \(\{(, id, *, +\}\) \(\{), id, *, +\}\)
\(T\) \(\{(, id, *\}\) \(\{), id, *\}\)
\(F\) \(\{(, id\}\) \(\{), id\}\)

按如下规则逐条扫描文法

  1. \(E\rightarrow (E)\)，则有\((=)\)

  2. 终结符在左边，非终结符在右边

    1. \(+T\)，\(+ < FirstVt(T)\)
    2. \(*F\)，\(*<FirstVt(F)\)
    3. ...

  3. 非终结符在左边，终结符在右边

    1. \(E+\)，\(LastVt(E)>+\)
    2. ...

最终计算得到算术优先表格

一个更为详细的例子，参考

1
2
3
4
5
6
7
8
9
10
11
12
13
14
char table[9][9] = {   //算符优先级表
//           +   -   *   /   ^   !   (   )   $    // 当前运算符
    /* + */ '>','>','<','<','<','<','<','>','>',
    /* - */ '>','>','<','<','<','<','<','>','>',
    /* * */ '>','>','>','>','<','<','<','>','>',
    /* / */ '>','>','>','>','<','<','<','>','>',
    /* ^ */ '>','>','>','>','>','<','<','>','>',
    /* ! */ '>','>','>','>','>','>',' ','>','>',
    /* ( */ '<','<','<','<','<','<','<','=',' ',
    /* ) */ ' ',' ',' ',' ',' ',' ',' ',' ',' ',
    /* $ */ '<','<','<','<','<','<','<',' ','='
    // 栈顶运算符
};
// 作者：dongzengjie

用法，先在表达式左右两侧添加$号，形如$1+2*(3+4)$，一个算数栈num，一个符号栈op。op初始化压如$ ，结束的时候再压如一个$。

数字计算好之后直接入数字栈

符号：

  • 若栈顶符号优先级低，继续压栈
  • 若栈顶符号优先级相等，弹出栈顶，且不压栈
  • 若栈顶符号的优先级更高，弹出符号进行计算（不需要循环处理，斜对角线的需要计算的优先级都是>）

位运算

最大公约数

阶乘

快速幂

开平方

进制转换

取余数

二进制

X出现的次数

几何

数学规律

分段乘积最大值

坐板凳

等概率

Rand

  1. 拒绝采样，rand7，通过两次调用，可以生成0-49个随机数，砍掉不满10个数的部分
  2. 在拒绝采样的部分，继续测试
  3. 进制来实现

蓄水池算法

从未知长度的数据流中随机取出k个数

思路是：每个数被最终选中的概率都是被选中的概率 * 不被替换的概率，伪代码如下。

1
2
3
4
5
6
7
8
9
10
vector<int> calc(vector<int> arr, int k){
  vector<int> ans(arr.begin(), arr.begin()+k);
  int i=k, n=arr.size(), j;
  for(;i<n;++i){
    if((j=(rand()%(i+1))<k){
      ans[j]=arr[i];
    }
  }
  return ans;
}

洗牌

  • 逐次随机抽取

    随机抽取一张牌，直到抽出所有的牌就是最终的洗牌结果

  • 多次随机交换

    随机抽两张牌进行交换，抽的次数足够多就完成了洗牌

  • Fisher–Yates shuffle算法

    每次随机选取一个数，然后将该数与数组中最后(或最前)的元素相交换(如果随机选中的是最后/最前的元素，则相当于没有发生交换)；然后缩小选取数组的范围，去掉最后的元素,即之前随机抽取出的数。重复上面的过程，直到剩余数组的大小为1，即只有一个元素时结束。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    void shuffle(int* array, int len) {
      int i = len;
      int j = 0;
      
      while (--i>0) {
        j = rand() % (i + 1);
        swap(array[i], array[j]);
      }
    }

数学技巧

其他

模拟

简单

未分类 牛客

未做

数据库

待分类

多线程

锁 & 信号量

Shell

题外篇

刷题历程

  • 《程序员代码面试指南》是本好书，在牛客网上刷了80%的时候，我懒散了，丝毫没有做下去的动力，不过按照这本书的目录来刷题，的确会让人很愉快，因为你知道你自己做的题归属于哪一类。

  • 为了增强自己的自信心，我开始在leetcode上刷《剑指offer》，然后就刷完了，记不清自己有什么收获，该错还是错，但是确实比第一遍做到时候要顺利很多。

  • 某一天突然买了leetcode的会员，本着充分利用的会员的资源，我根据题号，筛选高频题刷起，刷着刷着就自闭了，题目之间的联系太少了，很多时候都变成为了AC而在做。(其实是因为困难和中等的占比太大了)

  • 观察了身边的同学，我发现了《labuladong的算法小抄》，发现和《程序员代码面试指南》一样都是归纳整理之后的题目，不同点在于这本书的分类更偏向于框架思想，不看内容已经爱了，doing...

    据说labuladong涉嫌抄袭，知乎链接， 尊重知识产权，如果真是抄袭的，不建议你再购买本书。

  • 最近又看上了《程序员面试金典》，10天不买零食小吃，就买下来...在此之前，重新归纳整理一遍做过的算法题吧，男人的嘴，骗人的鬼，书已经买了，零食一天都没少。

  • 眼看春招就要开始了，突然发现自己做题的能力貌似被遗忘了，有点难过。接下来以巩固复习为主！

  • 5勋章、500道题、全站前5000，在2021年4月的最后一天，向5月问好～
    在leetcode上已经有规律刷题半年的时间了，随着刚开始的时而癫狂、时而懒散，到慢慢地变成生活的习惯。感谢力扣伴我成长！

  • 2021年7月31日，600题了。开始出现了松懈的苗头，这个月的补卡券都不够用的了。在这里也提醒自己要做题先想好思路，不要着急动手，少用debug，提升通过率。

  • 2021年8月31日，700题了。回顾经典书籍中的算法题十分的重要而有意义。继续提醒自己，先想好思路再下手，注意边界问题的解决，提升通过率。

  • 2021年9月20日，800题了。中秋节前夕，祝福团圆永远。

  • 2021年11月10日 16:20，会员到期前的1分钟。想想去年今日，时间过的可真快。

致谢

  • 感谢与我一起刷题的伙伴们，互相“嘲讽”，互相帮助，让我可以保持着刷题的动力， DML 401 加油！
  • 感谢我的本科同学，ACM大佬，顶会论文作者，小帕，无数次帮我debug 乱麻般的代码，让我没有那么多烂尾，保持着继续下去的热情。

存储点：2021.08.08