# leetcode-cpp **Repository Path**: oweni/leetcode-cpp ## Basic Information - **Project Name**: leetcode-cpp - **Description**: 基于Cpp语言的LeetCode刷题代码 - **Primary Language**: C++ - **License**: Not specified - **Default Branch**: master - **Homepage**: None - **GVP Project**: No ## Statistics - **Stars**: 0 - **Forks**: 1 - **Created**: 2022-03-14 - **Last Updated**: 2022-05-25 ## Categories & Tags **Categories**: Uncategorized **Tags**: None ## README # LeetCode 代码仓库 本仓库中保存了LeetCode刷题过程中的代码，主要按照**数据结构、算法思想**两大类对题目进行分类记录。 ## Part 0 亮点题目记录 ### 数据结构 #### 1.1 数组 - 240 - 287 - 378 - 647：**Manacher** 算法，在线性时间内求解最长回文子串 - 667 #### 1.2 链表 - 160 #### 1.3 栈和队列 - 155：差值代替数字保存在栈中，以节省空间 - 225：队列实现栈 - 232：栈实现队列 - 739：单调栈 #### 1.4 树 - 94：用迭代的方式实现中序遍历 - 105：从前序与中序遍历序列构造二叉树 - 124：二叉树中的最大路径和 - 144：用迭代的方式实现前序遍历 - 145：用迭代的方式实现后序遍历 - 208：前缀树的定义和实现 - 236：二叉树的最近公共祖先 - 437：前缀和 - 572：树哈希 - 687 #### 1.5 图 ### 算法思想 动态规划 - 1277 ## Part 1 数据结构 ### 1.1 数组 #### 1 两数之和（Easy） **Completion Time: 2021.7.19** 本题目标是从数组中找出两个数，要求这两个数之和为给定的结果。 首先，可以使用**暴力法**求解。因为本题对运行时间的要求不高，所以可以对原数组进行双重遍历，寻找相加符合要求的两个数。该方法时间复杂度为 $O(n^{2})$。 第二，为了节约运行时间，可以使用**静态哈希表**的方法。遍历原数组，以原数组中元素的值为 key，以下标为 value 建立哈希表，从而只要遍历一次数组，在哈希表中查询是否存在以剩余数值为 key 的项即可。该方法时间复杂度为 $O(n)$，以空间换时间，所以会占用较大空间。 #### 5* 最长回文子串（Medium） - **Completion Time: 2022.1.14** - 给你一个字符串 `s`，找到 `s` 中最长的回文子串。 - **动态规划** - **中心扩展** - **Manacher 算法** #### 9 回文数（Easy） - **Completion Time: 2022.1.3** - 本题目标是判断一个数字是否为回文数。 - 由于题目要求不能把数字拆分为字符数组进行判断，因此也不能使用诸如队列和栈之类的数据结构。 - 这里我们考虑将原数字翻转过来，但是这样可能会造成反转后的整数溢出的问题，处理起来不是很方便。 - 因此我们考虑只反转其中一半的数字，不断将给反转后的数字乘上 `10` 再加上原始数字的个位，然后原始数字除以 `10`，知道反转的数字大于原始数字，就已经完成了反转一半数字的任务。然后根据长度为奇数和偶数分别判断即可。 - 该方法时间复杂度为 $O(log(n))$，空间复杂度为 $O(1)$。 #### 13 罗马数字转整数（Easy） - **Completion Time: 2022.1.24** - 本题的目标是给定一个罗马数字，将其转换成整数。 - 根据罗马数字的规律我们可以得到如下两种情况： - 通常情况下，罗马数字中小的数字在大的数字的右边。若输入的字符串满足该情况，那么可以将每个字符视作一个单独的值，累加每个字符对应的数值即可。 - 若存在小的数字在大的数字的左边的情况，根据规则需要减去小的数字。对于这种情况，我们也可以将每个字符视作一个单独的值，若一个数字右侧的数字比它大，则将该数字的符号取反。 - 该方法时间复杂度为 $O(n)$，空间复杂度为 $O(1)$。 #### 14 最长公共前缀（Easy） - **Completion Time: 2022.1.24** - 编写一个函数来查找字符串数组中的最长公共前缀。 如果不存在公共前缀，返回空字符串 `""`。 - 方法一是横向扫描，依次遍历每个字符串，更新最长公共前缀。 - 另一种方法是纵向扫描。纵向扫描时，从前往后遍历所有字符串的每一列，比较相同列上的字符是否相同，如果相同则继续对下一列进行比较，如果不相同则当前列不再属于公共前缀，当前列之前的部分为最长公共前缀。 #### 26 删除有序数组中的重复项（Easy） - **Completion Time: 2022.2.2** - 给你一个有序数组 `nums` ，请你** 原地** 删除重复出现的元素，使每个元素 **只出现一次** ，返回删除后数组的新长度。 不要使用额外的数组空间，你必须在 **原地 修改输入数组 **并在使用 O(1) 额外空间的条件下完成。 - 本题可以使用快慢指针，用快指针遍历原数组，用慢指针记录数组中无重复元素的下标。 #### 27 移除元素（Easy） - **Completion Time: 2022.2.2** - 给你一个数组 `nums`* *和一个值 `val`，你需要 **原地** 移除所有数值等于 `val`* *的元素，并返回移除后数组的新长度。 不要使用额外的数组空间，你必须仅使用 `O(1)` 额外空间并 **原地 修改输入数组**。 元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。 - 本题类似于 `LeetCode 26`，不同的是删除的元素的特定值的元素。 #### 28 实现 strStr()（Easy） - **Completion Time: 2022.2.4** - 实现 [strStr()](https://baike.baidu.com/item/strstr/811469) 函数。 给你两个字符串 `haystack` 和 `needle` ，请你在 `haystack` 字符串中找出 `needle` 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 `-1` 。 **说明：** 当 `needle` 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。 对于本题而言，当 `needle` 是空字符串时我们应当返回 0 。这与 C 语言的 [strstr()](https://baike.baidu.com/item/strstr/811469) 以及 Java 的 [indexOf()](https://docs.oracle.com/javase/7/docs/api/java/lang/String.html#indexOf(java.lang.String)) 定义相符。 - 本题除了暴力匹配算法，还可以使用 KMP 算法，具体见如下链接：https://leetcode-cn.com/problems/implement-strstr/solution/shi-xian-strstr-by-leetcode-solution-ds6y/ #### 35 搜索插入位置（Easy） - **Completion Time: 2022.2.4** - 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 `O(log n)` 的算法。 - 本题类似于二分查找，需要返回对应的下标值。 #### 42* 接雨水（Hard） - **Completion Time: 2022.1.12** - 给定 `n` 个非负整数表示每个宽度为 `1` 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。 - 动态规划，双指针 - 单调栈 #### 48 旋转图像（Medium） - **Completion Time: 2022.1.15** - 给定一个 *n* × *n* 的二维矩阵 `matrix` 表示一个图像。请你将图像顺时针旋转 90 度。 你必须在**[ 原地](https://baike.baidu.com/item/原地算法)** 旋转图像，这意味着你需要直接修改输入的二维矩阵。**请不要** 使用另一个矩阵来旋转图像。 - 寻找数学规律，顺时针旋转=水平翻转+主对角线反转 #### 58 最后一个单词的长度（Easy） - **Completion Time: 2022.2.2** - 给你一个字符串 `s`，由若干单词组成，单词前后用一些空格字符隔开。返回字符串中最后一个单词的长度。 **单词** 是指仅由字母组成、不包含任何空格字符的最大子字符串。 - 小技巧：在原字符串最后添加一个空格 #### 66 加一（Easy） - **Completion Time: 2022.2.4** - 给定一个由 **整数** 组成的 **非空** 数组所表示的非负整数，在该数的基础上加一。 最高位数字存放在数组的首位， 数组中每个元素只存储**单个**数字。 你可以假设除了整数 0 之外，这个整数不会以零开头。 - 本题目标为一个大数加一，可以从低位依次向高位遍历，寻找一个可以进位，即非 9 的下标。特殊情况是每一位都是 9，需要在首位加入1，并向将每一位向后移动一位。 #### 67 二进制求和（Easy） - **Completion Time: 2022.2.4** - 给你两个二进制字符串，返回它们的和（用二进制表示）。 输入为 **非空** 字符串且只包含数字 `1` 和 `0`。 - 本题两个数字从低位至高位依次遍历，计算每一个的和，同时需要维护一个进位符号。 #### 88 合并两个有序数组（Easy） - **Completion Time: 2022.2.5** - 给你两个按 **非递减顺序** 排列的整数数组 `nums1` 和 `nums2`，另有两个整数 `m` 和 `n` ，分别表示 `nums1` 和 `nums2` 中的元素数目。 请你 **合并** `nums2` 到 `nums1` 中，使合并后的数组同样按 **非递减顺序** 排列。 **注意：**最终，合并后数组不应由函数返回，而是存储在数组 `nums1` 中。为了应对这种情况，`nums1` 的初始长度为 `m + n`，其中前 `m` 个元素表示应合并的元素，后 `n` 个元素为 `0` ，应忽略。`nums2` 的长度为 `n` 。 - 本题需要合并两个有序数组，并将最终的结果保存在第一个数组中，也就是说需要将第二个数组中的元素插入第一个数组中。如果从小到大插入元素，那么每插入一个元素就需要将其后的元素都依次向后移动一位。为了防止移动元素带来的复杂度，那么可以从大到小插入元素，遍历两个数组，选择较大值插入目标数组中。 #### 118 杨辉三角（Easy） - **Completion Time: 2022.2.20** - 给定一个非负整数 *`numRows`，*生成「杨辉三角」的前 *`numRows`* 行。 在「杨辉三角」中，每个数是它左上方和右上方的数的和。 #### 119 杨辉三角 II（Easy） - **Completion Time: 2022.2.20** - 给定一个非负索引 `rowIndex`，返回「杨辉三角」的第 `rowIndex` 行。 在「杨辉三角」中，每个数是它左上方和右上方的数的和。 #### 125 验证回文串（Easy） - **Completion Time: 2022.2.5** - 给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。 **说明：**本题中，我们将空字符串定义为有效的回文串。 - 本题可以定义一对左右指针，依次从字符串两端向内侧寻找字母或者数字进行比较，直至两个指针交汇即可。该方法的时间复杂度为 O(|s|)，其中 |s| 是字符串 s 的长度，空间复杂度为 O(1)。 #### 128 最长连续序列（Medium） - **Completion Time: 2022.1.2** - 本题目标是在原数组中找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。 - 使用**哈希表**的思想，先遍历原数组，用一个集合记录出现过的数字。然后遍历集合中数字，记录从 `x` 开始依次递增都出现过的序列的最大长度。此处还有一个要点，就是如果 `x-1` 也出现在这个集合中，直接跳过该元素，因为从 `x-1` 开始的序列长度一定大于从 `x` 开始的序列长度。该方法时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。 #### 136 只出现一次的数字（Easy） - **Completion Time: 2022.2.5** - 给定一个**非空**整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。 **说明：** 你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？ - 异或 #### 205 同构字符串（Easy） - **Completion Time: 2022.1.3** - 本题要求是给定两个字符串 s 和 t，判断它们是否是同构的。如果 s 中的字符可以按某种映射关系替换得到 t ，那么这两个字符串是同构的。每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序。不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。 - 由题意可得，两个字符串中的字符是双映射关系，s 中的每个字符只能对应 t 中的一个字符，t 中的每个字符也只能对应 s 中的一个字符。因此可以准备两个映射表，分别记录 s 到 t 和 t 到 s 的映射关系。遍历原字符串，遇到第一次出现的字符就加入映射表；不是第一次出现则跟映射表中进行对比，出现不一致的时候就可以判定不是同构字符串。 - 该方法时间复杂度为 $O(n)$，其中 $n$ 为字符串的长度；空间复杂度为$O(S)$，其中 $S$ 为字符集大小。 #### 217 存在重复元素（Easy） - **Completion Time: 2022.1.2** - 本题目表示判断一个数组中是否存在重复元素。 - 第一种方法是对数组先排序，然后对比相邻数组是否有相同元素。该方法时间复杂度为 $O(nlog(n))$，空间复杂度为 $O(log(n))$。 - 第二种方法是使用哈希表，即 `Java` 中的 `Hashset` 实现，遍历数组判断如果集合中已经存在该元素。该方法时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。 #### 240* 搜索二维矩阵 II（Medium） **Completion Time: 2021.8.14** 本题目标是在一个矩阵中搜索一个目标值，该矩阵有如下特点：每行的元素从左到右升序排列，每列的元素从上到下升序排列。 本题非常巧妙，从矩阵右上角看，可以将原矩阵视作一棵二叉搜索树，即节点左侧的都是小于的该节点的分支，节点下方是大于该节点的分支。基于此，可以从矩阵右上方的节点开始，搜索目标值。该方法的时间复杂度为 $O(m+n)$，空间复杂度为 $O(1)$。 #### 242 有效的字母异位词（Easy） - **Completion Time: 2022.1.3** - 本题目标是判断两个字符串中是否所有字符出现次数相同。 - 其实可以将字符串看作元素是 `char` 的数组，因此将所有字符串相关的题目归纳于数组这个栏目中。 - 第一种方法是对字符串中的字符进行排序，然后依次对比每个位置的字符即可。该方法时间复杂度为 $O(nlog(n))$，空间复杂度为 $O(log(n))$。 - 第二种方法是**哈希表**的算法，即记录每个字符出现的次数，然后遍历每个字母对比次数即可。该方法时间复杂度为 $O(n)$，其中 $n$ 为字符串的长度；空间复杂度为$O(S)$，其中 $S$ 为字符集大小，本题中 $S=26$。 #### 283* 移动零（Easy） **Completion Time: 2021.8.14** 本题目标是将数组中的零元素移动至数组结尾。 本题可以使用快慢指针的方法，使用快指针遍历原数组中的非零元素，慢指针之前的数组为清除了零元素的数组。当快指针到达数组末尾时，慢指针之后的元素全部置零即可。该方法时间复杂度为 $O(n)$，空间复杂度为 $O(1)$。 #### 287* 寻找重复数（Medium） - **Completion Time: 2021.12.29** - 本题目标找出数组中重复的数，数组值在 [1, n] 之间，除此之外，本题还要求不能修改数组，也不能使用额外的空间。因此无法使用哈希表等算法。 - 本题的第一种方法是**二分查找法**。用 $cnt[i]$ 表示 $\textit{nums}$ 数组中小于等于 $i$ 的数有多少个。假设我们重复的数是 $\textit{target}$，那么 $[1,\textit{target}-1]$ 里的所有数满足 $\textit{cnt}[i]\le i$，$[terget,n]$ 里的所有数满足 $\textit{cnt}[i]>i$，具有单调性。 - 第二种方法是**双指针法**，也称为 Floyd 算法。这种方法重点是要将数组看作链表。此后难度主要是使用双指针法寻找环路的入口，即重复的数字。 - 对这个算法的思想不太理解的，可以参考这篇博客：[图解算法：确定单链表有环，如何找到环的入口和长度？_承香墨影的博客-CSDN博客_有环链表找环入口](https://blog.csdn.net/plokmju88/article/details/103675872) #### 378* 有序矩阵中第 K 小的元素（Medium） 本题目标正如题目名称所示，比较特殊的是该矩阵有如下特点：每行的元素从左到右升序排列，每列的元素从上到下升序排列。 本题可以使用最简单的暴力法，将有序矩阵转化为一个有序数组；也可以使用归并排序，将每一行视作一个有序数组，然后归并 n 个有序数组。 本题最好的办法是使用**二分查找法**，整个二维数组中 $matrix[0][0]$ 为最小值，$matrix[n−1][n−1]$ 为最大值，现在我们将其分别记作 `left` 和 `right`。此后我们根据二分查找的思想不断用 $(left+right)/2$ 更新 `mid ` 的值，然后统计原数组中不大于 `mid` 的元素数量： 如果数量不少于 `k`，那么说明最终答案不大于 `mid`； 如果数量少于 `k`，那么说明最终答案大于 `mid`。 该方法时间复杂度为 $O(nlog(r-l))$，空间复杂度为 $O(1)$。 第一种解法没有利用矩阵的性质，所以时间复杂度最差；第二种解法只利用了一部分性质（每一行是一个有序数列，而忽视了列之间的关系）；第三种解法则利用了全部性质，所以时间复杂度最佳。 #### 409 最长回文串 - **Completion Time: 2022.1.3** - 本题的目标是使用给定字符串中的字符，构造一个最长的回文串。 - 首先还是遍历原数组记录每个字母的出现次数，对于出现偶数次的字母，一定可以加入回文串中；对于出现奇数次的字母，可以取其中最大偶数次加入回文串中。最后，如果所有字母中有奇数次的字母，还可以取一个放到回文串的中间。 - 对于最后的放在中间的元素，还有一个判断的方法，就是判断由偶数次字母组成的字符串长度和原字符串长度是否相等，如果不是，则一定有一个字母可以放在中间。 - 该方法时间复杂度为 $O(n)$，其中 $n$ 为字符串的长度；空间复杂度为$O(S)$，其中 $S$ 为字符集大小，本题中 $S=52$。 #### 415 字符串相加（Easy） - **Completion Time: 2022.1.15** - 给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和并同样以字符串形式返回。 你不能使用任何內建的用于处理大整数的库（比如 BigInteger）， 也不能直接将输入的字符串转换为整数形式。 #### 485* 最大连续 1 的个数（Easy） **Completion Time: 2021.8.14** 本题目标是计算一个二进制数组中最长连续 1 的个数。 本体比较简单，遍历原数组，遇到 1 时就在增加计数器，遇到 0 时就重置当前计数器。当计数器大于最大值计数器时就更新最大值计数器。该方法时间复杂度为 $O(n)$，空间复杂度为 $O(1)$。 #### 565 数组嵌套（Medium） - **Completion Time: 2022.1.1** - 本题将数组的值作为索引，寻找一个数组中最大的环路。 - 主要思想是设置一个标记矩阵 `visited` 用来标记每个节点是否被访问过，每次从一个未经访问的结点开始按照节点索引依次访问，直至回到第一个点，记录该环路的长度，如果该长度大于已知的最大长度则记录。 - 该方法时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。 - 本体还有一个可以改进空间复杂度的小技巧，即不用定义新的 `visited` 矩阵，直接数组将访问过的元素值置为 `-1`。经过这种改进，时间复杂度为 $O(n)$，空间复杂度为 $O(1)$。 #### 566* 重塑矩阵（Easy） **Completion Time: 2021.8.14** 本题是实现了矩阵的 `reshape` 函数的功能，即重塑矩阵的行和列。 本题比较简单，新建一个矩阵，然后将元素一一映射到新矩阵即可。原矩阵 `mat` 的第 x 个元素对应的下标为 $(x/n,x\%n)$，而在新的重塑矩阵中对应的下标为 $(x/c,x\%c)$。该方法时间复杂度为 $O(rc)$，空间复杂度为 $O(1)$。 #### 594 最长和谐子序列（Easy） - **Completion Time: 2022.1.2** - 本题目目标是求一个数组中最长和谐子序列。 - 和谐数组是指一个数组里元素的最大值和最小值之间的差别正好是1。 - 数组的子序列是一个由数组派生出来的序列，它可以通过删除一些元素或不删除元素、且不改变其余元素的顺序而得到。 - 第一种方法是对数组先排序，然后计算相差为1的数字的出现次数。该方法时间复杂度为 $O(nlog(n))$，空间复杂度为 $O(1)$。 - 第二种方法是使用哈希表，遍历数组统计每个数字的出现次数，并用集合保存出现过的数字。然后遍历集合，计算相差为1的数字的出现次数之和的最大值。该方法时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。 #### 645 错误的集合（Easy） - **Completion Time: 2021.12.19** - 本题目标是从给定的数组中寻找1-n中丢失的数据已经重复的数据。 - 本题比较简单，可以使用哈希表或者集合然后远离原数组，依次记录每个数字出现的次数，为0即为丢失的数据，为2即为重复的数据。该方法时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。 - 本题还有一种偏数学的方法： - sum(nums) - sum(set(nums)) = 重复的数字 - (1 + len(nums)) * len(nums) // 2 - sum(set(nums)) = 丢失的数字 #### 647* 回文子串（Medium） - **Completion Time: 2022.1.3** - 本题的目标是求出给定字符串中 **回文子串** 的数目。 - 第一种方法是 **中心扩展** 的方法，即依次遍历原数组，枚举每一个回文中心，然后依次向外扩展直至两侧出现不同的数字。回文中心存在一个数字和两个数字两种情况，需要分别讨论。对于这一点还有一个小技巧，可以令回文中心为 $[l_{i},r_{i}]$，其中 $l_{i} = \lfloor \frac{i}{2} \rfloor$ ，$r_{i} = l_{i}+(i\ mod\ 2)$，这样只要从 0 到 2n-2 遍历 i，就可以得到所有可能的回文中心，通过这种方法把奇数长度和偶数长度的情况统一起来了。该方法时间复杂度为 $O(n^{2})$，空间复杂度为 $O(1)$。 - 第二种方法是 **Manacher** 算法，这是一种在线性时间内求解最长回文子串的算法。详细过程可以参考 [回文子串 - 回文子串 - 力扣（LeetCode） (leetcode-cn.com)](https://leetcode-cn.com/problems/palindromic-substrings/solution/hui-wen-zi-chuan-by-leetcode-solution/)。该方法的时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。 #### 667* 优美的排列 II（Medium） - **Completion Time: 2022.1.1** - 本题目标是构造一个数组，使数组元素为 1~n 的整数，且相邻元素的不同的差值的个数为 k。 - 本题是一个偏向找规律的题目，思路是将目标数组分为两部分。 - 公差为1的等差数列，该数列中相邻元素的差值相同，均为1。 - 最大值和最小值交错出现的交错数列，若该数列一共有 n 个元素，则该数列中相邻元素差值为 n-1~1。 - 该方法的时间复杂度为 $O(n)$，如果考虑保存结果的空间，则空间复杂度为 $O(n)$。 #### 696 计数二进制子串（Easy） - **Completion Time: 2022.1.3** - 给定一个字符串 `s`，统计并返回具有相同数量 `0` 和 `1` 的非空（连续）子字符串的数量，并且这些子字符串中的所有 `0` 和所有 `1` 都是成组连续的。 - 首先遍历原数组，统计连续的 0 或 1出现的次数，并将其记录为一个 `counts` 数组，该数组中两个相邻的数一定代表的是两种不同的字符。假设 `counts` 数组中两个相邻的数字为 `u` 和 `v`，它们对应着 u 个 0 和 v 个 1，或者 u 个 1 和 v 个 0。它们能组成的满足条件的子串数目为 $\min(u, v)$，即一对相邻的数字对答案的贡献。我们只要遍历所有相邻的数对，求它们的贡献总和，即可得到答案。该方法的时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。 - 对于某一个位置 i，其实我们只关心 i−1 位置的 counts 值是多少，所以可以用一个 last 变量来维护当前位置的前一个位置，这样可以省去一个 counts 数组的空间。该方法的时间复杂度为 $O(n)$，空间复杂度为 $O(1)$。 #### 697 数组的度（Easy） - **Completion Time: 2022.1.1** - 本题的目标是找到一个与原数组 **度相同的最短连续子数组**，其中数组的 **度** 的定义是指数组里任一元素出现频数的最大值。 - 可以使用 **哈希表** ，思路是遍历原数组记录每个数字出现的频数以及开始和结束的时间，在出现频数的最多的数字中首尾距离最短的就是目标数组。 - 该方法的时间复杂度为和空间复杂度均为 $O(n)$。 #### 766 托普利茨矩阵（Easy） - **Completion Time: 2022.1.1** - 本题的目标判断是否为 **托普利茨矩阵**，该矩阵的定义为：**当且仅当矩阵中每个元素都与其左上角相邻的元素（如果存在）相等** 时，该矩阵为托普利茨矩阵。 - 本题比较简单，就是遍历整个矩阵，将每个元素与其左上角的元素进行对比，如果全都一致则为托普利茨矩阵。 - 该方法的时间复杂度为 $O(mn)$，其中 $m$ 为矩阵的行数，$n$ 为矩阵的列数，矩阵中每个元素至多被访问两次；空间复杂度为 $O(1)$。 #### 769 最多能完成排序的块（Medium） - **Completion Time: 2022.1.1** - 将共有n个元素的 0~n-1 数组分割成几个“块”，并将这些块分别进行排序之后再连接起来，使得连接的结果和按升序排序后的原数组相同。求最多能将数组分成多少块？ - 该题主要是要发现规律：如果当前下表 i(含) 之前的最大值为i，则说明可以分块；反之说明前半部分有大于i的元素，后半部分有小于i的元素，比不可以分块。 - 该方法的时间复杂度为 $O(n)$，空间复杂度为 $O(1)$。 ### 1.2 链表 #### 2 两数相加（Medium） **Completion Time: 2021.7.20** 本题目标是将以链表形式输入的两个数字相加，并同样以链表的形式输出。 本题总体而言难度是不高的，因为输入的链表节点已经按照数字从低位到高位进行排序了，也就是说两个链表中的相同序号的节点在两个数字中对应的位数是相同的。因此解决本题，只需要定义两个指针分别指向两个输入的链表，然后对应位置的节点 value 相加，以此建立一个新的链表并输出即可。该方法的时间复杂度为 $O(\max(m,n))$。 #### 19* 删除链表的倒数第 N 个结点（Medium） **Completion Time: 2021.8.12** 本题目标是删除链表的倒数第 n 个节点。 本题可以使用**快慢指针**的方法，让快指针先走 n 个节点，然后让快慢指针同步移动。当快指针到达链表结尾时，满指针指向的下一节点就是要删除的节点。该方法时间复杂度为 $O(n)$，空间复杂度为 $O(1)$。 #### 21* 合并两个有序链表（Easy） **Completion Time: 2021.7.30** 本题目标是将两个原本就正序排列的列表进行合并。 首先，本题可以使用**迭代法**。设置两个指针分别指向初始两个链表的开头，然后依次开始遍历，将两个指针中值较小的节点插入最终链表中。该方法时间复杂度为 $O(m+n)$，空间复杂度为 $O(1)$。 #### 24* 两两交换链表中的节点（Medium） **Completion Time: 2021.8.12** 本题目标是将一个链表中的节点两两交换。 本题主要就是遍历节点，如果当前节点和下一节点都不是 `nullptr` 就需要交换这两个节点。由于本题要求不能只修改节点的值，所以需要修改各个节点的后驱指针即可。该方法时间复杂度为 $O(n)$，空间复杂度为 $O(1)$。 #### 82 删除排序链表中的重复元素 II（Medium） - **Completion Time: 2022.1.14** - 存在一个按升序排列的链表，给你这个链表的头节点 `head` ，请你删除链表中所有存在数字重复情况的节点，只保留原始链表中 **没有重复出现** 的数字。 返回同样按升序排列的结果链表。 #### 83 删除排序链表中的重复元素（Easy） **Completion Time: 2021.8.12** 本题目标是取出一个链表中值重复的节点。 因为本题初始条件给出了原始链表是升序的，所以比较简单，遍历该链表，如果出现当前节点与下一节点的值相同，则跳过下一节点，反之则将当前节点移动到下一节点即可。该方法的时间复杂度为 $O(n)$，空间复杂度为 $O(1)$。 #### 138 复制带随机指针的链表（Medium） - **Completion Time: 2022.1.18** - 给你一个长度为 `n` 的链表，每个节点包含一个额外增加的随机指针 `random` ，该指针可以指向链表中的任何节点或空节点。 构造这个链表的 **[深拷贝](https://baike.baidu.com/item/深拷贝/22785317?fr=aladdin)**。 深拷贝应该正好由 `n` 个 **全新** 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 `next` 指针和 `random` 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。**复制链表中的指针都不应指向原链表中的节点** 。 例如，如果原链表中有 `X` 和 `Y` 两个节点，其中 `X.random --> Y` 。那么在复制链表中对应的两个节点 `x` 和 `y` ，同样有 `x.random --> y` 。 返回复制链表的头节点。 用一个由 `n` 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 `[val, random_index]` 表示： - `val`：一个表示 `Node.val` 的整数。 - `random_index`：随机指针指向的节点索引（范围从 `0` 到 `n-1`）；如果不指向任何节点，则为 `null` 。 你的代码 **只** 接受原链表的头节点 `head` 作为传入参数。 #### 141 环形链表（Easy） - **Completion Time: 2022.1.15** - 给你一个链表的头节点 `head` ，判断链表中是否有环。 如果链表中有某个节点，可以通过连续跟踪 `next` 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 `pos` 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 `pos` 是 `-1`，则在该链表中没有环。**注意：`pos` 不作为参数进行传递**，仅仅是为了标识链表的实际情况。 如果链表中存在环，则返回 `true` 。 否则，返回 `false` 。 - 第一种方法是哈希表 - 第二种方法是快慢指针 #### 148 排序链表（Medium） - **Completion Time: 2022.1.18** - 给你链表的头结点 `head` ，请将其按 **升序** 排列并返回 **排序后的链表** 。 - 类似数组中的归并排序，用快慢指针寻找链表中点 #### 160* 相交链表（Easy） **Completion Time: 2021.7.29** 本题目标是在两个链表中寻找开始相交的第一个节点，不存在则输出 `nullptr`。 首先，本题目标是寻找两个链表中第一个相同的节点，可以自然地联想到先将第一个链表中的节点保存到**哈希集合**中，然后遍历第二个链表并查找哈希集合。该方法的时间复杂度为 $O(m+n)$，空间复杂度为 $O(m)$。 第二，本题还可以使用**双指针**的方法来降低时间和空间复杂度，该方法也是本题的特色。这两个链表的交点距离起点的距离是不一定的，但是距离终点的距离是一定的（若不存在交点则距离终点距离为0）。所以可以将一个链表最后的 `nullptr` 连到另一个链表的开端，这样做的目的是从两个链表的起点开始到这个节点的距离相同。因为，两个链表通过这种方式连接之后，起点到交点、交点到终点的距离都是相同的。这样，只要设置两个指针，以不同的起点遍历这个拼接成的链表，途中相同的节点就是两个链表的交点。该方法代码并不复杂，但是第一次比较难想到这个方法。该方法的时间复杂度为 $O(m+n)$，空间复杂度为 $O(1)$。 #### 206* 反转链表（Easy） **Completion Time: 2021.7.30** 本题目标是将输入的链表进行反转并输出。难度并不大，主要是了解一下反转链表的过程。 首先，本题可以用**迭代法**，结合链表的结构并不难完成本题的目标。在遍历链表的过程中，把每个结点的 `next` 修改为前驱节点即可。最后返回原链表中的尾节点即可。该方法的时间复杂度为 $O(n)$，空间复杂度为 $O(1)$。 第二，本体还可以使用**递归法**，递归的终止条件为到达最后一个节点即 `node.next == nullptr`，然后执行指令 `node.next.next = node.next` 即可。该方法的时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。 #### 234* 回文链表（Easy） **Completion Time: 2021.8.13** 本题目表示要判断一个链表是否为回文链表。 首先本题可以在快慢指针的基础上，将链表中左侧的数据全都保存下来，然后继续移动慢指针，将慢指针的数据与保存的数据进行比较。该方法的时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。 第二，题目中的进阶要求是空间复杂度为 $O(1)$，因此我们不能使用数据结构来保存相应的数据，因此需要对链表的结构进行一定的修改。在使用快慢指针的基础上，在完成第一遍遍历后，将后半段链表进行翻转，然后从两端开始遍历并比较相应的数字。该方法的时间复杂度为 $O(n)$，空间复杂度为 $O(1)$。 #### 237* 删除链表中的节点（Easy） - **Completion Time: 2022.2.5** - 请编写一个函数，用于 **删除单链表中某个特定节点** 。在设计函数时需要注意，你无法访问链表的头节点 `head` ，只能直接访问 **要被删除的节点** 。 题目数据保证需要删除的节点 **不是末尾节点** 。 - 本题不涉及太多的算法，主要是一种思路，在不知道链表头节点的情况下删除一个节点，常规思路下困难在于无法修改该节点的前驱节点，也就难以完成该任务。本题中，将该节点的值保存为子节点的值，然后删除子节点，进而完成了该任务。 #### 328* 奇偶链表（Medium） **Completion Time: 2021.8.13** 本题目标是修改原链表中的顺序，奇数节点在前，偶数节点在后。 本题只要依次遍历原链表，然后将奇数节点和偶数节点分别串成一个链表，最后将奇数链表的最后一个指针指向偶数链表的开始即可。该方法的时间复杂度为 $O(n)$，空间复杂度为 $O(1)$。 #### 445* 两数相加 II（Medium） **Completion Time: 2021.8.13** 本题是第二题的升级版，数字高位位于链表的开始位置。 由于根据题目要求最好不要修改输入链表，即先将输入链表进行节点反转。因此我们可以使用 `Stack` 栈来顺序保存链表中的数据，然后利用栈先进后出的原则将从高位开始存储的链表中的数据从低位开始输出。该方法的时间复杂度为 $O(\max(m, n))$，空间复杂度为 $O(m + n)$。 #### 725* 分隔链表（Medium） **Completion Time: 2021.8.13** 本题的目标是将输入的链表分割成 k 个连续部分，要保证各个部分的长度尽量一致。 本体需要先对初始链表进行遍历，获取初始链表的长度。进而计算得到分割后各段链表的长度。然后从头开始，将每段最后的节点的 `next` 指向 `nullptr` 即可。该方法的时间复杂度为 $O(n+k)$，空间复杂度为 $O(k)$。 ### 1.3 栈和队列 #### 20 有效的括号（Easy） - **Completion Time: 2022.1.2** - 本题的要求是给定一个只包括 `'('`，`')'`，`'{'`，`'}'`，`'['`，`']'` 的字符串 `s` ，判断字符串是否有效。 - 本题比较简单，依次遍历字符串中的字符，遇到左半部分符号入栈，遇到右半部分则检查栈顶元素是否匹配即可。该方法的时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。 - 如果单纯就这题目的角度考虑，还可以考虑 `ASCII` 码中差值的问题，但是效率并不会提升太多，而且可读性一般，仅作参考。 #### 155* 最小栈（Easy） - **Completion Time: 2022.1.2** - 本题要求在实现栈的基本功能的基础上，能方便的查询当前栈中的最小值。 - 第一种方法是定义一个**辅助栈**，与数据栈保持同步，每次操作都会相应地存入或取出最小值。该方法的时间复杂度为 $O(1)$，空间复杂度为 $O(n)$。 - 另一个方法是在栈中保存差值，即每个元素保存的是相对于栈最小值的变化量，即 `-1` 表示存入该元素后栈的最小值减小了1，`1` 表示该元素比栈的最小值大1。在每次存入和取出操作中，不断更新最小值。该方法的时间复杂度为 $O(1)$，空间复杂度为 $O(1)$。 #### 225* 用队列实现栈（Easy） - **Completion Time: 2022.1.2** - 本题要求正如题目所说，用两个队列来模拟栈的操作，主要要求实现四个函数`push()`、`pop()`、`top()`、`empty()`。 - 不同于第232题中的将第一个栈中元素依次取出然后存入第二个栈中，由于两个队列都是 `FIFO` 的，所有从第一个队列中依次取出然后依次存入第二个队列无法改变元素的顺序。 - 其实本题只需要一个队列就可以实现： - `push` 操作要求新存入的数字保存在队列头部 - `pop` 操作要取的是队列头部的元素 - `top` 操作要查询的是队列头部的元素 - `empty` 操作要查询该队列是否为空 - 因此重点在于如何使新存入的元素保存在队列头部，我们可以**在队列尾部存入新数字后将原有的数字依次取出并再次存入该队列**。 - 该方法的时间复杂度为 $O(1)$，空间复杂度为 $O(1)$。 #### 232* 用栈实现队列（Easy） - **Completion Time: 2022.1.2** - 本题要求正如题目所说，用两个栈来模拟队列的操作，主要要求实现四个函数`push()`、`pop()`、`top()`、`empty()`。 - 由于队列是 `FIFO` 的，而栈是 `LIFO` 的，假如我们先只考虑用一个栈模拟队列的情况： - `push` 操作无所谓，只需要保证结构的中的数字是按照输入顺序排序的即可 - `pop` 操作要取的是栈底的元素 - `top` 操作要查询的是栈底的元素 - `empty` 操作要查询该栈是否为空 - 也就是说主要问题集中在如何取 `栈低的元素`，此时由于我们有第二个栈，考虑一个操作——**将 stack1 的元素依次取出并推入 stack2**。那么原来 `stack1` 中的栈底元素就成了 `stack2` 中的栈顶元素，此时不管是 `pop` 还是 `top` 就可以很方便的实现了。整体来说，模拟的队列就是 `stack1` 的栈顶至栈底，然后连接上 `stack2` 的栈底至栈顶。 - 该方法的时间复杂度为入栈 $O(n)$，其余 $O(1)$；空间复杂度为 $O(n)$。 #### 503 下一个更大元素 II（Medium） - **Completion Time: 2022.1.2** - 本题要求求一个循环数组（最后一个元素的下一个元素是数组的第一个元素）中每个元素的下一个更大元素。 - 主要思路同 `739` 单调栈，唯一的不同是循环数组，将数组的前 `n-1` 个元素再重复一遍接在原数组之后。其余操作相同。 - 该方法的时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。 #### 739* 每日温度（Medium） - **Completion Time: 2022.1.2** - 本题目要求根据每日气温列表 `temperatures` ，请计算在每一天需要等几天才会有更高的温度。如果气温在这之后都不会升高，请在该位置用 `0` 来代替。 - 此题自然可以用暴力求解法，在此不做过多赘述。 - 此题还可以使用**单调栈**的算法，该算法常用于**需要找到左边或者右边第一个比当前位置的大或小的数**。在本题中，这是一个单调递减栈，具体操作如下： - 遍历整个数组，如果栈不空，且当前数字大于栈顶元素，那么如果直接入栈的话就不是递减栈 ，所以需要取出栈顶元素，由于当前数字大于栈顶元素的数字，而且一定是第一个大于栈顶元素的数，直接求出下标差就是二者的距离。 - 继续看新的栈顶元素，直到当前数字小于等于栈顶元素停止，然后将数字入栈，这样就可以一直保持递减栈，且每个数字和第一个大于它的数的距离也可以算出来。 - 该方法的时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。 ### 1.4 树 #### 94* 二叉树的中序遍历（Easy） - **Completion Time: 2022.1.6** #### 98 验证二叉搜索树（Medium） - **Completion Time: 2022.1.14** - 给你一个二叉树的根节点 `root` ，判断其是否是一个有效的二叉搜索树。 **有效** 二叉搜索树定义如下： - 节点的左子树只包含 **小于** 当前节点的数。 - 节点的右子树只包含 **大于** 当前节点的数。 - 所有左子树和右子树自身必须也是二叉搜索树。 - 中序遍历检查元素是否单调递增即可。 #### 100 相同的树（Easy） - **Completion Time: 2022.1.3** - 给你两棵二叉树的根节点 `p` 和 `q` ，编写一个函数来检验这两棵树是否相同。如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。 - 利用 **递归** 的思想，递归定义是判断两棵树的左右子树是否都是相同的树，递归终止条件为：两个节点都是 `nullptr` 返回 `true`，其中有一个为 `nullptr` 返回 `false`。该方法的时间复杂度为 $O(\min(m,n))$，空间复杂度为 $O(\min(m,n))$，其中 m 和 n 分别是两个二叉树的节点个数。 #### 101 对称二叉树（Easy） - **Completion Time: 2022.1.4** - 给定一个二叉树，检查它是否是镜像对称的。 - 第一种方法是使用 **递归** 的思想，两棵树互为镜像需要同时满足下面的条件： - 它们的两个根结点具有相同的值 - 每个树的右子树都与另一个树的左子树镜像对称 - 我们可以实现这样一个递归函数，通过「同步移动」两个指针的方法来遍历这棵树，p 指针和 q 指针一开始都指向这棵树的根，随后 p 右移时，q 左移，p 左移时，q 右移。每次检查当前 p 和 q 节点的值是否相等，如果相等再判断左右子树是否对称。该方法的时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。 - 第二种方法是使用 **迭代** 的思想，首先我们引入一个队列，这是把递归程序改写成迭代程序的常用方法。初始化时我们把根节点入队两次。每次提取两个结点并比较它们的值（队列中每两个连续的结点应该是相等的，而且它们的子树互为镜像），然后将两个结点的左右子结点按相反的顺序插入队列中。当队列为空时，或者我们检测到树不对称（即从队列中取出两个不相等的连续结点）时，该算法结束。该方法的时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。 #### 102 二叉树的层序遍历（Medium） - **Completion Time: 2022.1.7** - 给你一个二叉树，请你返回其按 **层序遍历** 得到的节点值。 （即逐层地，从左到右访问所有节点）。 - 利用 **BFS**，每次遍历取出该层的所有元素即可。该方法的时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。 #### 104 二叉树的最大深度（Easy） - **Completion Time: 2022.1.3** - 本题的目标是求一颗二叉树的最大深度，可以使用 `BFS`。 - 使用 **递归** 的思想可以很简单的解决这个问题，递归的子问题是以二叉树的左右节点为根节点的二叉树的最大深度，递归终止条件为当前节点为 `nullptr`，即叶节点。即，如果我们知道了左子树和右子树的最大深度 $l$ 和 $r$，那么该二叉树的最大深度即为 $\max(l,r) + 1$。 - 该方法的时间复杂度为 $O(n)$，其中 n 为二叉树节点的个数；空间复杂度为 $O(\textit{height})$，其中 $\textit{height}$ 表示二叉树的高度。 #### 105* 从前序与中序遍历序列构造二叉树（Medium） - **Completion Time: 2022.1.14** - 给定一棵树的前序遍历 `preorder` 与中序遍历 `inorder`。请构造二叉树并返回其根节点。 - [从前序与中序遍历序列构造二叉树 - 从前序与中序遍历序列构造二叉树 - 力扣（LeetCode） (leetcode-cn.com)](https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/solution/cong-qian-xu-yu-zhong-xu-bian-li-xu-lie-gou-zao-9/) #### 108 将有序数组转换为二叉搜索树（Easy） - **Completion Time: 2022.1.6** - 给你一个整数数组 `nums` ，其中元素已经按 **升序** 排列，请你将其转换为一棵 **高度平衡** 二叉搜索树。**高度平衡** 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。 - 本题要求高度平衡，因此类似于二分查找的思想，每次取出数组的中间元素作为根节点，将数组左侧元素构建左子树，右侧元素构建右子树。该方法的时间复杂度为 $O(n)$，空间复杂度为 $O(log(n))$。 #### 109* 有序链表转换二叉搜索树（Medium） - **Completion Time: 2022.1.6** - 给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。本题中，一个高度平衡二叉树是指一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1。 - 第一种想法是利用单链表构造一个升序数组，然后利用 `LeetCode 108` 就可以把一个升序数组转换成一个二叉搜索树。该方法的时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。 - 如果要求不使用额外的数组空间，再来考虑这个问题。其实本质就是要找出链表的中点作为根节点，因此可以使用 **快慢指针** 的思想，快指针到达链表末尾时，慢指针所在的位置就是链表的中点。该算法的时间复杂度为 $O(nlog(n))$，空间复杂度为 $O(log(n))$。 - 第二种方法的时间复杂度的瓶颈在于寻找中位数节点。由于**构造出的二叉搜索树的中序遍历结果就是链表本身**，因此我们可以将分治和中序遍历结合起来，减少时间复杂度。具体可以参考链接：[有序链表转换二叉搜索树 - 有序链表转换二叉搜索树 - 力扣（LeetCode） (leetcode-cn.com)](https://leetcode-cn.com/problems/convert-sorted-list-to-binary-search-tree/solution/you-xu-lian-biao-zhuan-huan-er-cha-sou-suo-shu-1-3/)。该算法的时间复杂度为 $O(n)$，空间复杂度为 $O(log(n))$。 #### 110 平衡二叉树（Easy） - **Completion Time: 2022.1.3** - 给定一个二叉树，判断它是否是高度平衡的二叉树。本题中，一棵高度平衡二叉树定义为：一个二叉树 **每个节点** 的左右两个子树的高度差的绝对值不超过 1 。 - 本题可以利用 `LeetCode 104` 的计算二叉树最大深度的函数。 - 第一种方法是 **自顶向下的递归**，具体做法类似于 **二叉树的前序遍历**，即对于当前遍历到的节点，首先计算左右子树的高度，如果左右子树的高度差是否不超过 1，再分别递归地遍历左右子节点，并判断左子树和右子树是否平衡。该方法的时间复杂度为 $O(n^{2})$，空间复杂度为 $O(n)$。 - 第二种方法是 **自底向上的递归**。由于第一种方法是自顶向下递归，因此对于同一个节点，函数 $\texttt{height}$ 会被重复调用，导致时间复杂度较高。如果使用自底向上的做法，则对于每个节点，函数 $\texttt{height}$ 只会被调用一次。自底向上递归的做法类似于 **后序遍历**，对于当前遍历到的节点，先递归地判断其左右子树是否平衡，再判断以当前节点为根的子树是否平衡。如果一棵子树是平衡的，则返回其高度（高度一定是非负整数），否则返回 -1。如果存在一棵子树不平衡，则整个二叉树一定不平衡。该方法的时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。 #### 111 二叉树的最小深度（Easy） - **Completion Time: 2022.1.3** - 给定一个二叉树，找出其最小深度。 - 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。 - 叶子节点是指没有子节点的节点。 - 本题大致思路类似于 `LeetCode 104`。要注意的是，叶子节点不是 `nullptr`，而是有值且 `left == nullptr && right == nullptr`。因此在求出左右子树的最小深度后，如果两个子树中有一个为 `nullptr`，则需要计算 `leftDepth + rightDepth + 1`，而不是一味地在两棵子树中取较小值加一，即 `min(leftDepth, rightDepth) + 1`。该方法的时间复杂度为 $O(n)$，其中 n 为二叉树节点的个数；空间复杂度为 $O(\textit{height})$，其中 $\textit{height}$ 表示二叉树的高度。 #### 112 路径总和（Easy） - **Completion Time: 2022.1.3** - 给你二叉树的根节点 `root` 和一个表示目标和的整数 `targetSum` 。判断该树中是否存在 **根节点到叶子节点** 的路径，这条路径上所有节点值相加等于目标和 `targetSum` 。如果存在，返回 `true` ；否则，返回 `false` 。**叶子节点** 是指没有子节点的节点。 - 利用 **递归** 的思想，递归定义是 `(hasPathSum(root->left, targetSum - root->val) || hasPathSum(root->right, targetSum - root->val))`，终止条件为当前节点为 `nullptr` 则返回 `false`，或者当前节点为叶子节点且 `targetSum = root->val`。该方法的时间复杂度为 $O(n)$，其中 n 为二叉树节点的个数；空间复杂度为 $O(\textit{height})$，其中 $\textit{height}$ 表示二叉树的高度。 #### 113 路径总和 II（Medium） - **Completion Time: 2022.1.18** - 给你二叉树的根节点 `root` 和一个整数目标和 `targetSum` ，找出所有 **从根节点到叶子节点** 路径总和等于给定目标和的路径。 **叶子节点** 是指没有子节点的节点。 #### 124* 二叉树中的最大路径和（Hard） - **Completion Time: 2022.1.14** - **路径** 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 **至多出现一次** 。该路径 **至少包含一个** 节点，且不一定经过根节点。 **路径和** 是路径中各节点值的总和。 给你一个二叉树的根节点 `root` ，返回其 **最大路径和** 。 #### 129 求根节点到叶节点数字之和（Medium） - **Completion Time: 2022.1.15** - 给你一个二叉树的根节点 `root` ，树中每个节点都存放有一个 `0` 到 `9` 之间的数字。 每条从根节点到叶节点的路径都代表一个数字： - 例如，从根节点到叶节点的路径 `1 -> 2 -> 3` 表示数字 `123` 。 计算从根节点到叶节点生成的 **所有数字之和** 。 **叶节点** 是指没有子节点的节点。 #### 144* 二叉树的前序遍历（Easy） - **Completion Time: 2022.1.6** - 给你二叉树的根节点 `root` ，返回它节点值的 **前序** 遍历。 - 本题利用 **递归** 和 **DFS** 可以很简单的实现，在此简单介绍一下用 **迭代** 和 **BFS** 的实现方式，使用一个栈保存所有需要访问的节点，每到一个新节点首先读取该节点的值，然后按照 **先右子节点后左子节点** 的原则将子节点入栈，因为栈先进后出，所以为了保证左子树先访问需要后入栈。该方法的时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。 - 本题还有一种可以节省空间的 **Morris** 遍历的方法，具体可以参考：[二叉树的前序遍历 - 二叉树的前序遍历 - 力扣（LeetCode） (leetcode-cn.com)](https://leetcode-cn.com/problems/binary-tree-preorder-traversal/solution/er-cha-shu-de-qian-xu-bian-li-by-leetcode-solution/)。该方法的时间复杂度为 $O(n)$，空间复杂度为 $O(1)$。 #### 145* 二叉树的后序遍历（Easy） - **Completion Time: 2022.1.6** - 给定一个二叉树，返回它的 **后序** 遍历。 - 跟 `LeetCode 144` 一样，用 **递归** 和 **DFS** 可以比较简单地解决问题，在这里介绍一下用 **迭代** 和 **BFS** 的实现方式。 - 在后序遍历中，栈中弹出的节点，我们只能确定其左子树肯定访问完了，但是无法确定右子树是否访问过。 - 因此，我们在后序遍历中，引入了一个prev来记录历史访问记录。 - 当访问完一棵子树的时候，我们用prev指向该节点。 - 这样，在回溯到父节点的时候，我们可以依据prev是指向左子节点，还是右子节点，来判断父节点的访问情况。 - 因此算法主要分为两个步骤： - 不断寻找最左子节点，将中间访问的节点入栈，然后弹出其栈顶元素 - 如果栈顶元素没有右子树，或者右子树已经访问过了，则访问当前节点的值 - 该方法的时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。 #### 208* 实现 Trie (前缀树)（Medium） - **Completion Time: 2022.1.6** - **[Trie](https://baike.baidu.com/item/字典树/9825209?fr=aladdin)**（发音类似 "try"）或者说 **前缀树** 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补完和拼写检查。请你实现 Trie 类： - `Trie()` 初始化前缀树对象。 - `void insert(String word)` 向前缀树中插入字符串 `word` 。 - `boolean search(String word)` 如果字符串 `word` 在前缀树中，返回 `true`（即，在检索之前已经插入）；否则，返回 `false` 。 - `boolean startsWith(String prefix)` 如果之前已经插入的字符串 `word` 的前缀之一为 `prefix` ，返回 `true` ；否则，返回 `false` 。 - 具体定义和实现可以参考：[实现 Trie (前缀树) - 实现 Trie (前缀树) - 力扣（LeetCode） (leetcode-cn.com)](https://leetcode-cn.com/problems/implement-trie-prefix-tree/solution/shi-xian-trie-qian-zhui-shu-by-leetcode-ti500/)。了解基本概念后，实现过程并不是很难，可以理解为一个多叉树（几个字符就有几个叉）。 #### 226 翻转二叉树（Easy） - **Completion Time: 2022.1.3** - 翻转一棵二叉树。 - 利用 **递归** 和 **后序遍历** 的思想，先翻转左右两棵子树，在交换当前节点的左右子节点即可。该方法的时间复杂度为 $O(n)$；平均情况下，空间复杂度为 $O(log(n))$，最差情况下树形成链状，空间复杂度为 $O(n)$，因此最终时间复杂度为 $O(n)$。 #### 230 二叉搜索树中第K小的元素（Medium） - **Completion Time: 2022.1.6** - 给定一个二叉搜索树的根节点 `root` ，和一个整数 `k` ，请你设计一个算法查找其中第 `k` 个最小元素（从 1 开始计数）。 - 二叉查找树的中序遍历的顺序就是节点从小到大排列的顺序，因此我们对该二叉树进行中序遍历即可。该方法的时间复杂度为 $O(height + k)$，空间复杂度为 $O(\textit{height})$，其中 $\textit{height}$ 表示二叉树的高度。 - 如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，你将如何优化算法？可以参考 `LeetCode 1382` 先将二叉搜索树转化为平衡二叉搜索树。 #### 235 二叉搜索树的最近公共祖先（Easy） - **Completion Time: 2022.1.6** - 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。[百度百科](https://baike.baidu.com/item/最近公共祖先/8918834?fr=aladdin)中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（**一个节点也可以是它自己的祖先**）。” - 本题采用 **递归** 的思想，如果 p、q 的值都小于 root 的值，调用 `root->left`；如果两者都大于，则调用 `root->right`；如果一个大于，一个小与，则返回 `root`。该方法的时间复杂度为 $O(n)$，空间复杂度为 $O(1)$。 #### 236* 二叉树的最近公共祖先（Medium） - **Completion Time: 2022.1.6** - 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。[百度百科](https://baike.baidu.com/item/最近公共祖先/8918834?fr=aladdin)中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（**一个节点也可以是它自己的祖先**）。” - 第一种方法是利用 **递归** 的思想，可以分为如下三种情况： - root 为 p 或 q，这时公共祖先为 root - p、q 分别在 root 的左右子树上，此时公共祖先也是 root - p、q 在 root 的同一棵子树上，可以递归调用子函数求解 - 该方法的时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。 #### 257 二叉树的所有路径（Easy） - **Completion Time: 2022.2.5** - 给你一个二叉树的根节点 `root` ，按 **任意顺序** ，返回所有从根节点到叶子节点的路径。 **叶子节点** 是指没有子节点的节点。 - 本题可以使用 **DFS + 回溯** 的思想，遍历到叶节点就将当前路径加入到最终的结果中。本题有一个比较特殊的地方就是路径由字符串进行保存，需要提前将整数转化为字符串。 #### 337 打家劫舍 III（Medium） - **Completion Time: 2022.1.5** - 在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。 除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。 - 本题可以用 **动态规划** 的方法，维护一个记录从每一个节点开始的最大金额的 `map`。该方法的时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。 #### 404 左叶子之和（Easy） - **Completion Time: 2022.1.4** - 计算给定二叉树的所有左叶子之和。 - 利用 **二叉树的前序遍历**，对每一个节点判断其左节点是否为叶子节点，如果是则将该左节点的值记录到最终结果中即可。除此之外，利用 **DFS**、**BFS** 也是同样的道理。该方法的时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。 #### 437* 路径总和 III（Medium） - **Completion Time: 2022.1.3** - 给定一个二叉树的根节点 `root` ，和一个整数 `targetSum` ，求该二叉树里节点值之和等于 `targetSum` 的 **路径** 的数目。**路径** 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。 - 第一种方法利用了 **递归** 和 **DFS** 的思想，先定义了一个函数 `rootSum()` 表示从该节点开始的满足条件的路径条数，进而可以将问题拆分成包含该节点和不包含的独立讨论。该方法的时间复杂度为 $O(n^{2})$，空间复杂度为 $O(n)$。 - 第二种方法是利用了 **前缀和** 的思想，具体过程可以参考：[路径总和 III - 路径总和 III - 力扣（LeetCode） (leetcode-cn.com)](https://leetcode-cn.com/problems/path-sum-iii/solution/lu-jing-zong-he-iii-by-leetcode-solution-z9td/)。该方法的时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。 #### 501 二叉搜索树中的众数（Easy） - **Completion Time: 2022.1.6** - 给定一个有相同值的二叉搜索树（BST），找出 BST 中的所有众数（出现频率最高的元素）。 - 本题在 **中序遍历** 不断统计当前元素的出现次数，如果大于已知的最大出现次数则更新相关变量即可。该方法的时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。 #### 513 找树左下角的值（Easy） - **Completion Time: 2022.1.5** - 给定一个二叉树的 **根节点** `root`，请找出该二叉树的 **最底层 最左边** 节点的值。假设二叉树中至少有一个节点。 - 本题利用 **BFS** 的算法，对二叉树进行遍历，每次进入循环时队列头部的元素即为该层最左边的节点，然后取出队列中的所有元素并将其子节点加入队列。该方法的时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。 #### 530 二叉搜索树的最小绝对差（Easy） - **Completion Time: 2022.1.6** - 给你一个二叉搜索树的根节点 `root` ，返回 **树中任意两不同节点值之间的最小差值** 。差值是一个正数，其数值等于两值之差的绝对值。 - 本题在 **中序遍历** 不断跟上一个节点计算差值，并维护一个最小差值即可。该方法的时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。 #### 538 把二叉搜索树转换为累加树（Medium） - **Completion Time: 2022.1.6** - 给出二叉 **搜索** 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 `node` 的新值等于原树中大于或等于 `node.val` 的值之和。 - 本题可以使用 **反序的中序遍历**，在遍历过程中会按照节点的值从大到小的顺序进行遍历，所以可以维护一个 `sum` 变量，记录所有访问过的节点的值的和，用来取代节点的原有的值。该方法的时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。 #### 543 二叉树的直径（Easy） - **Completion Time: 2022.1.3** - 给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。 - 本题可以利用 `LeetCode 104` 的计算二叉树最大深度的函数 `maxDepth`。 - 对于每一个非叶节点，不难发现经过该节点的路径长度的最大值为 $maxDepth(left) + maxDepth(right)$。因此采用 **二叉树的后序遍历** 的方法，遍历每个节点，求出经过每个节点的路径长度最大值中的最大值。该方法的时间复杂度为 $O(n)$，其中 n 为二叉树节点的个数；空间复杂度为 $O(\textit{height})$，其中 $\textit{height}$ 表示二叉树的高度。 #### 572* 另一棵树的子树（Easy） - **Completion Time: 2022.1.3** - 给你两棵二叉树 `root` 和 `subRoot` 。检验 `root` 中是否包含和 `subRoot` 具有相同结构和节点值的子树。如果存在，返回 `true` ；否则，返回 `false` 。二叉树 `tree` 的一棵子树包括 `tree` 的某个节点和这个节点的所有后代节点。`tree` 也可以看做它自身的一棵子树。 - 第一种方法是利用 `LeetCode 100` 中判断相同的树的函数 `isSameTree()`。利用 **递归** 的思想。 - 此外还可以使用 **树哈希** 等算法，具体可以参考：[另一个树的子树 - 另一棵树的子树 - 力扣（LeetCode） (leetcode-cn.com)](https://leetcode-cn.com/problems/subtree-of-another-tree/solution/ling-yi-ge-shu-de-zi-shu-by-leetcode-solution/)。 #### 617 合并二叉树（Easy） - **Completion Time: 2022.1.3** - 给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则**不为** NULL 的节点将直接作为新二叉树的节点。 - 利用 **递归** 和 **DFS** 的思想，递归定义为当前节点的值为两个节点的值之和，左右节点分别为两个节点的相对应的左右子树的合并二叉树的根节点，终止条件为左右子结点中至少有一个为 `nullptr`。 该方法的时间复杂度为 $O(\min(m,n))$，空间复杂度为 $O(\min(m,n))$，其中 m 和 n 分别是两个二叉树的节点个数。 #### 637 二叉树的层平均值（Easy） - **Completion Time: 2022.1.5** - 给定一个非空二叉树, 返回一个由每层节点平均值组成的数组。 - 本题利用 **BFS** 的算法，对二叉树进行遍历，每次进入循环时取出队列中的所有元素，即为该层的所有元素。该方法的时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。 #### 653 两数之和 IV - 输入 BST（Easy） - **Completion Time: 2022.1.6** - 给定一个二叉搜索树 `root` 和一个目标结果 `k`，如果 BST 中存在两个元素且它们的和等于给定的目标结果，则返回 `true`。 - 第一种方法是使用 `HashSet` 记录所有出现过的值，然后对于每一个节点只需要判断其差值是否在 `HasnSet` 中即可。该方法的时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。 - 还有一种充分利用 `BST` 性质的方法，先将二叉搜索树转化为一个升序数组，然后定义两个指针从两侧（即数组的最小值和最大值）逐渐向中间逼近，寻找有没有符合条件的数字对。该方法的时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。 #### 669 修剪二叉搜索树（Medium） - **Completion Time: 2022.1.6** - 给你二叉搜索树的根节点 `root` ，同时给定最小边界`low` 和最大边界 `high`。通过修剪二叉搜索树，使得所有节点的值在`[low, high]`中。修剪树不应该改变保留在树中的元素的相对结构（即，如果没有被移除，原有的父代子代关系都应当保留）。 可以证明，存在唯一的答案。所以结果应当返回修剪好的二叉搜索树的新的根节点。注意，根节点可能会根据给定的边界发生改变。 - 利用 **递归** 的思想，当 $\text{node.val > R}$，那么修剪后的二叉树必定出现在节点的左边；类似地，当 $\text{node.val < L}$，那么修剪后的二叉树出现在节点的右边；否则，就需要修剪树的两边。该方法的时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。 #### 671 二叉树中第二小的节点（Easy） - **Completion Time: 2022.1.3** - 给定一个非空特殊的二叉树，每个节点都是正数，并且每个节点的子节点数量只能为 `2` 或 `0`。如果一个节点有两个子节点的话，那么该节点的值等于两个子节点中较小的一个。更正式地说，`root.val = min(root.left.val, root.right.val)` 总成立。给出这样的一个二叉树，你需要输出所有节点中的**第二小的值。**如果第二小的值不存在的话，输出 -1 **。** - 本题利用 **DFS** 的算法，对二叉树进行遍历，按照提议要求求出每个结点的值，不断更新最小的值和第二小的值即可。该方法的时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。 #### 687* 最长同值路径（Medium） - **Completion Time: 2022.1.4** - 给定一个二叉树，找到最长的路径，这个路径中的每个节点具有相同值。 这条路径可以经过也可以不经过根节点。两个节点之间的路径长度由它们之间的边数表示。 - 本题利用 **递归** 和 **DFS** 的思想，整体思路类似于 `LeetCode 543`。该方法的时间复杂度为 $O(n)$，其中 n 为二叉树节点的个数；空间复杂度为 $O(\textit{height})$，其中 $\textit{height}$ 表示二叉树的高度。 #### 958 二叉树的完全性检验（Medium） - **Completion Time: 2022.1.16** - 给定一个二叉树，确定它是否是一个*完全二叉树*。 **[百度百科](https://baike.baidu.com/item/完全二叉树/7773232?fr=aladdin)中对完全二叉树的定义如下：** 若设二叉树的深度为 h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。（注：第 h 层可能包含 1~ 2h 个节点。） ### 1.5 图 #### 785 判断二分图（Medium） - **Completion Time: 2022.1.6** - 存在一个 **无向图** ，图中有 `n` 个节点。其中每个节点都有一个介于 `0` 到 `n - 1` 之间的唯一编号。给你一个二维数组 `graph` ，其中 `graph[u]` 是一个节点数组，由节点 `u` 的邻接节点组成。形式上，对于 `graph[u]` 中的每个 `v` ，都存在一条位于节点 `u` 和节点 `v` 之间的无向边。该无向图同时具有以下属性： - 不存在自环（`graph[u]` 不包含 `u`）。 - 不存在平行边（`graph[u]` 不包含重复值）。 - 如果 `v` 在 `graph[u]` 内，那么 `u` 也应该在 `graph[v]` 内（该图是无向图） - 这个图可能不是连通图，也就是说两个节点 `u` 和 `v` 之间可能不存在一条连通彼此的路径。 **二分图** 定义：如果能将一个图的节点集合分割成两个独立的子集 `A` 和 `B` ，并使图中的每一条边的两个节点一个来自 `A` 集合，一个来自 `B` 集合，就将这个图称为 **二分图** 。 如果图是二分图，返回 `true` ；否则，返回 `false` 。 - 利用图中的 **BFS** 的思想，每次先找一个图中的未经染色的且没有已经染色的邻居的节点随机染色，然后在 BFS 过程中，相邻节点一定染不同的颜色，因此该子图中所有节点都可以确定是否可以正确染色。 ## Part 2 算法思想 ### 2.1 分治 #### 53* 最大子数组和（Easy） - **Completion Time: 2022.1.14** - 给你一个整数数组 `nums` ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。 **子数组** 是数组中的一个连续部分。 - 本题第一种方法是 **动态规划**，数组 `dp[i]` 表示以第 i 个元素结尾的连续子数组的最大和，则有状态转移方程 $dp[i] = max(dp[i - 1] + nums[i], nums[i])$。该方法的时间复杂度为 $O(n)$，空间复杂度为 $O(1)$。 - 本题第二种方法是 **分治**，类似于 **线段树** 的概念。具体过程可以参考：[最大子序和 - 最大子数组和 - 力扣（LeetCode） (leetcode-cn.com)](https://leetcode-cn.com/problems/maximum-subarray/solution/zui-da-zi-xu-he-by-leetcode-solution/)。 ### 2.2 动态规划 #### 70 爬楼梯（Easy） - **Completion Time: 2022.1.14** - 假设你正在爬楼梯。需要 *n* 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？ **注意：**给定 *n* 是一个正整数。 - 数组 `dp[i]` 表示爬 i 阶楼梯的方法数量，那么就有状态转移方程 $dp[i] = dp[i - 1] + dp[i - 2]$。 #### 198 打家劫舍（Medium） - **Completion Time: 2022.1.18** - 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，**如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警**。 给定一个代表每个房屋存放金额的非负整数数组，计算你 **不触动警报装置的情况下** ，一夜之内能够偷窃到的最高金额。 - 用 $\textit{dp}[i]$ 表示前 i 间房屋能偷窃到的最高总金额，那么就有状态转移方程：$dp[i] = max(dp[i-2]+nums[i],dp[i-1])$。 #### 221 最大正方形（Medium） - **Completion Time: 2022.1.14** - 在一个由 `'0'` 和 `'1'` 组成的二维矩阵内，找到只包含 `'1'` 的最大正方形，并返回其面积。 - 本题类似于 `LeerCode 1277` #### 322 零钱兑换（Medium） - **Completion Time: 2022.1.15** - 给你一个整数数组 `coins` ，表示不同面额的硬币；以及一个整数 `amount` ，表示总金额。 计算并返回可以凑成总金额所需的 **最少的硬币个数** 。如果没有任何一种硬币组合能组成总金额，返回 `-1` 。 你可以认为每种硬币的数量是无限的。 - **动态规划**，令 $dp[i]$ 表示金额 $i$ 需要的最少硬币数量，那么就有状态转移方程 $dp[i] = min(dp[i-coin]+1)$，其中 coin 是可以取的硬币金额。 #### 1277* 统计全为 1 的正方形子矩阵（Medium） - **Completion Time: 2022.1.14** - 给你一个 `m * n` 的矩阵，矩阵中的元素不是 `0` 就是 `1`，请你统计并返回其中完全由 `1` 组成的 **正方形** 子矩阵的个数。 ### 2.3 贪心算法 #### 402* 移掉 K 位数字（Medium） - **Completion Time: 2022.1.15** - 给你一个以字符串表示的非负整数 `num` 和一个整数 `k` ，移除这个数中的 `k` 位数字，使得剩下的数字最小。请你以字符串形式返回这个最小的数字。 ### 2.4 回溯算法 #### 22 括号生成（Medium） - **Completion Time: 2022.1.14** - 数字 `n` 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 **有效的** 括号组合。 #### 39 组合总和（Medium） - **Completion Time: 2022.1.18** - 给你一个 **无重复元素** 的整数数组 `candidates` 和一个目标整数 `target` ，找出 `candidates` 中可以使数字和为目标数 `target` 的 **所有不同组合** ，并以列表形式返回。你可以按 **任意顺序** 返回这些组合。 `candidates` 中的 **同一个** 数字可以 **无限制重复被选取** 。如果至少一个数字的被选数量不同，则两种组合是不同的。 对于给定的输入，保证和为 `target` 的不同组合数少于 `150` 个。 #### 46 全排列（Medium） - **Completion Time: 2022.1.13** - 给定一个不含重复数字的数组 `nums` ，返回其 **所有可能的全排列** 。你可以 **按任意顺序** 返回答案。 #### 78 子集（Medium） - **Completion Time: 2022.1.15** - 给你一个整数数组 `nums` ，数组中的元素 **互不相同** 。返回该数组所有可能的子集（幂集）。 解集 **不能** 包含重复的子集。你可以按 **任意顺序** 返回解集。 #### 79 单词搜索（Medium） - **Completion Time: 2022.1.15** - 给定一个 `m x n` 二维字符网格 `board` 和一个字符串单词 `word` 。如果 `word` 存在于网格中，返回 `true` ；否则，返回 `false` 。 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。 ## Part 3 高频面试 数据来源：[CodeTop企业题库](https://codetop.cc/home) ### 字节跳动 #### 亮点题目记录 - 15 - 146：模拟 LRU 数据结构 #### 3 无重复字符的最长子串（Medium） - **Completion Time: 2022.1.7** - 给定一个字符串 `s` ，请你找出其中不含有重复字符的 **最长子串** 的长度。 - 本题采用 **滑动窗口** 的思想，由于子串在原字符串中是一个连续的字符串，所以可以用两个指针表明子串在原字符串中的位置，遇到重复元素就左移左指针，不是重复元素就右移右指针，不断记录两个指针相差的最大值。该方法的时间复杂度为 $O(n)$，，空间复杂度为 $O(∑)$，其中 $∑$ 表示字符集的大小。 #### 15 三数之和（Medium） - **Completion Time: 2022.1.7** - 给你一个包含 `n` 个整数的数组 `nums`，判断 `nums` 中是否存在三个元素 *a，b，c ，*使得 *a + b + c =* 0 ？请你找出所有和为 `0` 且不重复的三元组。 **注意：**答案中不可以包含重复的三元组。 - 排序 + 双指针 #### 23* 合并K个升序链表（Medium） - **Completion Time: 2022.1.12** - 给你一个链表数组，每个链表都已经按升序排列。 请你将所有链表合并到一个升序链表中，返回合并后的链表。 - 分治合并 #### 25 K 个一组反转链表（Hard） 题目链接：[LeetCode25 K 个一组翻转链表](https://leetcode-cn.com/problems/reverse-nodes-in-k-group/) - **Completion Time: 2022.1.7** - 给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。 - **进阶：** - 你可以设计一个只使用常数额外空间的算法来解决此问题吗？ - **你不能只是单纯的改变节点内部的值**，而是需要实际进行节点交换。 - 本题由于要求反转一个组内的链表，很容易想到的利用 **栈** 先进后出的特性，按照原链表顺序节点入栈，节点数量到达 k 后，按照出栈顺序重新生成链表。该方法的时间复杂度为 $O(n)$，空间复杂度为 $O(1)$。 - 此处的也可以不显式地利用栈保存节点，也可以用两个变量保存一组链表的开始和结束，用一个子函数反转这组链表即可。在生成链表过程中，可以先制造一个伪头部，在返回结果的时候在返回 `head->next`，这样可以减少对头部的 `nullptr` 不必要的讨论。 #### 31* 下一个排列（Medium） - **Completion Time: 2022.1.12** - 实现获取 **下一个排列** 的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列（即，组合出下一个更大的整数）。 如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。 必须**[ 原地 ](https://baike.baidu.com/item/原地算法)**修改，只允许使用额外常数空间。 #### 32* 最长有效括号（Hard） - **Completion Time: 2022.1.14** - 给你一个只包含 `'('` 和 `')'` 的字符串，找出最长有效（格式正确且连续）括号子串的长度。 - 动态规划 - 栈 - 双向遍历 #### 33* 搜索旋转排序数组（Medium） - **Completion Time: 2022.1.12** - 整数数组 `nums` 按升序排列，数组中的值 **互不相同** 。 在传递给函数之前，`nums` 在预先未知的某个下标 `k`（`0 <= k < nums.length`）上进行了 **旋转**，使数组变为 `[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]`（下标 **从 0 开始** 计数）。例如， `[0,1,2,4,5,6,7]` 在下标 `3` 处经旋转后可能变为 `[4,5,6,7,0,1,2]` 。 给你 **旋转后** 的数组 `nums` 和一个整数 `target` ，如果 `nums` 中存在这个目标值 `target` ，则返回它的下标，否则返回 `-1` 。 #### 41* 缺失的第一个正数（Hard） - **Completion Time: 2022.1.13** - 给你一个未排序的整数数组 `nums` ，请你找出其中没有出现的最小的正整数。 请你实现时间复杂度为 `O(n)` 并且只使用常数级别额外空间的解决方案。 - 置换法，把每个元素放回正确的位置。 #### 54* 螺旋矩阵（Medium） - **Completion Time: 2022.1.12** - 给你一个 `m` 行 `n` 列的矩阵 `matrix` ，请按照 **顺时针螺旋顺序** ，返回矩阵中的所有元素。 #### 56 合并区间（Medium） - **Completion Time: 2022.1.13** - 以数组 `intervals` 表示若干个区间的集合，其中单个区间为 `intervals[i] = [starti, endi]` 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。 - 按照区间的左端点排序，那么在排完序的列表中，可以合并的区间一定是连续的。 首先，我们将列表中的区间按照左端点升序排序。然后我们将第一个区间加入 merged 数组中，并按顺序依次考虑之后的每个区间： - 如果当前区间的左端点在数组 merged 中最后一个区间的右端点之后，那么它们不会重合，我们可以直接将这个区间加入数组 merged 的末尾； - 否则，它们重合，我们需要用当前区间的右端点更新数组 merged 中最后一个区间的右端点，将其置为二者的较大值。 #### 69 Sqrt(x)（Easy） - **Completion Time: 2022.1.12** - 给你一个非负整数 `x` ，计算并返回 `x` 的 **算术平方根** 。由于返回类型是整数，结果只保留 **整数部分** ，小数部分将被 **舍去 。** **注意：**不允许使用任何内置指数函数和算符，例如 `pow(x, 0.5)` 或者 `x ** 0.5` 。 - **二分查找** #### 76* 最小覆盖子串（Hard） - **Completion Time: 2022.1.13** - 给你一个字符串 `s` 、一个字符串 `t` 。返回 `s` 中涵盖 `t` 所有字符的最小子串。如果 `s` 中不存在涵盖 `t` 所有字符的子串，则返回空字符串 `""` 。 **注意：** - 对于 `t` 中重复字符，我们寻找的子字符串中该字符数量必须不少于 `t` 中该字符数量。 - 如果 `s` 中存在这样的子串，我们保证它是唯一的答案。 - 本题使用 **滑动窗口** 的方法。具体过程可以参考：[最小覆盖子串 - 最小覆盖子串 - 力扣（LeetCode） (leetcode-cn.com)](https://leetcode-cn.com/problems/minimum-window-substring/solution/zui-xiao-fu-gai-zi-chuan-by-leetcode-solution/)。 #### 92 反转链表 II（Medium） - **Completion Time: 2022.1.13** - 给你单链表的头指针 `head` 和两个整数 `left` 和 `right` ，其中 `left <= right` 。请你反转从位置 `left` 到位置 `right` 的链表节点，返回 **反转后的链表** 。 - 本题可以使用 **一次遍历「穿针引线」反转链表（头插法）** 的方法。主要代码如下。该方法的时间复杂度为 $O(n)$，空间复杂度为 $O(1)$。 ```c++ while (curNode != rrightNode) { nextNode = curNode->next; curNode->next = prevNode; prevNode = curNode; curNode = nextNode; } ``` #### 103 二叉树的锯齿形层序遍历（Medium） - **Completion Time: 2022.1.7** - 给定一个二叉树，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。 - 利用两个栈保存每一层的元素，使用类似于 `BFS` 的算法，对树进行逐层遍历，用栈维护当前层的所有元素，遍历每一层时将子节点放入另一个栈。该方法的时间复杂度为 $O(n)$​，空间复杂度为 $O(n)$​。 #### 121 买卖股票的最佳时机（Easy） - **Completion Time: 2022.1.12** - 给定一个数组 `prices` ，它的第 `i` 个元素 `prices[i]` 表示一支给定股票第 `i` 天的价格。 你只能选择 **某一天** 买入这只股票，并选择在 **未来的某一个不同的日子** 卖出该股票。设计一个算法来计算你所能获取的最大利润。 返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 `0` 。 #### 122 买卖股票的最佳时机 II（Medium） - **Completion Time: 2022.1.15** - 给定一个数组 `prices` ，其中 `prices[i]` 是一支给定股票第 `i` 天的价格。 设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。 **注意：**你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。 #### 143 重排链表（Medium） - **Completion Time: 2022.1.12** - 给定一个单链表 `L` 的头节点 `head` ，单链表 `L` 表示为： ``` L0 → L1 → … → Ln - 1 → Ln ``` 请将其重新排列后变为： ``` L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → … ``` 不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。 - 寻找链表中点（双指针） + 链表逆序 + 合并链表 #### 146 LRU 缓存（Medium） - **Completion Time: 2022.1.7** - 请你设计并实现一个满足 [LRU (最近最少使用) 缓存](https://baike.baidu.com/item/LRU) 约束的数据结构。 实现 `LRUCache` 类： - `LRUCache(int capacity)` 以 **正整数** 作为容量 `capacity` 初始化 LRU 缓存 - `int get(int key)` 如果关键字 `key` 存在于缓存中，则返回关键字的值，否则返回 `-1` 。 - `void put(int key, int value)` 如果关键字 `key` 已经存在，则变更其数据值 `value` ；如果不存在，则向缓存中插入该组 `key-value` 。如果插入操作导致关键字数量超过 `capacity` ，则应该 **逐出** 最久未使用的关键字。 函数 `get` 和 `put` 必须以 `O(1)` 的平均时间复杂度运行。 - 本题的实现需要一个双向链表和一个哈希表，前者记录了按照最近使用顺序排列的节点，后者记录了节点的 `key` 到节点的映射关系。 - 对于初始化操作，可以加入伪头部和尾部，这样可以避免后续对链表两端的特判。 - 对于 `get()`，查找哈希表中是否存在 `key` 即可。 - 对于 `put()`，如果当前 `key` 已经存在，那么修改相应的值即可；如果不存在，则需要新建节点插入队列头部，如果实际容量大于规定的容量，则需要删除队列末尾的元素。 #### 162* 寻找峰值（Medium） - **Completion Time: 2022.1.14** - 峰值元素是指其值严格大于左右相邻值的元素。 给你一个整数数组 `nums`，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 **任何一个峰值** 所在位置即可。 你可以假设 `nums[-1] = nums[n] = -∞` 。 你必须实现时间复杂度为 `O(log n)` 的算法来解决此问题。 - **二分查找** #### 199 二叉树的右视图（Medium） - **Completion Time: 2022.1.12** - 给定一个二叉树的 **根节点** `root`，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。 - 层序遍历，输出每一层的最后一个值 #### 200 岛屿数量（Medium） - **Completion Time: 2022.1.12** - 给你一个由 `'1'`（陆地）和 `'0'`（水）组成的的二维网格，请你计算网格中岛屿的数量。 岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。 此外，你可以假设该网格的四条边均被水包围。 - 我们可以将二维网格看成一个无向图，竖直或水平相邻的 1 之间有边相连。 为了求出岛屿的数量，我们可以扫描整个二维网格。如果一个位置为 1，则以其为起始节点开始进行深度优先搜索。在深度优先搜索的过程中，每个搜索到的 1 都会被重新标记为 0。 最终岛屿的数量就是我们进行深度优先搜索的次数。 #### 215 数组中的第K个最大元素（Medium） - **Completion Time: 2022.1.7** - 给定整数数组 `nums` 和整数 `k`，请返回数组中第 `k` 个最大的元素。请注意，你需要找的是数组排序后的第 `k` 个最大的元素，而不是第 `k` 个不同的元素。 - 第一种方法是基于 **快速排序** 的选择算法，但是不需要将整个数组都排好序，在快速排序中过程中会选择任意一个元素 x 作为主元，**调整子数组的元素使得左边的元素都小于等于它，右边的元素都大于等于它**，那这个 x 的下标就是其在数组中的排序后的位置，利用这个性质即可。该方法的时间复杂度为 $O(n)$，空间复杂度为 $O(log(n))$。 - 第二种方法是基于 **堆排序** 的选择算法。首先根据原数组建立一个大根堆，做 $k-1$ 次删除操作后堆顶元素就是我们要找的答案。该方法的时间复杂度为 $O(nlog(n))$，空间复杂度为 $O(log(n))$。 #### 300 最长递增子序列（Medium） - **Completion Time: 2022.1.13** - 给你一个整数数组 `nums` ，找到其中最长严格递增子序列的长度。 子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，`[3,6,2,7]` 是数组 `[0,3,1,6,2,2,7]` 的子序列。 - 第一种方法是 **动态规划**。定义 $\textit{dp}[i]$ 为考虑前 $i$ 个元素，以第 $i$ 个数字结尾的最长上升子序列的长度。则状态转移方程为：$dp[i]=max(dp[j])+1$，其中 $0≤j