题型一:二分求下标
- 重点问题
题号 | 链接 | 题解 |
---|---|---|
704 | 二分查找(简单) | |
35 | 搜索插入位置(简单) | 【视频讲解】、文字题解 |
34 | 在排序数组中查找元素的第一个和最后一个位置(简单) | 【视频讲解】、文字题解 |
1095 | 山脉数组中查找目标值(中等) | 【视频讲解】、文字题解 |
4 | 寻找两个有序数组的中位数(困难) | 【视频讲解】、文字题解 |
说明:
- 第 34 题:二分查找找边界问题、CSDN、庸才顾子汐:关于 while (left <= right) 写法返回值的详细讨论;
- 第 4 题:二分查找里最难的问题,重点在于理解:① 为什么是在短数组里找边界;② 边界条件的判断。
练习:
题号 | 链接 | 题解 |
---|---|---|
33 | 搜索旋转排序数组(中等) | 文字题解 |
81 | 搜索旋转排序数组 II(中等) | 文字题解 |
153 | 153. 寻找旋转排序数组中的最小值(中等) | 文字题解 |
154 | 154. 寻找旋转排序数组中的最小值 II(困难) | 文字题解 |
275 | H指数 II(中等) | 文字题解 |
436 | 寻找右区间(中等) | 文字题解 |
1237 | 找出给定方程的正整数解(中等) | |
1300 | 转变数组后最接近目标值的数组和(中等) | 文字题解 |
题型二:二分确定一个有范围的整数(二分答案)
算法思想:减而治之。如果题目要我们找一个整数,这个整数有确定的范围,可以通过二分查找逐渐缩小范围,最后逼近到一个数。
题号 | 链接 | 题解 |
---|---|---|
69 | x 的平方根(简单) | 文字题解 |
287 | 寻找重复数(中等) | 文字题解 |
374 | 猜数字大小(简单) | 文字题解 |
1283 | 使结果不超过阈值的最小除数(中等) | 文字题解 |
1292 | 元素和小于等于阈值的正方形的最大边长(中等) |
题型三:复杂的判别函数(最大值极小化问题)
说明:这一类问题本质上还是「题型二」(二分答案),但是初学的时候会觉得有一些绕。这一类问题的问法都差不多,关键字是「连续」、「正整数」,请大家注意捕捉题目中这样的关键信息。
题号 | 链接 | 题解 |
---|---|---|
875 | 爱吃香蕉的珂珂(中等) | 文字题解 |
410 | 分割数组的最大值(困难) | 文字题解 |
LCP 12 | 小张刷题计划(中等) | |
1011 | 在 D 天内送达包裹的能力(中等) | |
1482 | 制作 m 束花所需的最少天数(中等) | |
1552 | 两球之间的磁力(中等) |
第 3 章 基础排序算法
这一部分包含了四种基础排序算法:选择排序、插入排序、希尔排序、冒泡排序。
「力扣」第 912 题:排序数组 的 题解:总结了排序问题的一些要点和学习资料,可以从排序问题开始学习算法。
数组的问题可以作为算法「新手场」,因为这些问题只需要掌握编程语言的基础知识就可以完成。以下问题都很容易想到解决方案,即使没有学习过相关的数据结构和算法知识。
知识点:循环不变量
- 循环不变量用于证明算法的有效性,也是编码正确的理论依据;
- 循环不变量定义帮助分清先加还是先赋值,还有一些边界条件。定义清楚循环不变量以后,代码的编写就会很轻松;
- 建议把「循环不变量」作为注释写在代码里,以方便自己调试和他人阅读。
题号 | 链接 | 题解 |
---|---|---|
912 | 排序数组(中等) | 文字题解 |
26 | 删除排序数组中的重复项(简单) | |
27 | 移除元素(简单) | |
283 | 移动零(简单) | 文字题解 |
第 4 章 高级排序算法(重要)
这一部分需要重点掌握三种高级排序算法:归并排序、快速排序、堆排序。
题号 | 链接 | 题解 |
---|---|---|
88 | 合并两个有序数组(简单) | 从后向前归并 |
《剑》51 | 数组中的逆序对(困难) | 【视频讲解】、文字题解 |
75 | 颜色分类(中等) | 文字题解 |
215 | 数组中的第K个最大元素(中等) | 文字题解 |
451 | 根据字符出现频率排序(中等) |
说明:
- 第 88 题:归并排序,注意这里从后向前归并;
- 《剑指 Offer》第 51 题:归并排序、树状数组(选学);
- 第 75 题:著名的「荷兰国旗」问题、快排;
- 第 215 题:快排、优先队列;
- 第 451 题:快排、优先队列。
第 5 章 非比较排序(选学)
这一部分包含了三种非比较排序排序:计数排序、基数排序、桶排序。解决这些问题需要知道 原地哈希 这个概念。
题号 | 链接 | 题解 |
---|---|---|
41 | 缺失的第一个正数(困难) | 【视频讲解】、文字题解 |
《剑》3 | 剑指 Offer 03. 数组中重复的数字(中等) | |
448 | 找到所有数组中消失的数字(简单) | |
442 | 数组中重复的数据(中等) |
第 6 章 滑动窗口与双指针
一、滑动窗口
- 思想简单,但是代码比较难一次写对;
- 滑动窗口的思想是:先向右移动右指针、再向右移动左指针,这样左右指针交替执行( 不回头 ),可以完成一些问题;
- 滑动窗口是 暴力解法的优化 ,如何 根据目标函数把暴力解法的一系列解排除掉,是使用滑动窗口的前提 ,一定要分析清楚;
- 下面提供的是一种参考的写法,请不要照搬,应该 先理解滑动窗口的思想(暴力解法的剪枝) ,然后多加练习,掌握编写代码的技巧和细节。
滑动窗口的参考写法(不是模板,请不要原样照搬,仅供参考,理解算法设计思想是更重要的):
public class Solution {
public String slidingWindow(String s, String t) {
// 起始的时候,都位于 0,同方向移动
int left = 0;
int right = 0;
while (right < sLen) {
if ( 在右移的过程中检测是否满足条件 ) {
// 对状态做修改,好让程序在后面检测到满足条件
}
// 右边界右移 1 格
right++;
while ( 满足条件 ) {
// 走到这里是满足条件的,左边界逐渐逐渐左移,可以取最小值
if ( 在左移的过程中检测是否不满足条件 ) {
// 对状态做修改,好让程序在后面检测到不满足条件
}
// 左边界左移 1 格
left++;
}
// 走到这里是不满足条件的,右边界逐渐右移,可以取最大值
}
return 需要的结果变量;
}
}
友情提示:第 3 题和第 76 题是必须要会做的基本问题。上面的问题理解透彻了,下面的问题就可以比较轻松地做出来。
重点问题:
题号 | 链接 | 题解 |
---|---|---|
3 | 无重复字符的最长子串(中等) | 文字题解 |
76 | 最小覆盖子串(困难) | [【视频讲解】]() |
209 | 长度最小的子数组(中等) | |
424 | 替换后的最长重复字符(中等) | |
1493 | 删掉一个元素以后全为 1 的最长子数组(中等) |
说明:
- 第 3 题:先暴力解法,再优化;
- 第 76 题:滑动窗口的典型问题,重点分析为什么可以使用滑动窗口。字符频数数组可以使用哈希表,也可以直接使用数组;使用 距离 的定义加速计算;
- 第 424 题:重点分析为什么可以使用滑动窗口。设计变量
maxCount
的含义:在滑动的过程中,出现的字符频数最多的个数;收集结果的判断语句(while (right - left > maxCount + k)
)比较难想到。第 424 题同类问题:「力扣」第 1493 题:删掉一个元素以后全为 1 的最长子数组 。
public class Solution {
// 第 424 题代码:滑动窗口(暴力解法的优化)
public int longestSubarray(int[] nums) {
int len = nums.length;
int left = 0;
int right = 0;
// 连续的 1 的个数
int ones = 0;
// 删除一个元素以后全为 1 的最长的子串的长度
int maxCount = 0;
int res = 0;
while (right < len) {
if (nums[right] == 1) {
ones++;
}
maxCount = Math.max(maxCount, ones);
right++;
// maxCount + 1 里的 1 就表示删除的那个元素
while (right - left > maxCount + 1) {
if (nums[left] == 1) {
ones--;
}
left++;
}
res = Math.max(res, right - left);
}
// 注意:这里返回 res 要减 1
return res - 1;
}
}
练习:
题号 | 题目 | 题解 | 知识点 |
---|---|---|---|
438 | 找到字符串中所有字母异位词(中等) | ||
567 | 字符串的排列(中等) | ||
643 | 子数组最大平均数 I(简单) | ||
978 | 最长湍流子数组(中等) | ||
992 | K 个不同整数的子数组(困难) |
说明:
- 第 209 题:题目中给出的关键信息:数组里的元素全部是正整数。一共有以下 3 种方法。
- 方法一:暴力解法
- 方法二:滑动窗口(分析可以使用滑动窗口的原因)
- 方法三:构造前缀和数组,然后使用二分查找
- 第 438 题:同第 76 题;
- 第 567 题:同第 76 题,收集符合条件的语句不一样而已。
二、双指针
「双指针」问题其实也是朴素算法的优化,一下子排序掉很多不符合题意的解,「滑动窗口」技巧也是这样的。依然是分析为什么可以使用双指针是更重要的。
二分查找算法应用于查找下标也可以认为是双指针的解法。
题号 | 链接 | 题解 | 知识点 |
---|---|---|---|
11 | 盛最多水的容器(中等) | ||
15 | 三数之和(中等) | ||
16 | 最接近的三数之和(中等) | 文字题解 | |
42 | 接雨水(困难) | 文字题解 | |
167 | 两数之和 II - 输入有序数组(简单) | 文字题解 | |
925 | 长按键入(简单) |
第 7 章 链表
解决链表问题,很实用的技巧是「画图」。其它算法问题的分析和讲解(和面试官讲解)也是这样。
可以为链表编写测试函数,方便调试。建议实现的方法有:① 通过数组创建一个单链表;② 根据当前结点打印当前结点以及后面的结点。这两个方法可以非常方便地帮助我们调试关于链表的程序。
题型一:基本的链表指针指向问题
注意:有一些问题需要使用「虚拟头结点」,以避免对链表第一个结点的复杂的分类讨论逻辑。这个思想在数组里我们见过,叫「哨兵」。
使用递归函数,避免复杂的更改指针变量指向操作,使得求解问题变得简单。
题号 | 链接 | 题解 |
---|---|---|
2 | 两数相加 | |
82 | 删除排序链表中的重复元素 II | |
26 | 反转链表 | |
24 | 两两交换链表中的节点 | |
25 | K 个一组翻转链表 | |
328 | 奇偶链表 | |
203 | 移除链表元素 | |
21 | 合并两个有序链表(简单) | |
876 | 链表的中间结点(简单) | 文字题解 |
148 | 排序链表 | 文字题解 |
说明:
- 这些问题使用递归和迭代都可以完成:206、24、25、328、203、21;
- 第 148 题需要知道如何使用递归函数实现链表排序,迭代的写法仅供参考。
题型二:快慢指针技巧
确切地说,叫「同步指针」可能更好一些。
使用两个指针变量,刚开始都位于链表的第一个结点,一个永远一次只走一步,另一个永远一次只走两步,一个在前,一个在后,同时走。这样当快指针走完的时候,慢指针就来到了链表的中间位置。
解决这些问题的共同特点就是使用两个指针变量同步移动。快慢指针的前进方向相同,且它们步伐的「差」是恒定的,根据这种确定性去解决链表中的一些问题。使用这种思想还可以解决链表的以下问题:
题号 | 链接 | 题解 |
---|---|---|
19 | 倒数第 k 个结点 | |
141 | 环形链表 | |
142 | 环形链表 II | |
161 | 相交链表 |
说明:
- 第 19 题:,快指针先走几步,不是靠猜的,要在纸上画图模拟一下,就清楚了;
- 第 141 题:,在环中的时候可以想象,A 同学开始有存款 100 元,每天赚 1 元,B 同学开始有存款 50 元,每天赚 2 元,B 同学一定会在某一天和 A 同学的存款一样;
- 第 161 题:起点不同,构造相同长度让它们相遇,同样是利用了同步走这个等量关系。
题型三:设计数据结构
题号 | 链接 | 题解 |
---|---|---|
707 | 设计链表(中等) | |
355 | 设计推特(中等) | 哈希表 + 链表 + 优先队列(经典多路归并问题)(Java) |
146 | LRU 缓存机制(中等) | 哈希表 + 双向链表(Java) |
460 | LFU 缓存(困难) | 哈希表 + 双向链表(Java) |
1206 | 设计跳表(困难) |
第 8 章 栈与队列
一、栈
题型一:基本的使用栈解决的问题
下面的问题非常基础,一定需要掌握:
题号 | 链接 | 题解 |
---|---|---|
20 | 有效的括号(简单) | |
71 | 简化路径(中等) | |
155 | 最小栈(简单) | 文字题解 |
225 | 用队列实现栈(简单) | 文字题解 |
232 | 用栈实现队列(简单) | 文字题解 |
946 | 946. 验证栈序列(中等) |
练习:
题号 | 链接 | 题解 |
---|---|---|
284 | 顶端迭代器(中等) | |
341 | 扁平化嵌套列表迭代器(中等) | |
946 | 验证栈序列(中等) | |
1111 | 有效括号的嵌套深度(中等) | 文字题解 |
题型二:单调栈
单调栈就是普通的栈,在使用的过程中恰好符合了「后进先出」,栈内元素单调的特点。「单调栈」和「单调队列」的问题通常来说很特殊,掌握例题和一些练习就可以了。
经验:单调栈中一般存下标。
题号 | 链接 | 题解 |
---|---|---|
84 | 柱状图中最大的矩形(困难) | 视频题解、文字题解 |
42 | 接雨水(困难) | 文字题解 |
739 | 每日温度(中等) | 文字题解 |
316 | 去除重复字母(困难) | 文字题解 |
说明:
- 第 739 题:推荐阅读 程序员的自我修养:739. Daily Temperatures;
练习:
序号 | 题目 | 题解 |
---|---|---|
496 | 下一个更大元素 I(简单) | 暴力解法、单调栈 |
503 | 下一个更大元素 II(中等) | |
901 | 股票价格跨度(中等) | LeetCode 第 901 题:股票价格跨度(单调栈) |
二、队列
题型一:基本的使用队列解决的问题
所有的使用广度优先遍历解决的问题,都使用了队列。
题号 | 题目序号 | 题解 |
---|---|---|
622 | 设计循环队列(中等) | 数组实现的循环队列 |
641 | 设计循环双端队列(中等) | 数组实现的循环双端队列 |
621 | 任务调度器(中等) | |
1306 | 跳跃游戏 III(中等)(中等) |
题型二:单调队列
单调队列就是普通的队列。「力扣」上的单调队列目前就发现这一个问题,关键分析清楚为什么设计的算法恰好使得单调队列。另外,「背包问题」中有使用单调队列进行优化的例子,感兴趣的朋友可以了解一下,是竞赛方面的知识。
经验:单调队列中一般存下标。
题号 | 链接 | 题解 |
---|---|---|
239 | 滑动窗口最大值(中等) | 文字题解 |
第 9 章 优先队列
说明:了解「堆」作为「优先队列」的实现是有必要的,有助于理解 remove()
、replace()
这些编码的细节,使用堆的时候才会更加有效。
应用:动态 选取当前队列中优先级最高的元素,重点理解「动态」的含义。
题号 | 链接 | 题解 |
---|---|---|
23 | 合并K个排序链表(困难) | 文字题解 |
215 | 数组中的第K个最大元素(中等) | 文字题解 |
295 | 数据流的中位数(困难) | 文字题解 |
347 | 前 K 个高频元素(中等) | |
703 | 数据流中的第K大元素(简单) | |
973 | 最接近原点的 K 个点(中等) | |
1296 | 划分数组为连续数字的集合(中等) |
第 10 章 并查集
并查集知识点的【视频讲解】在第 990 题视频题解里有。基础且常见的问题有:
题号 | 链接 | 题解 |
---|---|---|
990 | 等式方程的可满足性(中等) | 视频题解、文字题解 |
547 | 朋友圈(中等)(中等) | 文字题解 |
200 | 岛屿数量(中等)(中等) | 文字题解 |
684 | 冗余连接(中等) | |
1319 | 连通网络的操作次数(中等) | 文字题解 |
128 | 最长连续序列(困难)(中等) |
选做问题:
题号 | 链接 | 题解 |
---|---|---|
945 | 使数组唯一的最小增量(中等) | 文字题解 |
399 | 除法求值(中等) | |
685 | 冗余连接 II(困难) | |
721 | 账户合并(中等) | |
765 | 情侣牵手(困难) | |
952 | 按公因数计算最大组件大小(困难) | 文字题解 |
第 11 章 树(二叉树与二分搜索树)
题号 | 题目序号 | 题解 |
---|---|---|
105 | 从前序与中序遍历序列构造二叉树(中等) | 视频题解、文字题解 |
106 | 从中序与后序遍历序列构造二叉树(中等) | 文字题解 |
226 | 翻转二叉树(中等) | 文字题解 |
94 | 二叉树的中序遍历(中等) | 文字题解 |
230 | 二叉搜索树中第 K 小的元素(中等) | 文字题解 |
108 | 将有序数组转换为二叉搜索树(中等) | 文字题解 |
109 | 有序链表转换二叉搜索树(中等) | 文字题解 |
199 | 二叉树的右视图(中等) | 文字题解 |
第 12 章 回溯算法
题型一:基本回溯问题
通过这些问题理解回溯算法的思想,回溯算法的知识点讲解在「力扣」第 46 题的视频题解和文字题解。
回溯就是用深度优先遍历的方式去搜索 树(图)的所有解。深度优先遍历有很明显的递归结构。
做对下面这些问题的技巧:① 画图、画图、画图;② 理解深度优先遍历与递归;③ 多调试、多调试。
题号 | 题目序号 | 题解 |
---|---|---|
46 | 全排列(中等) | 视频题解、文字题解 |
47 | 全排列 II(中等) | 视频题解、文字题解 |
78 | 子集(中等) | 视频题解、文字题解 |
90 | 子集 II(中等) | 视频题解 |
77 | 组合(中等) | 文字题解 |
39 | 组合总和(中等) | 文字题解 |
40 | 组合总和 II(中等) | 文字题解 |
113 | 路径总和 II(中等) | 文字题解 |
60 | 第 k 个排列(中等) | 文字题解 |
257 | 二叉树的所有路径(中等) | 文字题解 |
491 | 递增子序列(中等) | |
1593 | 拆分字符串使唯一子字符串的数目最大(中等) | |
1071 | 活字印刷(中等) | 设计递归函数返回值 |
题型二:字符串上的回溯问题
重点理解:由于字符串每次都生成新字符,无须状态重置。
题号 | 链接 | 题解 |
---|---|---|
17 | 电话号码的字母组合(中等) | 文字题解 |
22 | 括号生成(中等) | 文字题解 |
93 | 复原IP地址(中等) | 文字题解 |
784 | 字母大小写全排列(中等) | 文字题解 |
题型三:Flood Fill
题号 | 链接 | 题解 |
---|---|---|
79 | 单词搜索(中等) | 文字题解 |
200 | 被围绕的区域(中等) | |
130 | 被围绕的区域(中等) |
题型四:一些游戏问题
序号 | 题目序号 | 题解 |
---|---|---|
51 | N皇后(困难) | 文字题解 |
37 | 解数独(困难) | |
529 | 扫雷游戏(中等) | 文字题解 |
说明:
- 第 51 题:经典问题,掌握「空间换时间」技巧;
- 第 529 题:寻找连通分量。DFS 和 BFS 均可。
第 13 章 动态规划(上)
动态规划的两个重要思想:
- 穷举:动态规划没有为问题设计专门的算法,它考虑了完成一件事情所有的情况;
- 空间换时间:记住了每一步求解的结果。
动态规划的两个思考方向:
- 「自顶向下」记忆化递归:
- 「自底向上」递推。
可以使用动态规划的解决问题需要具备的三个条件:
- 重复子问题:在计算的过程中,有一些问题会重复计算,必须记住结果。没有重复子问题的话,可以「分而治之」求解;
- 最优子结构:广义上说是「大规模问题的解与小规模问题的解的关系」,不一定需要在求最优解的场景下;
- 无后效性:特别重要,无后效性是设计状态非常重要的思考角度。「无后效性」即当前阶段一旦计算出结果,后面阶段的计算不会修改前面阶段计算出的状态值。整个求解的过程构成「有向无环图」。
动态规划的两个重要概念:
- 状态:记录了解决问题到了哪一步,通常用若干个变量表示;
- 状态转移方程:表达了大规模问题的解与小规模问题的解的关系。
问题分类参考:
说明:下面给出的典型问题还会添加(2020 年 12 月 2 日)。
一、入门问题
了解「自顶向下」记忆化递归与「自底向上」递推两种动态规划的方式。
题号 | 链接 | 题解 |
---|---|---|
509 | 斐波那契数(简单) |
- 第 509 题:斐波拉契数列递归做一定要加缓存,记忆化递归。
二、重复子问题
这部分需要用到「分步计数乘法原理」、「分类计数加法原理」。
题号 | 链接 | 题解 |
---|---|---|
70 | 爬楼梯(简单) | CSDN |
91 | 解码方法(中等) | 文字题解 |
《剑》46 | 把数字翻译成字符串(中等) | 视频题解 |
第 70 题:和斐波拉契数是同一道问题。计数类问题会用到分类计数原理、分步计数原理。
三、最优子结构
题号 | 链接 | 题解 |
---|---|---|
279 | 完全平方数(中等) | |
322 | 零钱兑换(中等) | 文字题解 |
343 | 整数拆分(中等) | 文字题解 |
377 | 组合总和 Ⅳ(中等) | 动态规划 |
说明:
第 377 题注意甄别不是背包问题。
四、无后效性
序号 | 链接 | 题解 | |
---|---|---|---|
198 | 打家劫舍(简单) | 文字题解 | |
120 | 三角形最小路径和(中等) | ||
62 | 不同路径(中等) | ||
63 | 不同路径 II(中等) | ||
64 | 最小路径和(中等) |
练习:
题号 | 链接 | 题解 |
---|---|---|
121 | 买卖股票的最佳时机(简单) | 暴力枚举 + 动态规划 + 差分思想、CSDN |
122 | 买卖股票的最佳时机 II(简单) | 暴力搜索 + 贪心算法 + 动态规划、CSDN |
123 | 买卖股票的最佳时机 III(困难) | 动态规划、CSDN |
188 | 188. 买卖股票的最佳时机 IV(困难) | 动态规划 |
309 | 最佳买卖股票时机含冷冻期(中等) | 动态规划 |
714 | 买卖股票的最佳时机含手续费(中等) | 动态规划 |
以下是一些「动态规划」经典问题。因为这些问题很重要,所以单独作为一个分类。
五、最大子段和
题号 | 链接 | 题解 |
---|---|---|
53 | 最大子序和(中等) | 文字题解、CSDN |
练习:
题号 | 链接 | 题解 |
---|---|---|
152 | 乘积最大子数组(中等) | 动态规划(理解无后效性) |
六、最长上升子序列
题号 | 链接 | 题解 |
---|---|---|
300 | 最长上升子序列(中等) | 动态规划 (包含O (N log N) 解法的状态定义以及解释) |
说明:第 300 题是非常经典的动态规划问题。$O(N \log N)$ 的解法,针对问题本身的特点进行状态定义,并证明状态数组是有序数组,降低了时间复杂度。
练习:
题号 | 链接 | 题解 |
---|---|---|
354 | 俄罗斯套娃信封问题 | 文字题解 |
646 | 最长数对链(中等) |
七、最长公共子串
题号 | 链接 | 题解 |
---|---|---|
1143 | 最长公共子序列(中等) | 文字题解 |
72 | 编辑距离(困难) | 文字题解、CDSN |
10 | 正则表达式匹配(困难) |
八、区间 DP 与划分型 DP
区间 DP:
题号 | 链接 | 题解 |
---|---|---|
5 | 最长回文子串(中等) | 文字题解 |
312 | 戳气球(困难) |
划分型 DP:
题号 | 链接 | 题解 |
---|---|---|
410 | 分割数组的最大值(困难) | 文字题解 |
九、树形 DP
题号 | 链接 | 题解 |
---|---|---|
337 | 打家劫舍 III(中等) | 文字题解 |
124 | 二叉树中的最大路径和(困难) |
第 14 章 动态规划(下)
一、背包问题
背包九讲:https://github.com/tianyicui/pack
题目序号 | 题解 | 知识点 |
---|---|---|
416. 分割等和子集 | 动态规划(0-1 背包问题) | 很重要的动态规划模型,必须掌握 |
518. 零钱兑换 II | 动态规划(套用完全背包问题模型) | |
322. 零钱兑换(中等) | 动态规划、使用「完全背包」问题思路、图的广度优先遍历 | |
494. 目标和 | 0-1 背包问题 | |
474. 一和零 | 动态规划(转换为 0-1 背包问题) |
(会补充「博弈类型 DP」、「状态压缩 DP」、「数位 DP」等。)
其它问题
题号 | 链接 | 题解 |
---|---|---|
746 | 使用最小花费爬楼梯(简单) | 文字题解 |
887 | 鸡蛋掉落(困难) | 动态规划(只解释官方题解方法一)(Java) |
32 | 最长有效括号(困难) | CSDN |
第 15 章 贪心算法
题号 | 链接 | 题解 |
---|---|---|
12 | 整数转罗马数字(中等) | 贪心算法(Java) |
452 | 用最少数量的箭引爆气球(中等) | |
455 | 分发饼干(中等) | |
122 | 买卖股票的最佳时机 II(简单) | |
56 | 合并区间(中等) | 贪心算法(Java) |
45 | 跳跃游戏 II(困难) | |
55 | 跳跃游戏(中等) | |
376 | 摆动序列(中等) |
第 17 章 哈希表
题号 | 链接 | 题解 |
---|---|---|
1 | 两数之和(简单) | 【视频讲解】 |
36 | 有效的数独(中等) | 哈希表(布尔数组、位运算) |
49 | 字母异位词分组(中等) | 自定义字符串的哈希规则,使用质数作为乘法因子(Java) |
202 | 快乐数(简单) | |
217 | 存在重复元素(简单) | |
219 | 存在重复元素 II(简单) | |
454 | 四数相加 II(中等) |
第 18 章 前缀和与哈希表
题号 | 链接 | 题解 |
---|---|---|
560 | 和为K的子数组(中等) | 暴力解法、前缀和、前缀和优化(Java) |
1248 | 统计「优美子数组」(中等) | |
974 | 和可被 K 整除的子数组(中等) |
第 19 章 广度优先遍历
题号 | 链接 | 题解 |
---|---|---|
剑 13 | 机器人的运动范围(中等) | 深度优先遍历、广度优先遍历 |
207 | 课程表(中等) | 拓扑排序、深度优先遍历 |
210 | 课程表 II(中等) | 拓扑排序(广度优先遍历) + 深度优先遍历(Java、Python) |
993 | 二叉树的堂兄弟节点(中等) | 深度优先遍历、广度优先遍历 |
690 | 员工的重要性(简单) | 深度优先遍历、广度优先遍历(Java、Python) |
1306 | 跳跃游戏 III(中等) | 广度优先遍历 |
365 | 水壶问题(中等) | 图的广度优先遍历(Java) |
127 | 单词接龙(中等) | 广度优先遍历、双向广度优先遍历(Java、Python) |
126 | 单词接龙 II(困难) | 单双向广度优先遍历 + 回溯算法(Java、Python) |
树的广度优先遍历的一些问题、LeetBook 里的一些问题。
第 20 章 图论算法(最小生成树)
第 21 章 图论算法(单源最短路径)
第 22 章 分治算法
分治思想(分而治之)把一个规模较大的问题拆分成为若干个规模较小的相同类型的子问题,然后对这些子问题递归求解,等待每一个子问题完成以后,再得到原问题的解。
分治算法可以并行执行,但是在基础算法领域,分治算法是以 深度优先遍历 的方式执行的。
应用分治思想的典型算法:归并排序、快速排序。
分治思想的典型问题:「剑指 Offer 第 51 题」:《剑指 Offer》 51. 数组中的逆序对(视频讲解)。
题号 | 链接 | 题解 |
---|---|---|
50 | Pow(x, n) | 文字题解 |
其它典型问题(待添加)
题目 | 题解 | 知识点 |
---|---|---|
66. 加一(简单) | ||
189. 旋转数组 | 记住这个旋转三次的操作。 | |
8. 字符串转换整数 (atoi) | 尽量不使用库函数、一次遍历(Java) |
还会继续更新,欢迎朋友们多提宝贵意见!