[数据结构与算法]力扣记录：代码随想录总结

前言

• 花费两个月刷完了代码随想录，通过分类型地学习与做题，让我对算法有了更深入的认识，打下了牢固的基础，感谢代码随想录，感谢carl哥！

一、数组

• 一般数组、字符串（可以转为字符数组）都可以考虑以下方法

二分查找

• 遇到数组有序，且无重复元素
• 数组无序也可考虑排序，有重复元素也可考虑使用二分法查找左右边界
• 时间复杂度O(logn)
• 应用：数组的查找问题
• 题目
  • 704 二分查找、35 搜索插入位置、34 在排序数组中查找元素的第一个和最后一个位置、69 x的平方根、367 有效的完全平方数

双指针

• 快慢指针：两个指针都从头开始，速度不一样。一个for循环实现两个for循环的功能
• 左右指针（对撞指针）：两个指针分别从首尾出发，速度看情况。
• 两个指针可以指向同一个数组，也可以分别指向不同数组
• 题目
  • 27 移除元素、26 删除排序数组中的重复项、283 移动零、844 比较含退格的字符串、977 有序数组的平方

滑动窗口

• 实际上依赖双指针：快慢指针分别指向窗口左右边界
• 固定窗口大小
• 动态更新窗口大小
• 应用：求某个子串或子数组的最值问题，或求某个目标值。
• 题目
  • 209 长度最小的子数组、904 水果成篮、76 最小覆盖子串

螺旋矩阵

• 模拟，注意边界的判断
• 题目
  • 59 螺旋矩阵II、54 螺旋矩阵、剑指Offer 29 顺时针打印矩阵

二、链表

• 操作链表时尽量设置虚拟头节点指向链表头节点，处理完后返回虚拟头节点的next即可，这样不需要对链表头节点单独拉出来处理。
• 链表的增删改查
• 题目
  • 203 移除链表元素、707 设计链表
  • 206 反转链表、24 两两交换链表中的节点
  • 19 删除链表的倒数第N个节点、面试题02.07 链表相交、142 环形链表II

三、哈希表

• 将数组作为哈希表，每个下标对应一个key：一般是限定了输入范围，数字、小写字母、大写字母等
• 求交集、需要去重的情况使用set
• HashMap
• 题目
  • 242 有效的字母异位词、383 赎金信、49 字母异位词分组、438 找到字符串中所有字母异位词
  • 349 两个数组的交集、350 两个数组的交集II
  • 202 快乐数、1 两数之和
  • 454 四数相加II、15 三数之和、18 四数之和

四、字符串

• 字符串也常用双指针法
• KMP：使用前缀表解决匹配问题和重复子串问题
• 题目
  • 344 反转字符串、541 反转字符串II
  • 剑指Offer05 替换空格、151 翻转字符串里的单词、剑指Offer58II 左旋转字符串
  • 28 实现strStr()、459 重复的子字符串

五、双指针

• 针对数组、字符串和链表问题都可以使用双指针，降低时间复杂度
• N数之和，三数、四数之和用双指针，两数之和用哈希表
• 之前使用双指针的题目

六、栈与队列

• 理解栈和队列的原理，两个栈实现队列、一个队列实现栈。
• 栈解决匹配问题（括号匹配、逆波兰表达式）、字符串去重问题
• 单调队列：维护队列中元素递增或递减（手动实现）
• 优先级队列：大（小）顶堆，priorityQueue默认是大顶堆
• 求前k大使用小顶堆；求前k小使用大顶堆
• 题目
  • 232 用栈实现队列
  • 225 用队列实现栈
  • 20 有效的括号
  • 1047 删除字符串中的所有相邻重复项
  • 150 逆波兰表达式求值
  • 239 滑动窗口最大值
  • 347 前 K 个高频元素

七、*二叉树

• 二叉树问题一定要掌握递归！递归时注意前中后序的要求！

7.1 二叉树的遍历

• 递归遍历（深度优先）：前序、中序、后序，使用栈实现迭代遍历（模拟）

• 层序遍历（广度优先）：使用队列实现

• 题目：

  • 144 二叉树的前序遍历、94 二叉树的中序遍历、145 二叉树的后序遍历
  • 102 二叉树的层序遍历、107 二叉树的层次遍历II、199 二叉树的右视图、637 二叉树的层平均值、429 N叉树的层序遍历、515 在每个树行中找最大值、116 填充每个节点的下一个右侧节点指针、117 填充每个节点的下一个右侧节点指针II、104 二叉树的最大深度、111 二叉树的最小深度
  • 226 翻转二叉树

7.2 二叉树的属性

• 二叉树深度：
• 二叉树高度：
• 递归函数有返回值：找到一条符合条件的路径即可
• 递归函数没有返回值：找到所有符合条件的路径
• 题目
  • 101 对称二叉树、100 相同的树、572 另一个树的子树
  • 104 二叉树的最大深度、559 n叉树的最大深度、111 二叉树的最小深度
  • 222 完全二叉树的节点个数、110 平衡二叉树、257 二叉树的所有路径、100 相同的树
  • 404 左叶子之和、513 找树左下角的值、112 路径总和、113 路径总和II

7.3 二叉树的修改与改造

• 构造二叉树：前序和中序、后序和中序可以唯一确定一颗二叉树。构造时直接通过下标索引操作原数组节省空间，注意下标边界。
• 需要同时操作两个二叉树时使用队列模拟层序遍历。
• 题目
  • 226 翻转二叉树、
  • 106 从中序与后序遍历序列构造二叉树、105 从前序与中序遍历序列构造二叉树、654 最大二叉树、617 合并二叉树

7.4 求二叉搜索树的属性

• 二叉搜索树：左子树比根节点小，右子树比根节点大。中序遍历为有序数组
• 完全二叉树：每一层左侧节点是满的
• 满二叉树：每一层的节点都是满的
• 满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树
• 题目
  • 700 二叉搜索树中的搜索、98 验证二叉搜索树、530 二叉搜索树的最小绝对差、501 二叉搜索树中的众数、538 把二叉搜索树转换为累加树

7.5 二叉树公共祖先问题

• 后序、回溯
• 题目
  • 236 二叉树的最近公共祖先、235 二叉搜索树的最近公共祖先

7.6 二叉搜索树的修改与改造

• 题目
  • 701 二叉搜索树中的插入操作、450 删除二叉搜索树中的节点、669 修剪二叉搜索树、108 将有序数组转换为二叉搜索树
  • 538 把二叉搜索树转换为累加树

八、*回溯算法

8.1 组合

• 求一个集合符合条件的组合需要使用startIndex来控制递归的起始下标
• 求多个互相不影响的集合符合条件的组合可以不使用startIndex
• 注意剪枝优化和结果去重
• 时间复杂度O(n * 2 ^ n)，空间复杂度O(n)
• 题目
  • 77 组合、17 电话号码的字母组合、216 组合总和III、39 组合总和、40 组合总和II

8.2 分割

• 分割问题类似组合问题，需要注意分割的边界
• 题目
  • 131 分割回文串、93 复原IP地址

8.3 子集

• 子集问题需要收集所有节点的结果，组合问题需要收集叶子节点的结果
• 同样注意剪枝和去重问题
• 时间复杂度O(n * 2 ^ n)，空间复杂度O(n)
• 题目
  • 78 子集、90 子集II

8.4 排列

• 排列是有序的，组合是无序的；排列每次都从下标0开始，组合是从startIndex开始
• 排列需要使用used数组记录使用过的元素来去重
• 时间复杂度O(n !)，空间复杂度O(n)
• 题目
  • 46 全排列、47 全排列II

8.5 棋盘问题

• 二维递归回溯
• 题目
  • 51 N皇后
    • 时间复杂度O(n !)，空间复杂度O(n)
  • 37 解数独
    • 时间复杂度O(9 ^ m)，空间复杂度O(n ^ 2)

8.6 其他

• 图论的深度搜索问题：332
• 题目
  • 491 递增子序列、332 重新安排行程

九、贪心算法

• 找出局部最优，推出全局最优

9.1 简单

• 455 分发饼干、1005 K次取反后最大化的数组和、860 柠檬水找零

9.2 中等

9.2.1 序列问题

• 376 摆动序列、738 单调递增的数字

9.2.2 *股票问题

• 结合动态规划方法
• 题目
  • 122 买卖股票的最佳时机II、714 买卖股票的最佳时机含手续费

9.2.3 两个维度权衡问题

• 先确定一个维度再计算另一个维度
• 题目
  • 135 分发糖果、406 根据身高重建队列

9.3 较难

9.3.1 *区间问题

• 55 跳跃游戏、45 跳跃游戏II、452 用最少数量的箭引爆气球、435 无重叠区间、763 划分字母区间、56 合并区间

9.3.2 其他

• 53 最大子序和、134 加油站、968 监控二叉树

十、*动态规划DP

• 动规五步：定义dp数组、确定递推公式、初始化dp数组、确定遍历顺序、举例

10.1 基础题目

• 509 斐波那契数、70 爬楼梯、746 使用最小花费爬楼梯、62 不同路径、63 不同路径II、343 整数拆分、96 不同的二叉搜索树

10.2 *背包问题

10.2.1 01背包

• 二维dp数组dp[i][j]表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是dp[i][j]。注意遍历顺序都可以（小到大）
• 使用一维滚动数组dp[j]优化，表示容量为j的背包，所背的物品价值可以最大为dp[j]。注意遍历顺序为先物品（i小到大）后背包（j大到小，防止物品放入多次）
• 题目
  • 416 分割等和子集、1049 最后一块石头的重量II、494 目标和、474 一和零

10.2.2 完全背包

• 使用一维滚动数组，注意遍历顺序都可以（小到大，物品可以放入多次），如果不是求组合或排列，一般先物品后背包，没那么容易弄混
• 如果求组合数，先物品后背包
• 如果求排列数，先背包后物品
• 题目
  • 518 零钱兑换II、377 组合总和IV、70 爬楼梯、322零钱兑换、279 完全平方数、139 单词拆分

10.3 打家劫舍

• 考虑偷和不偷的状态
• 题目
  • 198 打家劫舍、213 打家劫舍II、337 打家劫舍III

10.4 股票问题

• 考虑每天可能存在的状态
• 题目
  • 121 买卖股票的最佳时机（只能买卖一次）、122 买卖股票的最佳时机II（可以买卖多次）、123 买卖股票的最佳时机III（最多买卖两次）、188 买卖股票的最佳时机IV（最多买卖k次）、309 买卖股票的最佳时机含冷冻期（买卖多次，卖出有一天冷冻期）、714 买卖股票的最佳时机含手续费（买卖多次，每次有手续费）

10.5 子序列问题

• 题目

10.5.1 子序列（不连续）

• 300 最长上升子序列、1143 最长公共子序列、1035 不相交的线

10.5.2 子序列（连续）

• 674 最长连续递增序列、718 最长重复子数组、53 最大子序和

10.5.3 编辑距离

• 392 判断子序列、115 不同的子序列、583 两个字符串的删除操作、72 编辑距离

10.5.4 回文

• 647 回文子串、516 最长回文子序列

十一、单调栈

• 739 每日温度、496 下一个更大元素I、503 下一个更大元素II、42 接雨水、84 柱状图中最大的矩形