Skip to content

LeetCode高频题目,包含学习整理的文章和刷题模板,参考宫水三叶博主、《算法(第四版)》、《算法导论》和《Hello 算法》等技术书籍

License

Notifications You must be signed in to change notification settings

FangYuan33/LeetCode

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 
 
 
 
 
 
 
 
 

Repository files navigation

大家好,我是 方圆。最近仓库 Star 星数增长蛮快的,实在感谢大家。这个仓库是我在算法学习路上总结的经验性知识,目前来说我认为其中缺憾的地方是动态规划和图没有专题文章,如果后续有时间,我会尽快整理出来。算法学习在我看来是一件需要占用大块时间去做的事情,对于我现在的工作状态来说,比较难拿出十天半个月来做这件事情了,所以也希望大家能够提 Pull Request 共同建设。

我重新将题目的顺序整理了一下,我认为比较合适的顺序是:双指针、滑动窗口和二分查找,接下来是数据结构链表、栈、队列、散列表等等,换个脑子学习一下排序算法,接下来就是树、图数据结构,再就是回溯、动态规划等等,最后是树状数组和线段树,我觉得这两部分内容作为扩展学习更合适。另外我也整理了 掘金 和 CSDN 的专栏,大家按照喜好看自己喜欢的网站吧,方便的话,可以在掘金上帮忙点个关注(我总觉得 CSDN 是一个没有人在运营的博客网站...),希望大家算法学习的开心~

双指针

数组

题目链接 题解 备注
26. 删除有序数组中的重复项 简单 Solution26.java
392. 判断子序列 简单 Solution392.java
27. 移除元素 简单 Solution27.java
LCR 139. 训练计划 I 简单 SolutionLCR139.java
面试题 10.01. 合并排序的数组 简单 Interview1001.java
88. 合并两个有序数组 简单 Solution88.java
581. 最短无序连续子数组 中等 Solution581.java
80. 删除有序数组中的重复项 II 中等 Solution80.java
11. 盛最多水的容器 中等 Solution11.java
881. 救生艇 中等 Solution881.java
870. 优势洗牌 中等 Solution870.java
658. 找到 K 个最接近的元素 中等 Solution658.java
825. 适龄的朋友 中等 Solution825.java
56. 合并区间 中等 Solution56.java
413. 等差数列划分 中等 Solution413.java
167. 两数之和 II - 输入有序数组 中等 Solution167.java
15. 三数之和 中等 Solution15.java
16. 最接近的三数之和 中等 Solution16.java
18. 四数之和 中等 Solution18.java
134. 加油站 中等 Solution134.java

字符串

题目链接 题解 备注
125. 验证回文串 简单 Solution125.java ✅Character.isLetterOrDigit() 静态方法判断是字母和数字
面试题 17.11. 单词距离 中等 Interview1711.java
809. 情感丰富的文字 中等 Solution809.java
443. 压缩字符串 中等 Solution443.java
481. 神奇字符串 中等 Solution481.java
524. 通过删除字母匹配到字典里最长单词 中等 Solution524.java
777. 在LR字符串中交换相邻字符 中等 Solution777.java
838. 推多米诺 中等 Solution838.java
面试题 01.05. 一次编辑 中等 Interview0105.java

滑动窗口

固定窗口

题目链接 题解 备注
643. 子数组最大平均数 I 简单 Solution643.java
1423. 可获得的最大点数 中等 Solution1423.java
1984. 学生分数的最小差值 简单 Solution1984.java
438. 找到字符串中所有字母异位词 中等 Solution438.java
567. 字符串的排列 中等 Solution567.java
1052. 爱生气的书店老板 中等 Solution1052.java

动态窗口

题目链接 题解 备注
剑指 Offer 57 - II. 和为s的连续正数序列 简单 SolutionOffer57.java
1446. 连续字符 简单 Solution1446.java
LCR 008. 长度最小的子数组 中等 SolutionLCR008.java
76. 最小覆盖子串 困难 Solution76.java
713. 乘积小于 K 的子数组 中等 Solution713.java 固定右端点的子数组数量为以该右端点结尾的数组长度
992. K 个不同整数的子数组 困难 Solution992.java ⭐️
3. 无重复字符的最长子串 中等 Solution3.java
1759. 统计同质子字符串的数目 中等 Solution1759.java
1695. 删除子数组的最大得分 中等 Solution1695.java
1004. 最大连续1的个数 III 中等 Solution1004.java
1208. 尽可能使字符串相等 中等 Solution1208.java
904. 水果成篮 中等 Solution904.java
424. 替换后的最长重复字符 中等 Solution424.java
2024. 考试的最大困扰度 中等 Solution2024.java
2302. 统计得分小于 K 的子数组数目 困难 Solution2302.java

二分查找

数组有序

题目链接 题解 备注
704. 二分查找 简单 Solution704.java
35. 搜索插入位置 简单 Solution35.java
744. 寻找比目标字母大的最小字母 简单 Solution744.java
367. 有效的完全平方数 简单 Solution367.java
278. 第一个错误的版本 简单
34. 在排序数组中查找元素的第一个和最后一个位置 中等 Solution34.java
74. 搜索二维矩阵 中等 Solution74.java
240. 搜索二维矩阵 II 中等 Solution240.java
268. 丢失的数字 简单 Solution268.java
剑指 Offer 53 - II. 0~n-1中缺失的数字 简单 SolutionOffer532.java 二分查找两段性的典型应用
436. 寻找右区间 中等 Solution436.java
532. 数组中的 k-diff 数对 中等 Solution532.java
911. 在线选举 中等 TopVotedCandidate.java ⭐️
1608. 特殊数组的特征值 简单 Solution1608.java
1818. 绝对差值和 中等 Solution1818.java
33. 搜索旋转排序数组 中等 Solution33.java
153. 寻找旋转排序数组中的最小值 中等 Solution153.java
81. 搜索旋转排序数组 II 中等 Solution81.java
154. 寻找旋转排序数组中的最小值 II 困难 Solution154.java
1005. K 次取反后最大化的数组和 简单 Solution1005.java left指针表示小于被查找值的数量的应用

数组无序

查找峰值是非常典型的根据数据二段性进行二分的题目

题目链接 题解 备注
162. 寻找峰值 中等 Solution162.java ⭐️
852. 山脉数组的峰顶索引 中等 Solution852.java

贪心算法

题目链接 题解 备注
1760. 袋子里最少数目的球 中等 Solution1760.java
875. 爱吃香蕉的珂珂 中等 Solution875.java
2226. 每个小孩最多能分到多少糖果 中等 Solution2226.java
1011. 在 D 天内送达包裹的能力 中等 Solution1011.java
410. 分割数组的最大值 困难 Solution410.java
1552. 两球之间的磁力 中等 Solution1552.java
475. 供暖器 中等 Solution475.java
1802. 有界数组中指定下标处的最大值 中等 Solution1802.java 等差数列求和公式:(首项 + 尾项)* 项数 / 2
719. 找出第 K 小的数对距离 困难 Solution719.java
668. 乘法表中第k小的数 困难 Solution668.java

前缀和

前缀和表示数组的前 n 项和,它是一种数据预处理的方法,是对空间换时间的应用,我们一般会创建 数组长度 + 1 大小的数组来记录前缀和,并将 0 索引处的前缀和标记为 0,表示前 0 项和,如下图所示,索引 1 处的前缀和表示原数组中的前 1 项和(nums[0]),所以我们想获取原数组中某索引元素的前缀和的话,需要将索引值加 1 再从前缀和数组中取值。

前缀和.drawio.png

一般 连续子数组 求和且不涉及区间修改的问题都可以使用前缀和来求解,通过 前缀和减法计算 我们能计算出任意区间和,这一点很重要,利用这一点可以解决很多区间求和的问题。

  • 一维数组前缀和计算模板如下:
    int[] preSum = new int[nums.length + 1];
    for (int i = 1; i < preSum.length; i++) {
        preSum[i] = preSum[i - 1] + nums[i - 1];
    }

一维数组前缀和

题目链接 题解 备注
1894. 找到需要补充粉笔的学生编号 中等 Solution1894.java
1744. 你能在你最喜欢的那天吃到你最喜欢的糖果吗? 中等 Solution1744.java
497. 非重叠矩形中的随机点 中等 Solution497.java
528. 按权重随机选择 中等 Solution528.java
238. 除自身以外数组的乘积 中等 Solution238.java
274. H 指数 中等 Solution274.java

前缀和减法计算任意区间和

我们能通过前缀和减法计算任意区间和,即 preSum[k, i] = preSum[0, i] - preSum[0, k - 1],其中 k <= i

题目链接 题解 备注
303. 区域和检索 - 数组不可变 简单 NumArray.java
724. 寻找数组的中心下标 简单 Solution724.java
1588. 所有奇数长度子数组的和 简单 Solution1588.java
1652. 拆炸弹 简单 Solution1652.java
1310. 子数组异或查询 中等 Solution1310.java
525. 连续数组 中等 Solution525.java 本题技巧性比较强,思路是将 0 看成 -1,并找到相等的前缀和后计算最长的数组长度,本质上是前缀和减法
560. 和为 K 的子数组 中等 Solution560.java ⭐️
396. 旋转函数 中等 Solution396.java
523. 连续的子数组和 中等 Solution523.java
926. 将字符串翻转到单调递增 中等 Solution926.java
2055. 蜡烛之间的盘子 中等 Solution2055.java

二维数组前缀和

我觉得 304 题是二维数组前缀和的代表性题目,熟悉它的解题思路之后,大概几分钟就能解出来。我们以计算 matrix[i][j] 处的前缀和为例,其中二维数组中每个元素表示以 [0, 0] 为左上角,以当前元素 [i, j] 为右下角构成的矩阵的前缀和,在计算 matrix[i][j] 之前,我们先来看一下官方题解给出示例图,我觉得记住这张图能的推导出计算公式:

计算 matrix[i][j] 我们能够依靠已知的前缀和 matrix[i - 1][j - 1]matrix[i - 1][j]matrix[i][j - 1],其实我们可以轻易的根据图示得出 matrix[i][j] = matrix[i - 1][j] + matrix[i][j - 1] - matrix[i - 1][j - 1],为什么要减去 matrix[i - 1][j - 1] 呢,因为在 matrix[i - 1][j]matrix[i][j - 1] 中都包含着 matrix[i - 1][j - 1],我们做加和计算时把 matrix[i - 1][j - 1] 加了两遍,所以需要再减去一个,记住这个图示之后遇到类似的题推导一下就可以了,不必记住模板。

计算二维数组前缀和的要点一定是确定好 矩形的对角(左上角和右下角 或 左下角和右上角)

题目链接 题解 备注
304. 二维区域和检索 - 矩阵不可变 中等 NumMatrix.java
661. 图片平滑器 简单 Solution661.java

差分

字符串

题目链接 题解 备注
14. 最长公共前缀 简单 Solution14.java
1455. 检查单词是否为句中其他单词的前缀 简单 Solution1455.java startsWith() 方法
187. 重复的DNA序列 中等 Solution187.java
面试题 10.02. 变位词组 中等 Interview1002.java
394. 字符串解码 中等 Solution394.java
151. 反转字符串中的单词 中等 Solution151.java
165. 比较版本号 中等 Solution165.java Integer.parseInt() 字符串转整数自动忽略前导0
8. 字符串转换整数 (atoi) 中等 Solution8.java ⭐️数字边界问题处理
43. 字符串相乘 中等 Solution43.java
6. Z 字形变换 中等 Solution6.java

链表

链表是一种 递归 的数据结构,与数组不同的是它不需要占用连续的内存空间,但是需要额外的空间保存后继节点的指针,以此将所有的链表节点串联起来。它的删除和插入操作比较高效,时间复杂度为 $O(1)$,但是想访问链表中某个值时,需要对链表进行遍历,时间复杂度为 $O(n)$链表是数组的一种重要的替代方式

链表反转

    public ListNode reverseList(ListNode head) {
        ListNode pre = null;

        while (head != null) {
            ListNode temp = head.next;
            head.next = pre;
            pre = head;
            head = temp;
        }

        return pre;
    }
题目链接 题解 备注
206. 反转链表 简单 Solution206.java
234. 回文链表 简单 Solution234.java 快慢指针分开链表
92. 反转链表 II 中等 Solution92.java
25. K 个一组翻转链表 困难 Solution25.java

递归

题目链接 题解 备注
剑指 Offer 06. 从尾到头打印链表 简单 SolutionOffer06.java
剑指 Offer 35. 复杂链表的复制 中等 SolutionOffer35.java
24. 两两交换链表中的节点 中等 Solution24.java
剑指 Offer 25. 合并两个排序的链表 简单 SolutionOffer25.java
23. 合并K个升序链表 困难 Solution23.java 分治的思想(想想归并排序)
148. 排序链表 中等 Solution148.java 也是分治的思想,但是它的难度是中等,其实和上一题差不多
430. 扁平化多级双向链表 中等 Solution430.java
138. 随机链表的复制 中等 Solution138.java

双指针、快慢指针

题目链接 题解 备注
剑指 Offer 22. 链表中倒数第k个节点 简单 SolutionOffer22.java
876. 链表的中间结点 简单 Solution876.java
141. 环形链表 简单 Solution141.java
142. 环形链表 II 中等 Solution142.java
287. 寻找重复数 中等 Solution287.java ⭐️ 1. 如果提示 n + 1 个数,且数字范围在 [1, n] 内,那么可以使索引和该位置的值一致,来协助解题
2. 该题由于不能修改数组,所以转换成了环形链表求解
160. 相交链表 简单 Solution160.java
1823. 找出游戏的获胜者 中等 Solution1823.java

前驱节点在删除链表节点中的应用

题目链接 题解 备注
剑指 Offer 18. 删除链表的节点 简单 SolutionOffer18.java
83. 删除排序链表中的重复元素 简单 Solution83.java
82. 删除排序链表中的重复元素 II 中等 Solution82.java
19. 删除链表的倒数第 N 个结点 中等 Solution19.java
725. 分隔链表 中等 Solution725.java
237. 删除链表中的节点 中等 Solution237.java

推导

题目链接 题解 备注
328. 奇偶链表 中等 Solution328.java
382. 链表随机节点 中等 Solution382.java
剑指 Offer II 029. 排序的循环链表 中等 SolutionOfferTwo29.java
面试题 02.05. 链表求和 中等 Solution0205.java
445. 两数相加 II 中等 Solution445.java
817. 链表组件 中等 Solution817.java
86. 分隔链表 中等 Solution86.java

数据结构

题目链接 题解 备注
146. LRU 缓存 中等 LRUCache.java
LRUCacheLinkedHashMap.java
从 LinkedHashMap 源码到手撕 LRU 缓存
460. LFU 缓存 困难 LFUCache.java 手撕 LFU 缓存
432. 全 O(1) 的数据结构 困难 AllOne.java
707. 设计链表 中等 MyLinkedList.java
641. 设计循环双端队列 中等 MyCircularDeque.java
208. 实现 Trie (前缀树) 中等 Trie.java
1206. 设计跳表 困难

栈是一种基于 后进先出(LIFO)策略 的集合类型,这就需要我们在对值进行处理时注意结果值有没有对顺序的要求,因为入栈到出栈是倒序的。

  • 应用: 函数调用栈、括号的匹配、双栈实现浏览器的前进和后退功能、JVM栈、电子邮件的存放、算数表达式的求值(操作数栈和运算符栈)
题目链接 题解 备注
20. 有效的括号 简单 Solution20.java
232. 用栈实现队列 简单 MyQueue.java
155. 最小栈 中等 MinStack.java
946. 验证栈序列 中等 Solution946.java
71. 简化路径 中等 Solution71.java
1190. 反转每对括号间的子串 中等 Solution1190.java
385. 迷你语法分析器 中等 【宫水三叶】栈运用模拟题
636. 函数的独占时间 中等 Solution636.java
735. 行星碰撞 中等 Solution735.java
856. 括号的分数 中等 Solution856.java
1106. 解析布尔表达式 困难 Solution1106.java
32. 最长有效括号 困难 Solution32.java
726. 原子的数量 困难 Solution726.java

单调栈

单调栈本质上是 维护数组中的元素为单调序列,数组中的元素 要么 符合单调性顺利进栈,要么 不符合单调性而将栈中其他元素“挤走”再进栈,使得栈中序列始终满足单调性。

理解这一点很重要,我们以单调递增栈为例,如果出现了比栈顶元素 的值,即不符合当前栈中序列单增特性的值,那么它会使所有比它大的值出栈,而 该值便是接下来要连续出栈元素右侧最近的小值,比该值大的值出栈完毕后,该值进栈,使得栈中的序列仍然满足单调递增。

如果题目有 在连续序列中找元素左/右侧最近的大/小值 的特点,我们就可以使用单调栈来求解,找最近的小值的单调递增栈模板如下,注意入栈的是数组元素的索引而不是元素值:

Stack<Integer> stack = new Stack<>();

for (int i = 0; i < nums.length; i++) {
    while (!stack.isEmpty() && nums[i] < nums[stack.peek()]) {
        int index = stack.pop();

        // 关于 index 的特殊处理
        process();
    }
    // 索引入栈
    stack.push(i);

    // 处理逻辑
    process1();
}

这个模板其实很好记,根据想找小值还是找大值来确定模板中的 while 条件,如果找小值则使用小于号,则 nums[i] < nums[stack.peek()],如果找大值则使用大于号,则 nums[i] > nums[stack.peek()],再根据题意判断是否需要给大于小于号添加上等号,这一点考虑是在有重复值出现的情况下。

说了这么多,其实只需要考虑想找的是最近的小值还是大值,写对应的模板解题即可,即使你没明白为什么单调栈能找元素最近的大/小值(应该自己 Debug 学习一下)也没关系,只要使用了单调栈它就有这个性质,其他的全是虚妄......

题目链接 题解 备注
1475. 商品折扣后的最终价格 简单 Solution1475.java
739. 每日温度 中等 Solution739.java
901. 股票价格跨度 中等 StockSpanner.java
496. 下一个更大元素 I 简单 Solution496.java
503. 下一个更大元素 II 中等 Solution503.java 循环数组使用 % 运算
42. 接雨水 困难 Solution42.java ⭐️
1673. 找出最具竞争力的子序列 中等 Solution1673.java 子序列问题

计算当前值作为区间最大/最小值时的最大区间范围

该类型题目不直接要求找某元素左/右侧最近的大/小值,而是利用单调栈能找到某元素最近的大值/小值的特点来 确定当前元素作为区间内最大值/最小值时的区间范围这么说起来有点儿绕),以此来计算该元素对题解的"贡献"。

我们初始化每个元素的默认区间范围如下,这是该元素作为极值时的特殊情况:

int[] left = new int[nums.length];
Arrays.fill(left, -1);
int[] right = new int[nums.length];
Arrays.fill(right, nums.length);

以当前元素作为区间内最大值为例,记录每个元素能到达的左侧/右侧的最远距离:

Stack<Integer> stack = new Stack<>();

// 正序遍历计算上界
for(int i = 0; i < nums.length; i++) {
    while (!stack.isEmpty() && nums[i] >= nums[stack.peek()]) {
        right[stack.pop()] = i;    
    }  
    stack.push(i);
}
stack.clear();
// 逆序遍历计算下界
for (int i = nums.length - 1; i >= 0; i--) {
    while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) {
        left[stack.pop()] = i;
    }
    stack.push(i);
}

注意,记录的区间范围为全开区间,所以如果在计算区间长度时需要减 1,而且当题目中没有规定所有值都不同时,有时需要为其中一个(正序或逆序)遍历条件增加等号,避免发生“重复统计”。

题目链接 题解 备注
795. 区间子数组个数 中等 Solution795.java 乘法原理和重复值判断很需要注意
907. 子数组的最小值之和 中等 Solution907.java
84. 柱状图中最大的矩形 困难 Solution84.java ⭐️
85. 最大矩形 困难 Solution85.java 转换成 84 题来求解

队列

先进先出队列(简称队列)是一种基于先进先出(FIFO)策略的集合类型,它相比于栈多了能够在队首操作的方法,所以使用栈能解决的问题队列也能解决,不过使用队列解决的问题会突出 需要操作两端数据 的特点。

题目链接 题解 备注
622. 设计循环队列 中等 MyCircularQueue.java
1047. 删除字符串中的所有相邻重复项 简单 Solution1047.java
LCR 041. 数据流中的移动平均值 简单 MovingAverage.java
933. 最近的请求次数 简单 RecentCounter.java
649. Dota2 参议院 中等 Solution649.java

单调队列

单调队列是在单调栈的基础上实现了对 序列的两端操作,所以使用单调队能让我们 获取区间最值(队首即为最值)和 移除队首值。此外 不要局限 在只使用一个单调队列解题,有的题目需要维护两个单调队列来分别记录区间内的最大值和最小值来求解。

理论上使用单调栈能解决的问题单调队列也能解决,不过在我们不需要获取区间最值时还是使用单调栈来求解。

能获取区间最大值(nums[deque.peekFirst()])的单调递减队列模板如下:

    Deque<Integer> deque = new ArrayDeque<>();
    for (int i = 0; i < nums.length; i++) {
        while (!deque.isEmpty() && nums[i] > nums[deque.peekLast()]) {
            int index = deque.pollLast();
            // 关于 index 的特殊处理
            process();
        }
        deque.addLast(i);

        // 必要处理逻辑
        process1();
    }
题目链接 题解 备注
面试题59 - II. 队列的最大值 中等 MaxQueue.java
239. 滑动窗口最大值 困难 Solution239.java
1438. 绝对差不超过限制的最长连续子数组 中等 Solution1438.java ⭐️
654. 最大二叉树 中等 Solution654.java
2100. 适合打劫银行的日子 中等 Solution2100.java 单调队列的单调性的应用

题目链接 题解 备注
小顶堆实现 MyPriorityQueue.java
多路归并 Multiway.java
堆排序 DeapSort.java
LCR 159. 库存管理 III 简单 SolutionLCR159.java ✅大顶堆
面试题 17.14. 最小K个数 中等 Interview1714.java ✅大顶堆
1405. 最长快乐字符串 中等 Solution1405.java ✅大顶堆
215. 数组中的第K个最大元素 中等 Solution215.java ✅小顶堆
703. 数据流中的第 K 大元素 简单 KthLargest.java ✅小顶堆
692. 前K个高频单词 中等 Solution692.java ✅小顶堆
4. 寻找两个正序数组的中位数 困难 Solution4.java
295. 数据流的中位数 困难 MedianFinder.java
373. 查找和最小的 K 对数字 中等 Solution373.java ✅多路归并
1705. 吃苹果的最大数目 中等 Solution1705.java ✅贪心
1834. 单线程 CPU 中等 Solution1834.java ✅贪心
45. 跳跃游戏 II 中等 Solution45.java ✅贪心
871. 最低加油次数 困难 Solution871.java ✅贪心

散列表

实现散列表分为两步:

  1. 用散列函数将被查找的键转化为数组的一个索引,理想情况下,不同的键都能转化为不同的索引值
  2. 处理碰撞冲突,有两种常见的处理方法,分别为拉链法和线性探测法。前者的方法是将发生碰撞的元素保存在链表中;后者的思想是与其将内存用作链表,不如将它们保存在散列表的空元素中

散列表数据结构使用了适度的空间和时间,并在这两个极端之间找到了平衡

题目链接 题解 备注
169. 多数元素 简单 Solution169.java
229. 多数元素 II 中等 Solution229.java
1. 两数之和 简单 Solution1.java
205. 同构字符串 简单 Solution205.java
387. 字符串中的第一个唯一字符 简单 Solution387.java
242. 有效的字母异位词 简单 Solution242.java
409. 最长回文串 简单 Solution409.java
811. 子域名访问计数 中等 Solution811.java
299. 猜数字游戏 中等 Solution299.java
1282. 用户分组 中等 Solution1282.java
380. O(1) 时间插入、删除和获取随机元素 中等 RandomizedSet.java
388. 文件的最长绝对路径 中等 Solution388.java
447. 回旋镖的数量 中等 Solution447.java
2013. 检测正方形 中等 DetectSquares.java
41. 缺失的第一个正数 困难 Solution41.java 自建简单hash函数
49. 字母异位词分组 中等 Solution49.java
895. 最大频率栈 困难 FreqStack.java
2962. 统计最大元素出现至少 K 次的子数组 中等 Solution2962.java 固定右端点的子数组数量为以该右端点结尾的数组长度

排序算法

基础排序算法

题目链接 题解 备注
插入排序 InsertSort.java
希尔排序 ShellSort.java
选择排序 SelectionSort.java
冒泡排序 BubbleSort.java
题目链接 题解 备注
归并排序:基本实现 MergeSort.java
归并排序:将多次创建小数组的开销转换为只创建一次大数组 MergeSort2.java
归并排序:当数组有序时,跳过 merge() 方法 MergeSort3.java
归并排序:对小规模子数组使用插入排序 MergeSort4.java
快速排序:基本实现 QuickSort.java
快速排序:基准数优化 QuickSort2.java
快速排序:切换到插入排序 QuickSort3.java
快速排序:三向切分 QuickSort4.java
题目链接 题解 备注
桶排序 BucketSort.java
计数排序 CountingSort.java
基数排序 RadixSort.java

相关练习

题目链接 题解 备注
1051. 高度检查器 简单 Solution1051.java
1403. 非递增顺序的最小子序列 简单 Solution1403.java
LCR 186. 文物朝代判断 简单 SolutionLCR186.java
969. 煎饼排序 中等 Solution969.java ✅冒泡排序
LCR 170. 交易逆序对的总数 困难 SolutionLCR170.java ✅归并排序
324. 摆动排序 II 中等 Solution324.java
75. 颜色分类 中等 Solution75.java 快速排序:三向切分
1833. 雪糕的最大数量 中等 Solution1833.java 计数排序
451. 根据字符出现频率排序 中等 Solution451.java ✅自定义排序
937. 重新排列日志文件 中等 Solution937.java ✅自定义排序
LCR 164. 破解闯关密码 中等 SolutionLCR164.java ✅自定义排序

二叉搜索树和二叉树的中序遍历

题目链接 题解 备注
二叉搜索树 BinarySearchTree.java
94. 二叉树的中序遍历 简单 Solution94.java
LCR 174. 寻找二叉搜索树中的目标节点 简单 SolutionLCR174.java
1305. 两棵二叉搜索树中的所有元素 中等 Solution1305.java
230. 二叉搜索树中第K小的元素 中等 Solution230.java
235. 二叉搜索树的最近公共祖先 中等 Solution235.java
450. 删除二叉搜索树中的节点 中等 Solution450.java
669. 修剪二叉搜索树 中等 Solution669.java
98. 验证二叉搜索树 中等 Solution98.java
LCR 155. 将二叉搜索树转化为排序的双向链表 中等 SolutionLCR155.java
99. 恢复二叉搜索树 中等 Solution99.java
面试题 04.06. 后继者 中等 Interview0406.java

二叉树前序遍历

题目链接 题解 备注
144. 二叉树的前序遍历 简单 Solution144.java
226. 翻转二叉树 简单 Solution226.java
617. 合并二叉树 简单 Solution617.java
101. 对称二叉树 简单 Solution101.java
108. 将有序数组转换为二叉搜索树 简单 Solution108.java
109. 有序链表转换二叉搜索树 中等 Solution109.java
654. 最大二叉树 中等 Solution654.java
129. 求根节点到叶节点数字之和 中等 Solution129.java
449. 序列化和反序列化二叉搜索树 中等 Codec.java
113. 路径总和 II 中等 Solution113.java
LCR 143. 子结构判断 中等 SolutionLCR143.java
662. 二叉树最大宽度 中等 Solution662.java
LCR 152. 验证二叉搜索树的后序遍历序列 中等 SolutionLCR152.java
105. 从前序与中序遍历序列构造二叉树 中等 Solution105.java
106. 从中序与后序遍历序列构造二叉树 中等 Solution106.java

二叉树后序遍历

题目链接 题解 备注
145. 二叉树的后序遍历 简单 Solution145.java
104. 二叉树的最大深度 简单 Solution104.java
110. 平衡二叉树 简单 Solution110.java
236. 二叉树的最近公共祖先 中等 Solution236.java
337. 打家劫舍 III 中等 Solution337.java
814. 二叉树剪枝 中等 Solution814.java
687. 最长同值路径 中等 Solution687.java
124. 二叉树中的最大路径和 困难 Solution124.java
1080. 根到叶路径上的不足节点 中等 Solution1080.java
979. 在二叉树中分配硬币 中等 Solution979.java

二叉树层序遍历

题目链接 题解 备注
102. 二叉树的层序遍历 中等 Solution102.java
111. 二叉树的最小深度 简单 Solution111.java
LCR 151. 彩灯装饰记录 III 中等 SolutionLCR151.java
103. 二叉树的锯齿形层序遍历 中等 Solution103.java
199. 二叉树的右视图 中等 Solution199.java
623. 在二叉树中增加一行 中等 Solution623.java
655. 输出二叉树 中等 Solution655.java
987. 二叉树的垂序遍历 困难 Solution987.java
297. 二叉树的序列化与反序列化 困难 Codec.java

dfs

题目链接 题解 备注
114. 二叉树展开为链表 中等 Solution114.java
437. 路径总和 III 中等 Solution437.java
652. 寻找重复的子树 中等 Solution652.java
2096. 从二叉树一个节点到另一个节点每一步的方向 中等 Solution2096.java
863. 二叉树中所有距离为 K 的结点 中等 Solution863.java

红黑树

题目链接 题解 备注
左倾红黑树 LeftLeaningRedBlackTree.java 树专题 —— 深入理解左倾红黑树
经典红黑树 / 树专题 —— 深入理解经典红黑树
2034. 股票价格波动 中等 StockPrice.java
220. 存在重复元素 III 困难 Solution220.java 滑动窗口 + 红黑树

基础知识

深度优先搜索是先寻找离起点更远的顶点,只有在碰到死胡同时才访问近处的顶点;广度优先搜索则会先覆盖起点附近的顶点,只有在临近的所有顶点都被访问了之后才能前进。

题目链接 题解 备注
无向图 Graph.java
深度优先搜索 DepthFirstPaths.java
广度优先搜索 BreadthFirstPaths.java
Prim算法查找最小生成树 PrimMST.java
有向图 Digraph.java
Dijkstra算法查找最短路径 Dijkstra.java

有向图

题目链接 题解 备注
207. 课程表 中等 Solution207.java 判断是否有环

拓扑排序

拓扑排序是一种对有向无环图中顶点进行排序的算法,在拓扑排序中,如果图中存在一条从顶点 A 到顶点 B 的路径,那么在排序中顶点 A 出现在顶点 B 的前面,需要应用拓扑排序求解的题目会给出“顶点”间存在依赖关系的条件。

    public int[] findOrder(int numCourses, int[][] prerequisites) {
        // 创建有向图
        Digraph digraph = new Digraph(numCourses, prerequisites);
        // 拓扑排序求解
        return digraph.topological();
    }

    static class Digraph {

        // 顶点数
        private final int V;

        // 邻接表
        private final HashSet<Integer>[] adj;

        // 入度
        private final int[] inDegree;

        public Digraph(int numCourses, int[][] prerequisites) {
            this.V = numCourses;
            inDegree = new int[V];
            adj = new HashSet[V];
            for (int i = 0; i < adj.length; i++) {
                adj[i] = new HashSet<>();
            }
            // 初始化邻接表并统计每个顶点的入度
            for (int[] prerequisite : prerequisites) {
                adj[prerequisite[1]].add(prerequisite[0]);
                inDegree[prerequisite[0]]++;
            }
        }

        /**
         * 拓扑排序:找到图中入度为 0 的顶点,以及由入度为 0 顶点所指向的顶点
         */
        public int[] topological() {
            // 将所有入度为 0 的顶点入队
            ArrayDeque<Integer> deque = new ArrayDeque<>();
            for (int i = 0; i < inDegree.length; i++) {
                if (inDegree[i] == 0) {
                    deque.offer(i);
                }
            }

            // 将队列执行出队操作,出队的顺序就是拓扑序
            int index = 0;
            int[] res = new int[V];
            while (!deque.isEmpty()) {
                Integer v = deque.poll();
                for (Integer w : adj[v]) {
                    inDegree[w]--;
                    // 入度为 0 入队
                    if (inDegree[w] == 0) {
                        deque.offer(w);
                    }
                }
                res[index++] = v;
            }

            if (index == res.length) {
                return res;
            }
            return new int[0];
        }
    }
题目链接 题解 备注
210. 课程表 II 中等 Solution210.java
802. 找到最终的安全状态 中等 Solution802.java
851. 喧闹和富有 中等 Solution851.java

无向图

题目链接 题解 备注
1519. 子树中标签相同的节点数 中等 Solution1519.java

回溯算法

子集型回溯

题目链接 题解 备注
257. 二叉树的所有路径 简单 Solution257.java
78. 子集 中等 Solution78.java
17. 电话号码的字母组合 中等 Solution17.java
131. 分割回文串 中等 Solution131.java
784. 字母大小写全排列 中等 Solution784.java
22. 括号生成 中等 Solution22.java ⭐️
139. 单词拆分 中等 Solution139.java 字符串API word.startsWith(s); 和备忘录

组合型回溯

题目链接 题解 备注
77. 组合 中等 Solution77.java
39. 组合总和 中等 Solution39.java
40. 组合总和 II 中等 Solution40.java ⭐️
216. 组合总和 III 中等 Solution216.java

排列型回溯

题目链接 · 题解 备注
46. 全排列 中等 Solution46.java
47. 全排列 II 中等 Solution47.java ⭐️
LCR 157. 套餐内商品的排列顺序 中等 SolutionLCR157.java
面试题 08.12. 八皇后 困难 Interview0812.java
10. 正则表达式匹配 困难 Solution10.java

动态规划(待完善)

动态规划(dynamic programming)常用于 解决最优问题,它与分治法相似,都是通过组合子问题的解来求解原问题(programming 在这指的是一种表格法,而非计算机编程)。分治法是将问题分为互不相交的子问题,递归的求解子问题,再将它们的解组合起来,求出原问题的解。相反地,动态规划应用于子问题重叠的情况,即不同的子问题具有公共子问题,如果采用分治法的话,会反复地求解公共子问题,而动态规划算法对每个子问题只求解一次,并将解保存在表格中(也就是常用的dp数组),以便下次需要同样的子问题求解时,避免重复计算。

当发现题目需要采用动态规划求解时,一般需要考虑如下问题:

  1. 这个问题的 base case 是什么?base case 是一些简单的,能直接列出来的子问题的解,求解其他父问题时,需要依赖这些 base case
  2. 考虑如何利用这些 base case 求解父问题(也是网上常说归纳状态转移方程)
  3. 考虑如何定义dp来记录这些解,一般情况下一维dp数组就足够,像路径问题和子序列问题考虑使用二维dp数组

注意求解两字符串相比较的问题时(如编辑距离问题),一般定义二维dp数组,如下图所示,dp数组定义的长度和宽度分别为两字符串长度加一,黄色的方格为初始化 base case,记蓝色方格为待求解方格,其对角线方向的红色方格表示的是相等字符串的值。可以通过红色、绿色和紫色方格对蓝色方格进行求解:

  • 红色 -> 蓝色:表示已经相等的字符串经操作后再相等的结果值
  • 绿色 -> 蓝色:表示字符串text1转换成字符串text2的结果值
  • 紫色 -> 蓝色:表示字符串text2转换成字符串text1的结果值

img.png

记忆化搜索

题目链接 题解 备注
377. 组合总和 Ⅳ 中等 Solution377.java

递推

题目链接 题解 备注
509. 斐波那契数 简单 Solution509.java
70. 爬楼梯 简单 Solution70.java
746. 使用最小花费爬楼梯 简单 Solution746.java
LCR 165. 解密数字 中等 SolutionLCR165.java
2466. 统计构造好字符串的方案数 中等 Solution2466.java
2266. 统计打字方案数 中等 Solution2266.java

打家劫舍

题目链接 题解 备注
198. 打家劫舍 中等 Solution198.java
740. 删除并获得点数 中等 Solution740.java
2320. 统计放置房子的方式数 中等 Solution2320.java
213. 打家劫舍 II 中等 Solution213.java

子数组和

题目链接 题解 备注
53. 最大子数组和 中等 Solution53.java
2606. 找到最大开销的子字符串 中等 Solution2606.java
1749. 任意子数组和的绝对值的最大值 中等 Solution1749.java

最值问题

题目链接 题解 备注
322. 零钱兑换 中等 Solution322.java
343. 整数拆分 中等 Solution343.java
264. 丑数 II 中等 Solution264.java
面试题 17.09. 第 k 个数 中等 Interview1709.java
1218. 最长定差子序列 中等 Solution1218.java

最小路径和问题

题目链接 题解 备注
64. 最小路径和 中等 Solution64.java
LCR 166. 珠宝的最高价值 中等 SolutionLCR166.java
72. 编辑距离 中等 Solution72.java

子序列问题

涉及子序列,一般情况下时间复杂度为 $O(n^2)$,那么就跑不了双层的for循环

  • 针对数组的最长递增子序列问题:
int n = array.length;
int[] dp = new int[n];

for (int i = 0; i < n; i++) {
    for (int j = 0; j < i; j++) {
        dp[i] = 最值;    
    }
}
  • 针对两个数组或字符串的子序列问题:
int n1 = array1.length;
int n2 = array2.length;
int[][] dp = new int[n1][n2];

for (int i = 0; i < n1; i++) {
    for (int j = 0; j < n2; j++) {
        if (n1[i] == n2[j]) {
            dp[i][j] =
        } else {
            dp[i][j] =
        }    
    }    
}
题目链接 题解 备注
1143. 最长公共子序列 中等 Solution1143.java
1035. 不相交的线 中等 Solution1035.java
516. 最长回文子序列 中等 Solution516.java
1312. 让字符串成为回文串的最少插入次数 困难 Solution1312.java
300. 最长递增子序列 中等 Solution300.java
673. 最长递增子序列的个数 中等 Solution637.java
354. 俄罗斯套娃信封问题 困难 Solution354.java

其他问题

题目链接 题解 备注
LCR 185. 统计结果概率 中等 SolutionLCR185.java
467. 环绕字符串中唯一的子字符串 中等 Solution467.java

递归

递归矩阵问题注意单元格重复访问的问题,一般用 visited[][] 来标记是否访问过

题目链接 题解 备注
200. 岛屿数量 中等 Solution200.java
LCR 129. 字母迷宫 中等 SolutionLCR129.java
LCR 130. 衣橱整理 中等 SolutionLCR130.java
79. 单词搜索 中等 Solution79.java

贪心算法

贪心算法可以通过局部最优解来构造全局最优解,也就是说,在构造局部最优解时只需关注当前问题,而不必考虑子问题的解。这也是贪心算法与动态规划不同的地方,动态规划需要在每个步骤中都要进行一次选择,通常以一种自底向上的方式求解(先求子问题,再求较大的子问题),而贪心算法通常是自顶向下的,进行一次又一次选择,将给定问题变得更小,它可能依赖之前做出的选择,但不依赖任何将来的选择或是子问题的解。

题目链接 题解 备注
121. 买卖股票的最佳时机 简单 Solution121.java
122. 买卖股票的最佳时机 II 中等 Solution122.java
123. 买卖股票的最佳时机 III 困难 Solution123.java
179. 最大数 中等 Solution179.java 理解字符串的自定义排序
55. 跳跃游戏 中等 Solution55.java
334. 递增的三元子序列 中等 Solution334.java
135. 分发糖果 困难 Solution135.java
768. 最多能完成排序的块 II 困难 Solution768.java
1953. 你可以工作的最大周数 中等 Solution1953.java

位运算

题目链接 题解 备注
LCR 133. 位 1 的个数 简单 SolutionLCR133.java
231. 2 的幂 简单 Solution231.java 2的幂有 (n & (n - 1)) == 0
50. Pow(x, n) 中等 Solution50.java
136. 只出现一次的数字 简单 Solution136.java
137. 只出现一次的数字 II 中等 Solution137.java
260. 只出现一次的数字 III 中等 Solution260.java
318. 最大单词长度乘积 中等 Solution318.java
371. 两整数之和 中等 Solution371.java
1073. 负二进制数相加 中等 Solution1073.java

树状数组

相关学习:深入理解树状数组

树状数组是一种简单的数据结构,它支持单点修改和区间查询操作,一般的 RMQ 问题优先选择树状数组求解,而不是线段树,后者相对来说代码量大,也比较复杂

题目链接 题解 备注
307. 区域和检索 - 数组可修改 中等 NumArray.java
1395. 统计作战单位数 中等 Solution1395.java ⭐️
2179. 统计数组中好三元组数目 困难 Solution2179.java
775. 全局倒置与局部倒置 中等 Solution775.java
327. 区间和的个数 困难 Solution327.java

线段树

相关学习:深入理解线段树

线段树可以解决区间和、区间最大值或区间最小值的问题(RMQ 问题),不过线段树的代码量相对来说较大而且比较复杂,所以线段树是在前缀和、差分和树状数组解决方法之后不得已才会考虑的方案。 一般使用线段树的题目都具备 区间修改和区间查询 的特点,如果大家在这里是按照顺序刷的话,应该对 RMQ 问题有一个比较充分的了解了,在这里做一下相关题型解法的归纳:

  • 数组不变,区间查询:前缀和、树状数组和线段树
  • 数组单点修改,区间查询:树状数组和线段树
  • 数组区间修改,单点查询:差分和线段树
  • 数组区间修改,区间查询:线段树

注意每种题型涉及的解法都是越靠前越优先考虑。

单点修改和区间查询

题目链接 题解 备注
307. 区域和检索 - 数组可修改 中等 NumArray.java
239. 滑动窗口最大值 困难 Solution239.java
654. 最大二叉树 中等 Solution654.java

区间修改

题目链接 题解 备注
1893. 检查是否区域内所有整数都被覆盖 简单 Solution1893.java
1109. 航班预订统计 中等 Solution1109.java

动态开点

题目链接 题解 备注
729. 我的日程安排表 I 中等 MyCalendar.java
731. 我的日程安排表 II 中等 MyCalendarTwo.java ⭐️
732. 我的日程安排表 III 困难 MyCalendarThree.java
715. Range 模块 困难 RangeModule.java ✅️ 理解 add 是作为区间变化量还是区间内单个值的变化量

模拟

题目链接 题解 备注
796. 旋转字符串 简单 Solution796.java
1893. 检查是否区域内所有整数都被覆盖 简单 Solution1893.java
415. 字符串相加 简单 Solution415.java
406. 根据身高重建队列 中等 Solution406.java
1109. 航班预订统计 中等 Solution1109.java
729. 我的日程安排表 I 中等 MyCalendar.java
304. 二维区域和检索 - 矩阵不可变 中等 NumMatrix.java
901. 股票价格跨度 中等 StockSpanner.java
560. 和为 K 的子数组 中等 Solution560.java
496. 下一个更大元素 I 简单 Solution496.java
556. 下一个更大元素 III 中等 Solution556.java
219. 存在重复元素 II 简单 Solution219.java
611. 有效三角形的个数 中等 Solution611.java
54. 螺旋矩阵 中等 Solution54.java
59. 螺旋矩阵 II 中等 Solution59.java
48. 旋转图像 中等 Solution48.java
189. 轮转数组 中等 Solution189.java
89. 格雷编码 中等 Solution89.java
400. 第 N 位数字 中等 Solution400.java
12. 整数转罗马数字 中等 Solution12.java
2934. 最大化数组末位元素的最少操作次数 中等 Solution2934.java
2672. 有相同颜色的相邻元素数目 中等 Solution2672.java
3025. 人员站位的方案数 I 中等 Solution3025.java
2257. 统计网格图中没有被保卫的格子数 中等 Solution2257.java

About

LeetCode高频题目,包含学习整理的文章和刷题模板,参考宫水三叶博主、《算法(第四版)》、《算法导论》和《Hello 算法》等技术书籍

Topics

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages