别来无恙
Search K

Appearance

算法刷题总结（一） ​

链表总结 ​

  1. 利用 dummy节点统一删除头节点和中间节点的逻辑
  2. 查找倒数第n个节点
    • 快慢指针法，快指针先走 n 步，慢指针再走，等快指针走到底时，慢指针即为删除的前置节点
    • 利用栈先进后出，先全部进栈，再依次弹出 n 个节点，栈顶即为删除的前置节点
  3. 删除节点时需要考虑操作节点指针之间的顺序

哈希表 ​

  1. 数值比较小且连贯时，可以用数组下标来作为哈希表
  2. 使用 set，map 来做哈希表每次 set 值的时候需要对 key 进行 hash 处理，此时对比数组直接用下标会有额外的性能开销

字符串 ​

  1. 大部分字符串都依靠双指针解决。
  2. 少部分可以利用栈和队列的数据结构以及 KMP 算法来处理。
  3. 子序列问题利用动态规划解决（见子序列问题）

单调队列 ​

底层存储 ​

  1. 单调队列也叫优先级队列，底层其实是一个堆，堆就是一棵完全二叉树，同时保证父子节点的顺序关系

单调队列应用场景 ​

  1. 滑动窗口极值问题​​：当需要在一个​​滑动窗口​​中快速获取最大值或最小值时，单调队列可以在 O(1) 时间返回极值。例如：
    • 窗口滑动时，移除窗口外的旧元素，保持队列头部始终是当前窗口的极值。
    • 每次新元素入队时，删除队列中比当前元素小（或大）的元素，保持单调性。
  2. ​子数组问题优化​​：当问题涉及寻找满足特定条件的子数组（如最短长度、最长长度、区间和限制等），单调队列可以结合​​前缀和​​等技巧，快速判断子数组的合法性。
  3. ​​动态规划优化​​：在动态规划问题中，如果状态转移方程需要从某个区间内获取极值，单调队列可以将时间复杂度从 O(n) 优化到 O(1)。

优先队列要点 ​

  1. 及时从队首弹出元素，保证队首为最值（最大或者最小）
  2. 维护队列内部单调性
  3. 队列存储下标更加通用

LeetCode 中常见的单调队列题型​​ ​

​1. ​滑动窗口极值​​

  • 239.滑动窗口最大值（模板题，必刷）
  • 剑指 Offer 59 - II. 队列的最大值

​2. ​子数组和的最短/最长问题​​

  • 862.和至少为 K 的最短子数组（结合前缀和 + 单调队列）
  • 209.长度最小的子数组（暴力超时时可用单调队列优化）

​3. ​其他区间极值问题​​

  • 1438.绝对差不超过限制的最长连续子数组（维护两个单调队列，分别存最大值和最小值）

​单调队列的实现要点​​ ​

​1. ​队列中存储索引​​（而非直接存储数值），便于判断元素是否在窗口内。 ​2. ​维护单调性​​：插入新元素前，从队列尾部删除破坏单调性的元素。 ​3. ​删除过期元素​​：窗口滑动时，检查队首元素是否超出窗口范围，若超出则移除。

单调栈 ​

单调栈是栈的变种，通过维护栈内元素的单调性（单调递增或单调递减），其依赖输入顺序，主要用来处理“邻近”关系。 其与优先队列的区别在于：单调栈解决​​顺序敏感​​的局部单调问题，优先队列解决​​动态全局优先级​​问题

单调栈应用场景 ​

  1. 邻近问题：下/上一个更大/小元素
  2. 区间边界问题（在栈口形成凹形或者凸形结构）：接雨水、矩形面积

单调栈核心要点 ​

  1. 及时弹出无用元素
  2. 维护栈内单调性
  3. 栈内存储下标值更通用
  4. 对于单调递增栈，经常会在左右两边预填充 0（[84] 柱状图中最大的矩形），防止边界问题

二叉树 ​

种类 ​

  1. 满二叉树：如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上。
  2. 完全二叉树：除了最底层节点可能没填满外，其余每层节点数都达到最大值，同时最底层节点从左到右依次排列。
  3. 二叉搜索树：二叉搜索树是一个有序树。
    • 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
    • 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
    • 它的左、右子树也分别为二叉排序树。
  4. 平衡二叉搜索树：又被称为AVL（Adelson-Velsky and Landis）树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
    • C++中map、set、multimap，multiset的底层实现都是平衡二叉搜索树，所以map、set的增删操作时间时间复杂度是logn；
    • unordered_map、unordered_set，unordered_map、unordered_set底层实现是哈希表。

存储方式 ​

  1. 链式存储：通过用链表指针的形式把分布在各个地址的节点串联一起。
  2. 顺序存储：通过用数组的形式顺序存储，其元素在内存是连续分布的。父节点的数组下标是 i，那么它的左孩子就是 i *2 + 1，右孩子就是 i* 2 + 2

遍历方式 ​

  1. 深度优先搜索（前中后，其实指的就是中间节点的遍历顺序）
    • 前序遍历（递归法[底层是 函数调用栈]，迭代法[利用栈模拟递归]）
    • 中序遍历（递归法，迭代法）
    • 后序遍历（递归法，迭代法）
    • DFS遍历方式
  2. 广度优先搜索
    • 层次遍历（迭代法[利用队列]）

递归三步曲 ​

  1. 确定递归终止条件
  2. 确定递归的参数和返回值
  3. 确定单层递归的逻辑

回溯算法 ​

回溯算法是一种暴力搜索的思想，通常回溯过程发生在递归函数的下一步。

回溯算法应用场景 ​

  1. 数组组合问题
  2. 数组排列问题（排列强调顺序，组合不强调顺序）
  3. 字符串切割问题
  4. 数组求子集问题
    • 每个元素都可以 选｜不选，背包问题也是一种子集型回溯
  5. 棋盘问题（N 皇后问题、解数独问题）

回溯算法模版 ​

  1. 回溯算法一般是在集合中递归搜索，并且解决的问题都可以抽象为一颗树形结构，其中集合的大小构成了树的宽度，递归的深度构成的树的深度。 backtracking
text
function backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

关于去重 ​

  1. 去重前需要判断是否应该对集合排序
  2. 树层上在 for 循环前可以用 set 来去重，每次递归重新声明。
  3. 树枝去重（排列问题）需要用 visited 数组传入递归函数中去重。
text
function backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    // 声明 set 来做树层去重
    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
         if (set.has(选择)) {
               continue; // 树层去重
         }

         // 基于数组排序前提下，判断当前节点和上一个节点值相同
         if (当前节点和上一个节点值相同 && visited[上一节点] == false) {
               continue; // 树枝去重
         }

        处理节点;
        visited[选择] = true; // 处理节点
        backtracking(路径，visited, 选择列表); // 递归
        回溯，撤销处理结果
      visited[选择] = false; // 回溯
    }
}

贪心算法 ​

  1. 贪心算法是从局部最优解出发，推导出全局最优解的一种算法设计思想。
  2. 在做贪心算法类题目时可以通过思考每个阶段的局部最优解是什么？局部最优能否推出全局最优。至于如何思考局部最优，更多是通过分析题目以及反证法的思路来进行推导。

难点题目 ​

135.分发糖果 406.根据身高重建队列 763.划分字母区间 738.单调递增的数字 968.监控二叉树

动态规划 ​

内容较多，拆分到算法刷题总结二