算法

alg 即 algorithm

基础: 算法入门

LeetCode 1. 两数之和 是一个非常经典的问题，也是算法学习的入门题目。这个问题可以通过暴力枚举、哈希表等多种方法解决，是一个很好的起点。

数组和穷举

• 掌握数组的基本操作（遍历、插入、删除）
• 学习穷举法解决问题

基础数据结构

• 目标: 理解常见数据结构的基本操作和应用场景
• 学习内容:
  1. 数组和链表:
  • 动态数组, 单链表, 双链表
  • 常见操作: 插入、删除、查找
  • 穷举法 (Brute Force)
  2. 栈和队列:
  • 栈 (Stack) (LIFO) 先进后出
  • 队列 (Queue) (FIFO) 先进先出
  • 双端队列 (Deque)
  3. 哈希表:
  • 哈希函数, 哈希冲突
  • dict, set
  4. 字符串:
  • 字符串基本操作
  • 字符串匹配问题
• 推荐题目:
  • LeetCode 1. 两数之和 (哈希表， 穷举)
  • LeetCode 21. 合并两个有序链表 (链表)
  • LeetCode 206. 反转链表 (链表)
  • LeetCode 217. 存在重复元素 (哈希表)
  • LeetCode 242. 有效的字母异位词 (哈希表, 计数)
  • LeetCode 215. 数组中的第K个最大元素 (堆)
  • LeetCode 20. 有效的括号 (栈)
  • LeetCode 232. 用栈实现队列 (栈, 队列)
  • LeetCode 155. 最小栈 (栈)
  • LeetCode 641. 设计循环双端队列 (双端队列)
  • LeetCode 344. 反转字符串 (字符串)

排序

• 目标: 掌握常见排序算法的思想和实现
• 学习内容:
  1. 冒泡排序, 选择排序, 插入排序 (O(n^2))
  2. 快速排序, 归并排序, 堆排序 (O(nlogn))
  3. 计数排序, 基数排序, 桶排序 (O(n))
• 推荐题目:
  • LeetCode 912. 排序数组 (排序)
  • LeetCode 56. 合并区间 (排序)
  • LeetCode 75. 颜色分类 (双指针, 排序思想)
  • LeetCode 179. 最大数 (排序)
  • LeetCode 215. 数组中的第K个最大元素 (排序)

进阶: 算法思想与应用

贪心算法

• 目标: 理解贪心算法的思想和应用场景
• 学习内容:
  1. 贪心算法基本思想
  2. 贪心选择性质和最优子结构
  3. 贪心算法的正确性证明
  4. 贪心算法的应用: 区间调度, 活动选择, 最优装载, 最小生成树(Kruskal 算法)
• 推荐题目:
  • LeetCode 406. 根据身高重建队列 (贪心, 插入排序思想)
  • LeetCode 435. 无重叠区间 (贪心, 区间调度)
  • LeetCode 452. 用最少数量的箭引爆气球 (贪心, 区间问题)
  • LeetCode 763. 划分字母区间 (贪心)
  • LeetCode 134. 加油站 (贪心)

二分查找

• 目标: 掌握二分查找的思想和变种
• 学习内容:
  1. 标准二分查找
  2. 二分查找的变种（如查找左边界、右边界）, 二分查找变形问题
  3. 二分查找的应用: 有序数组查找, 最优解的范围搜索, 查找边界, 旋转数组查找
• 推荐题目:
  • LeetCode 704. 二分查找 (基础二分查找)
  • LeetCode 69. x 的平方根 (二分查找)
  • LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置 (变种二分)
  • LeetCode 153. 寻找旋转排序数组中的最小值 (二分查找)
  • LeetCode 33. 搜索旋转排序数组 (二分查找)
  • LeetCode 4. 寻找两个正序数组的中位数 (二分查找)

前缀和与差分

• 目标: 掌握前缀和和差分的思想, 解决区间和问题
• 学习内容:
  1. 前缀和的构建与应用
  2. 差分数组的构建与应用
  3. 二维前缀和
• 推荐题目:
  • LeetCode 560. 和为 K 的子数组 (前缀和, 哈希)
  • LeetCode 238. 除自身以外数组的乘积 (前缀积)
  • LeetCode 724. 寻找数组的中心索引 (前缀和)
  • LeetCode 974. 和可被 K 整除的子数组 (前缀和)
  • LeetCode 525. 连续数组 (前缀和)
  • LeetCode 303. 区域和检索 - 数组不可变 (前缀和)
  • LeetCode 304. 二维区域和检索 - 矩阵不可变 (二维前缀和)

双指针与滑动窗口

• 目标: 掌握双指针和滑动窗口的思想, 解决区间和问题

• 学习内容:

  1. 双指针的基本思想
  2. 滑动窗口的扩展与收缩
  3. 双指针和滑动窗口的应用: 两数之和, 三数之和, 最长无重复子串, 最小覆盖子串

• 推荐题目:

  • LeetCode 3. 无重复字符的最长子串 (滑动窗口)
  • LeetCode 344. 反转字符串 (双指针)
  • LeetCode 167. 两数之和 II - 输入有序数组 (双指针)
  • LeetCode 15. 三数之和 (双指针)
  • LeetCode 11. 盛最多水的容器 (双指针)
  • LeetCode 76. 最小覆盖子串 (滑动窗口)
  • LeetCode 209. 长度最小的子数组 (滑动窗口)
  • LeetCode 438. 找到字符串中所有字母异位词 (滑动窗口)
  • LeetCode 567. 字符串的排列 (滑动窗口)
  • LeetCode 904. 水果成篮 (滑动窗口)

动态规划 (DP)

• 目标: 掌握动态规划的思想和常见问题
• 学习内容:
  1. 动态规划的基本思想
  2. 动态规划的状态定义和状态转移方程
  3. 一维 DP: 斐波那契数列, 背包问题, 最长递增子序列
  4. 二维 DP: 最长公共子序列, 编辑距离, 最大正方形
  5. 状态压缩 DP
• 推荐题目:
  • LeetCode 70. 爬楼梯 (基础 DP, 斐波那契数列)
  • LeetCode 322. 零钱兑换 (完全背包)
  • LeetCode 198. 打家劫舍 (背包问题)
  • LeetCode 300. 最长递增子序列 (最长递增子序列)
  • LeetCode 1143. 最长公共子序列 (二维 DP)
  • LeetCode 72. 编辑距离 (编辑距离)
  • LeetCode 221. 最大正方形 (最大正方形)
  • LeetCode 516. 最长回文子序列 (最长回文子序列)
  • LeetCode 647. 回文子串 (回文子串)
  • LeetCode 10. 正则表达式匹配 (正则表达式)
  • LeetCode 44. 通配符匹配 (通配符)
  • LeetCode 221. 最大正方形 (最大正方形)
  • LeetCode 85. 最大矩形 (最大矩形)
  • LeetCode 516. 最长回文子序列 (最长回文子序列)

高级: 复杂算法与优化

分治与递归

• 目标: 掌握分治和递归的思想
• 学习内容:
  1. 分治的基本思想
  2. 分治的应用: 归并排序, 快速排序, 汉诺塔
  3. 递归的实现与优化（如尾递归）
  4. 递归的应用: 斐波那契数列, 汉诺塔, 二叉树遍历
• 推荐题目:
  • LeetCode 53. 最大子序和 (分治)
  • LeetCode 169. 多数元素 (分治)
  • LeetCode 50. Pow(x, n) (分治)
  • LeetCode 241. 为运算表达式设计优先级 (分治)
  • LeetCode 95. 不同的二叉搜索树 II (递归)
  • LeetCode 98. 验证二叉搜索树 (递归)
  • LeetCode 104. 二叉树的最大深度 (递归)
  • LeetCode 236. 二叉树的最近公共祖先 (递归)
  • LeetCode 297. 二叉树的序列化与反序列化 (递归)
  • LeetCode 226. 翻转二叉树 (递归)
  • LeetCode 114. 二叉树展开为链表 (递归)
  • LeetCode 654. 最大二叉树 (递归)
  • LeetCode 105. 从前序与中序遍历序列构造二叉树 (递归)
  • LeetCode 106. 从中序与后序遍历序列构造二叉树 (递归)
  • LeetCode 889. 根据前序和后序遍历构造二叉树 (递归)

图论算法

• 目标: 掌握图的表示和常见算法
• 学习内容:
  1. 图的表示: 邻接矩阵, 邻接表
  2. 图的遍历: 深度优先搜索 (DFS), 广度优先搜索 (BFS)
  3. 最短路径: Dijkstra 算法, Floyd 算法
  4. 最小生成树: Prim 算法, Kruskal 算法
  5. 拓扑排序: Kahn 算法, DFS 算法
• 推荐题目:
  • LeetCode 130. 被围绕的区域 (DFS)
  • LeetCode 127. 单词接龙 (BFS)
  • LeetCode 133. 克隆图 (图的遍历)
  • LeetCode 207. 课程表 (拓扑排序)
  • LeetCode 210. 课程表 II (拓扑排序)
  • LeetCode 399. 除法求值 (DFS)
  • LeetCode 785. 判断二分图 (图的染色, DFS)
  • LeetCode 743. 网络延迟时间 (最短路径, Dijkstra)
  • LeetCode 787. K 站中转内最便宜的航班 (Dijkstra)

高级数据结构

• 目标: 掌握高级数据结构的思想和应用
• 学习内容:
  1. 并查集 (Union Find)
  2. 堆 (Heap)
  3. 线段树 (Segment Tree)
  4. 树状数组 (Fenwick Tree)
  5. 字典树 (Trie)
• 推荐题目:
  • LeetCode 200. 岛屿数量 (并查集)
  • LeetCode 305. 岛屿数量 II (并查集)
  • LeetCode 307. 区域和检索 - 数组可修改 (树状数组\线段树)
  • LeetCode 399. 除法求值 (并查集)
  • LeetCode 547. 省份数量 (并查集)