前言
算法和数据结构
数据结构
存储⽅式
两种基本的存储：顺序存储和链式存储
| 顺序存储 | 链式存储 | |
|---|---|---|
| 基础结构 | 数组 | 链表 |
| 连续性 | 一次分配一块连续的内存空间 | 元素间不连续，通过指针指向下一个元素 |
| 扩容策略 | 重新分配⼀块更⼤的空间，再把旧空间数据全部复制过去，回收旧空间，时间复杂度O(N) | 通过指针指向⼀个元素的位置，不需要扩容 |
| 查找元素 | 随机访问；根据索引定位数据位置进行快速访问 | 不能随机访问；无法根据索引定位数据，通过指针的前驱或后驱定位数据 |
| 插入或删除元素 | 搬移数据以保持连续，时间复杂度 O(N) | 已知某⼀元素的前驱和后驱，操作指针即可删除该元素或者插⼊新元素，时间复杂度 O(1) |
常见的数据结构：散列表、栈、队列、堆、树、图
树: 二叉树、⼆叉搜索树、AVL 树、红⿊树、区间树、B 树
基本操作
增删改查
遍历数据: 迭代线性数据结构 ，递归非线性数据结构
基础
数组前缀和
适用: 原始数组不会被修改的情况下，快速、频繁地计算⼀个索引区间内的元素之和
| 题目 | 链接 | |
|---|---|---|
| LeetCode 303 | 区域和检索 - 数组不可变（中等） | 链接 |
| LeetCode 304 | ⼆维区域和检索 - 矩阵不可变（中等) | 链接 |
| LeetCode 560 | 和为K的⼦数组（中等） | 链接 |
差分数组
频繁对原始数组的某个区间的元素进⾏增减。
| 题目 | 链接 |
|---|---|
| Leetcode 370. 区间加法（中等） | 链接 |
| Leetcode 1109. 航班预订统计（中等） | 链接 |
| Leetcode 1094. 拼⻋（中等） | 链接 |
原地修改数组
在原地修改数组，避免数据的搬移
| 题目 | 题目 |
|---|---|
| 26.删除有序数组中的重复项（简单） | |
| 83.删除排序链表中的重复元素（简单） ） | |
| 27.移除元素（简单 | |
| 283.移动零（简单） |
双指针
双指针技巧 分为两类，一类是「快慢指针」，一类是「左右指针」。
快慢指针主要解决链表中的问题，比如典型的判定链表中是否包含环，快慢指针一般都初始化指向链表的头结点head，前进时快指针fast在前，慢指针slow在后，巧妙解决一些链表中的问题。
左右指针主要解决数组（或者字符串）中的问题，比如二分查找，在数组中实际是指两个索引值，一般初始化为left = 0, right = nums.length - 1。
滑动窗口技巧 主要适用于解决⼦串、⼦数组问题。
二分搜索 && 二分查找 :在有序的前提下进行搜索，常⽤的⼆分查找场景：寻找⼀个数、寻找左侧边界、寻找右侧边界
快慢指针
| Leetcode | 题目 |
|---|---|
| Leetcode 141 | 链表中是否含有环 |
| 已知链表中含有环，返回这个环的起始位置 | |
| Leetcode 876 | 寻找链表的中点 |
| Leetcode 19 | 寻找链表的倒数第n个元素 |
左右指针
| Leetcode | 题目 |
|---|---|
| Leetcode 167 | 两数之和II |
| Leetcode 344 | 反转数组 |
滑动窗口
| Leetcode | 题目 |
|---|---|
| Leetcode 76 | 最⼩覆盖⼦串（困难） |
| Leetcode 567 | 字符串的排列（中等） |
| Leetcode 438 | 找到字符串中所有字⺟异位词（中等） |
| Leetcode 3 | ⽆重复字符的最⻓⼦串（中等） |
| Leetcode 239 | 滑动窗⼝最⼤值 |
二分搜索
| Leetcode | 题目 |
|---|---|
| Leetcode 704 | ⼆分查找（简单） |
| Leetcode 34 | 在排序数组中查找元素的第⼀个和最后⼀个位置（中等） |
| Leetcode 875 | 爱吃⾹蕉的珂珂（中等） |
| Leetcode 1011 | 在D天内送达包裹的能⼒（中等） |
| Leetcode 793 | 阶乘函数后 K 个零 |
| Leetcode 392 | 判断⼦序列 |
| Leetcode 354 | 俄罗斯套娃信封问题 |
双指针-其他
| Leetcode | 题目 |
|---|---|
| Leetcode 26 | 删除有序数组中的重复项 |
| Leetcode 27 | 移除元素 |
| Leetcode 283 | 移动零 |
| Leetcode 42 | 接⾬⽔ |
| Leetcode 986 | 区间列表的交集 |
| Leetcode 870 | 优势洗牌 |
| Leetcode 15 | 三数之和 |
| Leetcode 18 | 四数之和 |
链表
| Leetcode | 题目 |
|---|---|
| 19.删除链表的倒数第 N 个结点 | |
| 21. 合并两个有序链表 | |
| 23. 合并K 个升序链表 | |
| 141. 环形链表 | |
| 142. 环形链表 II | |
| 160. 相交链表 | |
| 876. 链表的中间结点 | |
| 25. K 个⼀组翻转链表 | |
| 83. 删除排序链表中的重复元素 | |
| 92. 反转链表 II 链表操作:迭代 and 递归对比 | |
| 234. 回⽂链表 |
队列&&栈
互实现
| Leetcode | 题目 |
|---|---|
| 225. ⽤队列实现栈 | |
| 232. ⽤栈实现队列 |
括号题⽬
| Leetcode | 题目 |
|---|---|
| 20.有效的括号 | |
| 921. 使括号有效的最少添加 | |
| 1541. 平衡括号字符串的最少插⼊次数 |
单调栈
| Leetcode | 题目 |
|---|---|
| 496.下⼀个更⼤元素I（简单） | |
| 503.下⼀个更⼤元素II（中等） | |
| 739.每⽇温度（中等） |
单调队列结构
| Leetcode | 题目 |
|---|---|
| 22. 括号⽣成 | |
| 239. 滑动窗⼝最⼤值 |
数组去重
| Leetcode | 题目 |
|---|---|
| 316.去除重复字⺟（中等） | |
| 1081.不同字符的最⼩⼦序列（中等） |
基础设计
| Leetcode | 题目 |
|---|---|
| 146.LRU 缓存机制 | LRU 缓存机制 |
| 460. LFU 缓存 | |
| 380.常数时间插⼊、删除和获取随机元素（中等） | |
| 710.⿊名单中的随机数（困难） | |
| 295.数据流的中位数（困难） |
二叉树
递归遍历
1 | void traverse(TreeNode root) { |
技巧总结:
递归算法的关键要明确函数的定义，相信这个定义，⽽不要跳进递归细节。
⼆叉树的算法题，基于递归框架的，先要搞清楚root节点要做什么，然后根据题⽬要求选择使⽤前序，中序，后续的递归框架。
难点在于如何通过题⽬的要求思考出每⼀个节点需要做什么，只能通过多刷题进⾏练习
| Leetcode | 题目 |
|---|---|
| 226.翻转⼆叉树（简单） | |
| 114.⼆叉树展开为链表（中等） | |
| 116.填充每个节点的下⼀个右侧节点指针（中等） |
| Leetcode | 题目 |
|---|---|
| 654.最⼤⼆叉树（中等） | |
| 105.从前序与中序遍历序列构造⼆叉树（中等） | |
| 106.从中序与后序遍历序列构造⼆叉树（中等） |
| Leetcode | 题目 |
|---|---|
| 652.寻找重复的⼦树（中等） | |
| 297.⼆叉树的序列化和反序列化（困难） | |
| 1373.⼆叉搜索⼦树的最⼤键值和（困难） |
二叉搜索树
BST(Binary Search Tree)是⼀种特殊的⼆叉树，两个主要特点:
左⼩右⼤，即每个节点的左⼦树都⽐当前节点的值⼩，右⼦树都⽐当前节点的值⼤
中序遍历结果是有序的
| 题目 | |
|---|---|
| 230 | BST第K⼩的元素（中等） |
| 538 | ⼆叉搜索树转化累加树（中等） |
| 1038 | BST转累加树（中等） |
| 题目 | |
|---|---|
| 450.删除⼆叉搜索树中的节点（中等） | |
| 701.⼆叉搜索树中的插⼊操作（中等） | |
| 700.⼆叉搜索树中的搜索（简单） | |
| 98.验证⼆叉搜索树（中等） |
| 题目 | |
|---|---|
| 96.不同的⼆叉搜索树（Easy） | |
| 95.不同的⼆叉搜索树II（Medium） |
图论
图论之基础
| Leetcode | 题目 |
|---|---|
| 797.所有可能的路径（中等） | |
图论之⼆分图
| Leetcode | 题目 |
|---|---|
| 785. 判断⼆分图（中等） | |
| 886. 可能的⼆分法（中等） |
图论之Union-Find算法
| Leetcode | 题目 |
|---|---|
| 323.⽆向图中的连通分量数⽬（中等） | |
| 130.被围绕的区域（中等） | |
| 990.等式⽅程的可满⾜性 |
图论之Kruskal算法
| Leetcode | 题目 |
|---|---|
| 261. 以图判树（中等） | |
| 1135. 最低成本联通所有城市（中等） | |
| 1584. 连接所有点的最⼩费⽤（中等） |
图论之Dijkstra算法
| Leetcode | 题目 |
|---|---|
| 743. ⽹络延迟时间（中等） | |
| 1514. 概率最⼤的路径（中等） | |
| 1631. 最⼩体⼒消耗路径（中等） |
图论之其他
| Leetcode | 题目 |
|---|---|
| 277.搜索名⼈（中等） |
DFS算法/回溯算法
基础
| Leetcode | 题目 |
|---|---|
| 46.全排列（中等） | |
| 51.N皇后（困难） |
集合划分
| Leetcode | 题目 |
|---|---|
| 698.划分为k个相等的⼦集（中等） |
子集、排列、组合
| Leetcode | 题目 |
|---|---|
| 78.⼦集（中等） | |
| 46.全排列（中等） | |
| 77.组合（中等） |
岛屿类型
| Leetcode | 题目 |
|---|---|
| 200.岛屿数量（中等） | |
| 1254.统计封闭岛屿的数⽬（中等） | |
| 1020.⻜地的数量（中等） | |
| 695.岛屿的最⼤⾯积（中等） | |
| 1905.统计⼦岛屿（中等） | |
| 694.不同的岛屿数量（中等） |
BFS算法
基础
| Leetcode | 题目 |
|---|---|
| 111.⼆叉树的最⼩深度（简单） | |
| 752.打开转盘锁（中等） |
其他
| Leetcode | 题目 |
|---|---|
| 773.滑动谜题（困难） |
动态规划
基础
| 核心 | Leetcode题目 |
|---|---|
| 核⼼原理 | 509.斐波那契数（简单） 322.零钱兑换（中等） |
| base case 和备忘录的初始值怎么定？ | 931.下降路径最⼩和（中等） |
| 最优⼦结构和 dp 数组的遍历⽅向怎么定？ | 到底什么才叫「最优⼦结构」，和动态规划什么关系。 为什么动态规划遍历 dp 数组的⽅式五花⼋⻔，有的正着遍历，有的倒着遍历，有的斜着遍历。 |
经典
| Leetcode | 题目 |
|---|---|
| 300.最⻓递增⼦序列（中等） | |
| 53.最⼤⼦序和（简单） | |
| 1143.最⻓公共⼦序列（中等） | |
| 583. 两个字符串的删除操作（中等） | |
| 712.两个字符串的最⼩ASCII删除和（中等） | |
| 72.编辑距离（困难） | |
| 10.正则表达式匹配（困难） |
背包
| 类型 | Leetcode题目 |
|---|---|
| 0-1 背包问题 | |
| 完全背包问题 | 518.零钱兑换II（中等） |
| ⼦集背包问题 | 416.分割等和⼦集（中等） |
| Leetcode | 题目 |
|---|---|
| 121.买卖股票的最佳时机（简单） | |
| 122.买卖股票的最佳时机 II（简单） | |
| 123.买卖股票的最佳时机 III（困难） | |
| 188.买卖股票的最佳时机 IV（困难） | |
| 309.最佳买卖股票时机含冷冻期（中等） | |
| 714.买卖股票的最佳时机含⼿续费（中等） |
| Leetcode | 题目 |
|---|---|
| 198.打家劫舍（简单） | |
| 213.打家劫舍II（中等） | |
| 337.打家劫舍III（中等） |
| Leetcode | 题目 |
|---|---|
| 877.⽯⼦游戏（中等） | |
| 64.最⼩路径和（中等） | |
| 887.鸡蛋掉落（困难） | |
| 174.地下城游戏（困难） | |
| 514.⾃由之路（困难） | |
| 787. K 站中转内最便宜的航班（中等） |
数学算法
数学算法⼤多就是位运 算、找规律、概率算法、素数之类
| 类型 | Leetcode题目 |
|---|---|
| 如何⾼效寻找素数 | 204.计数质数（简单） |
| 两道常考的阶乘算法题 | 172.阶乘后的零（简单） 793.阶乘后 K 个零（困难） |
| 如何在⽆限序列中随机抽取元素 | 382.链表随机节点（中等） 398.随机数索引（中等） |
| 吃葡萄 | 吃葡萄-牛客网 |
| 如何同时寻找缺失和重复的元素 | 645.错误的集合（简单） |
其他
| 类型 | Leetcode题目 |
|---|---|
| ⼀个⽅法团灭 nSum问题 | 15.三数之和（中等） 18.四数之和（中等） |
| ⼀个⽅法解决三道区间问题 | 1288.删除被覆盖区间（中等） 56.区间合并（中等） 986.区间列表的交集（中等） |
| 快速选择算法 | 215.数组中的第 K 个最⼤元素（中等） |
| 分治算法详解：运算优先级 | 241.为运算表达式设计优先级（中等） |
| 扫描线技巧：安排会议室 | 253.会议室 II（中等） |
| 贪⼼算法 | 134.加油站（中等） 1024.视频拼接（中等） |
| 如何实现⼀个计算器 | 224.基本计算器（困难） 227.基本计算器II（中等） 772.基本计算器III（困难） |
| ⽃地主 | 659. 分割数组为连续⼦序列（中等） |
| 判定完美矩形 | 391.完美矩形（困难） |