Skip to content

Latest commit

 

History

History
855 lines (608 loc) · 83.1 KB

README.md

File metadata and controls

855 lines (608 loc) · 83.1 KB
Raw

LeetCode-Solutions-in-Good-Style

说明：由于个人时间和精力的关系，下面给出的问题列表不太全，我和绝大多数同学一样，边学习边总结，我会在以后的时间添加一些典型的问题，争取做更多的分享，感谢大家的支持。

大家好，这里是一个《算法与数据结构》的简易入门级教程，适用于零基础和转行同学。

  • 特别感谢 @AbbyDeng 同学的更名建议；

  • 本项目是我在学习《算法与数据结构》的时候，在 LeetCode（力扣） 上做的练习，目前主要提供 Java 语言，Python 语言的代码在 这里（不齐全）；

  • 适用于准备算法面试和学习「算法与数据结构」入门，不适合于准备算法竞赛；

  • 所有的代码都通过 LeetCode（力扣） 在线测评系统检测；

  • 建议安装 Octotree 插件，以获得最佳的阅读体验。

Octotree 插件

可以叫我 weiwei，在我力所能及且时间允许的情况下，我会尽可能回答我知道的问题。如果有不能及时回复的问题，可能是因为我没有看到站内通知，可以发邮件给我 [email protected] 。

我的个人网站和算法学习笔记。

讲解如有错误，欢迎指正！

微信群与 QQ 群

如果需要一起刷题的朋友，可以加入微信群和 QQ 群。

微信群 QQ 群
每日一题打卡活动和加入微信群可以点 这里 。 群号：812791932

感谢负雪明烛和二哥组织建群。

我的 LeetBook

这里给自己做一个宣传，我最近在「力扣」上推出了自己的 LeetBook：零起步学算法（原名《使用「力扣」学习算法与数据结构》），主要面向 转行 、零基础 的朋友，讲解算法与数据结构的基础知识。

说明：

  • 该 LeetBook 的前两章（ 时间复杂度、二分查找）是免费阅读的，后面的章节 需要付费 阅读，非会员价 99 元，会员价 69 元，您当前看到的主页目录与 LeetBook 是一样的，只有多出来的部分，不会更少；

  • LeetBook 的课程标题、例题、练习、讨论区、配套代码仓库（就是您当前看到的这个仓库）都是完全公开的，如果 LeetBook 里设计的内容（包括练习）您已经掌握，就不太建议购买；

  • 投入精力与平时写题解是一样的，只不过 LeetBook 在制作图表上会更细致一点。付费内容是：制作教程的时间精力付出、「力扣」的工作人员和高手参与制作和审核，阅读体验会更好一些。不排除平时写的题解知识点比 LeetBook 还要多；

  • 中、高阶用户请谨慎购买；

  • 可以在「力扣」站内或者是我的其他社交账号向我咨询课程内容，也可以向本仓库提 issue。不管是否购买课程，我都会尽量回答我所知道的问题（时间允许，能力范围之内）。感谢大家一直以来，一如既往对我的支持。有建议和意见也欢迎大家与我交流；

  • 我所讲解的知识在我曾经向大家推荐的书籍，我写的博客、题解和笔记里都有，已经发布的题解、博客、笔记都会一直共享，并且只要我有时间和精力，我还会坚持做分享和答疑；

  • 很感谢「力扣」给我机会做课程的机会，帮助我完成一个小小心愿。

使用「力扣」学习算法与数据结构

「力扣」分类以及题解目录（按照 LeetBook 的章节编排，第 16 章以后为目前 LeetBook 不包含的章节）

说明：题目分类与我的 LeetBook 章节对应。

第 1 章 时间复杂度

这部分内容介绍了 时间复杂度 这个概念，可以收看 【视频讲解】 ，完全免费。 这一章节没有练习。

第 2 章 二分查找

题型一：二分求下标

  • 重点问题
题号 链接 题解
704 二分查找（简单）
35 搜索插入位置（简单） 【视频讲解】、文字题解
34 在排序数组中查找元素的第一个和最后一个位置（简单） 【视频讲解】、文字题解
1095 山脉数组中查找目标值（中等） 【视频讲解】、文字题解
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 去除重复字母（困难） 文字题解

说明：

练习：

序号 题目 题解
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 章 动态规划（下）

一、背包问题

image.png

背包九讲：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) 文字题解

我录制的视频题解

树状数组、线段树、背包问题、并查集、第 128 题

题目 知识点
用「排除法」（减治思想）写二分查找问题 二分查找
「力扣」第 35 题：搜索插入位置 二分查找
「力扣」第 34 题：在排序数组中查找元素的第一个和最后一个位置 二分查找
「力扣」第 1095 题：山脉数组中查找目标值 二分查找
「力扣」第 4 题：寻找两个正序数组的中位数 二分查找
「力扣」第 75 题：颜色分类 循环不变量、快排
《剑指 Offer》 51. 数组中的逆序对 分治算法
「力扣」第 1 题：两数之和 哈希表
「力扣」第 41 题：缺失的第一个正数 原地哈希
「力扣」第 76 题：最小覆盖子串 滑动窗口
「力扣」第 84 题：柱状图中最大的矩形 栈（单调栈）
「力扣」第 105 题：从前序与中序遍历序列构造二叉树 树、递归
「力扣」第 990 题：等式方程的可满足性 并查集
「力扣」第 127 题：单词接龙 单双向 BFS
「力扣」第 46 题：全排列 回溯算法
「力扣」第 47 题：全排列 II 回溯算法
「力扣」第 78 题：子集 回溯算法
「力扣」第 90 题：子集 II 回溯算法
「力扣」第 5 题：最长回文子串 动态规划
《剑指 Offer》46. 把数字翻译成字符串 动态规划
「力扣」第 416 题：分割等和子集 动态规划

其它典型问题（待添加）

题目 题解 知识点
66. 加一（简单）
189. 旋转数组 记住这个旋转三次的操作。
8. 字符串转换整数 (atoi) 尽量不使用库函数、一次遍历（Java）