LeetCode 题目总结

本博客不定期更新 LeetCode 题目总结，所有题目使用 Java 实现，小部分题目也提供 JavaScript 代码。我不追求一行 AC 但是我追求一题多解，比较常规的思路，解释清楚复杂度，代码可读性强。欢迎留言和评论，共同进步。这本是我自己用来复习的笔记，如果也能帮到你，那也是我的福报。

如果你想按类型刷题，可以参考我的标签。我做出的分类比 LC 官方的更细一些，比如我有如下展示的这些类型，其中有一些类型在 2021 年 6 月以前官方没有收录，有的按照题设分类，有的按照思路/解法分类。同时有一些题目的解法或者思想很类似的，我也会以相关题目的形式列在文章的最底部。对于每一种类型的题，你可以基本按照题号从小到大开始刷，比较小的题号（尤其前 400）都是经典题，一般直接问算法，比较大的题号往往是前 400 题中某个题目的 followup 或变形，如果你看懂题目要考什么，其实涉及的算法在前 400 题应该都有涉及。题是刷不完的，只有总结反思才会有提高。

• flood fill 岛屿类 - 往往是通过 BFS/DFS 从一个点开始遍历整个二维数组，根据题意找岛的个数/面积或者找一个点与点之间的距离，一个走到某个坐标上的步数/时间
• matrix 矩阵类，跟岛屿类型的题很接近，但是主要考点是二维数组的非常规遍历，翻转。官方把岛屿类的题也归类到 matrix 一类了，我这里做了一些区分
• monotonic stack 单调栈 - 不容易想到但是的确能解决问题的一种思路，如果不用单调栈，暴力解基本是 O(n^2) 级别的
• two pointer 双指针，包括很多可以用双指针做但是没有标注成双指针类型的题
• prefix sum 前缀和
• sliding window 滑动窗口
• sliding window with fixed size 固定尺寸的滑动窗口
• palindrome 回文 - 也是双指针的一个子类，两边往中间逼近
• line sweep 扫描线/差分数组 - 这一类的题其实也分为两个子类，一类是类似会议室那种，一类是合并子区间那种
• counting sort 计数排序
• bucket sort 桶排序
• Longest Increasing Subsequence (LIS) 最长递增子序列
  • 这个类型的题往往跟 DP 有关
• Longest Common Subsequence (LCS) 最长相同子序列，经典题有
  • Edit Distance
  • Longest Common Subsequence
• two sum 两数之和 - 一些算是 two sum 的 followup 题
• MOD - 结果非常大，需要取模的题。如果需要优化，大多涉及到二分
• binary search 二分法
  • 我总结的三个二分法模板及其区别
• binary search on answer 在答案上二分
  • 也是二分的一类题，一般不是直接在 input 数组上做二分
• Dijkstra 迪杰斯特拉算法
  • 使用类似广度优先搜索的方法解决图的单源最短路径问题，一般会涉及有向和有权的图
• graph 图论 - 包括很多 input signature 给的是树但是实际是需要自己把图或邻接表建立起来的题，和官方压根没有给出 graph 这个 tag 的题（比如1192题，2021年6月这个题官方加了tag了）
• union find - 并查集 - 解决一些 BFS 做会复杂度高或 DFS 做会 stack overflow 的图论的题，比如如果数据是以数据流的形式给出的，BFS 的复杂度就会很高。并查集有时候在 union 的过程中就能找到答案。
• knapsack 背包问题 - 动态规划中的一个子类
• memorization - 记忆化（递归）- 动态规划中的一个子类
• simulation - 模拟，一般不涉及算法，就是根据题意实现
• gcd 最大公约数

我做了一个 腾讯文档 记录总结写过题解的题目并附上链接。