网硕互联帮助中心力扣hot 100
来源：leetcode.cn /studyplan/top-100-liked
一、哈希
1. 两数之和【简单】 → leetcode.cn/problems/two-sum
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。 你可以按任意顺序返回答案。 示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：nums[0] + nums[1] == 9，返回 [0, 1]
示例 2：
输入：nums = [3,2,4], target = 6
输出：[1,2]
示例 3：
输入：nums = [3,3], target = 6
输出：[0,1]
约束： 2 <= nums.length <= 10⁴；-10⁹ <= nums[i] <= 10⁹；-10⁹ <= target <= 10⁹；只会存在一个有效答案。进阶：你能想出一个时间复杂度小于 O(n²) 的算法吗？
49. 字母异位词分组【中等】 → group-anagrams
给你一个字符串数组，请你将字母异位词组合在一起。可以按任意顺序返回结果列表。 字母异位词是由重新排列源单词的所有字母得到的新单词。 示例 1：
输入：strs = ["eat","tea","tan","ate","nat","bat"]
输出：[["bat"],["nat","tan"],["ate","eat","tea"]]
示例 2：
输入：strs = [""]
输出：[[""]]
示例 3：
输入：strs = ["a"]
输出：[["a"]]
约束： 1 <= strs.length <= 10⁴；0 <= strs[i].length <= 100；strs[i] 仅包含小写字母。
128. 最长连续序列【中等】 → longest-consecutive-sequence
给定一个未排序的整数数组 nums，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。 请你设计并实现时间复杂度为 O(n) 的算法解决此问题。 示例 1：
输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]，长度为 4
示例 2：
输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9
约束： 0 <= nums.length <= 10⁵；-10⁹ <= nums[i] <= 10⁹。
二、双指针
283. 移动零【简单】 → move-zeroes
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。 请注意，必须在不复制数组的情况下原地对数组进行操作。 示例 1：
输入：nums = [0,1,0,3,12]
输出：[1,3,12,0,0]
示例 2：
输入：nums = [0]
输出：[0]
约束： 1 <= nums.length <= 10⁴；-2³¹ <= nums[i] <= 2³¹ – 1。进阶：你能尽量减少完成的操作次数吗？
11. 盛最多水的容器【中等】 → container-with-most-water
给定一个长度为 n 的整数数组 height。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i])。 找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。 返回容器可以储存的最大水量。 注意：你不能倾斜容器。 示例 1：
输入：height = [1,8,6,2,5,4,8,3,7]
输出：49
解释：选择第 2 条线(高度8)与第 9 条线(高度7)，宽度 min(8,7)=7，面积 7×7=49
示例 2：
输入：height = [1,1]
输出：1
约束： n == height.length；2 <= n <= 10⁵；0 <= height[i] <= 10⁴。
15. 三数之和【中等】 → 3sum
给你一个整数数组 nums，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k，同时还满足 nums[i] + nums[j] + nums[k] == 0。请你返回所有和为 0 且不重复的三元组。 注意：答案中不可以包含重复的三元组。 示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0
不同的三元组是 [-1,0,1] 和 [-1,-1,2]
示例 2：
输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0
示例 3：
输入：nums = [0,0,0]
输出：[[0,0,0]]
约束： 3 <= nums.length <= 3000；-10⁵ <= nums[i] <= 10⁵。
42. 接雨水【困难】 → trapping-rain-water
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。 示例 1：
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，可以接 6 个单位的雨水
示例 2：
输入：height = [4,2,0,3,2,5]
输出：9
约束： n == height.length；1 <= n <= 2×10⁴；0 <= height[i] <= 10⁵。
三、滑动窗口
3. 无重复字符的最长子串【中等】 → longest-substring-without-repeating-characters
给定一个字符串 s，请你找出其中不含有重复字符的最长子串的长度。 示例 1：
输入：s = "abcabcbb"
输出：3
解释：因为无重复字符的最长子串是 "abc"，所以其长度为 3
示例 2：
输入：s = "bbbbb"
输出：1
解释：最长子串是 "b"，长度为 1
示例 3：
输入：s = "pwwkew"
输出：3
解释：最长子串是 "wke"，长度为 3。注意答案必须是子串，"pwke" 是子序列而非子串
约束： 0 <= s.length <= 5×10⁴；s 由英文字母、数字、符号和空格组成。
438. 找到字符串中所有字母异位词【中等】 → find-all-anagrams-in-a-string
给定两个字符串 s 和 p，找到 s 中所有 p 的异位词子串，返回这些子串的起始索引。不考虑答案输出的顺序。 异位词指由相同字母重排列形成的字符串（包括相同的字符串）。 示例 1：
输入：s = "cbaebabacd", p = "abc"
输出：[0,6]
解释：
起始索引为 0 的子串是 "cba"，它是 "abc" 的异位词
起始索引为 6 的子串是 "bac"，它是 "abc" 的异位词
示例 2：
输入：s = "abab", p = "ab"
输出：[0,1,2]
解释：
起始索引为 0 的子串是 "ab"
起始索引为 1 的子串是 "ba"
起始索引为 2 的子串是 "ab"
约束： 1 <= s.length, p.length <= 3×10⁴；s 和 p 仅包含小写字母。
四、子串
560. 和为 K 的子数组【中等】 → subarray-sum-equals-k
给你一个整数数组 nums 和一个整数 k，请你统计并返回该数组中和为 k 的子数组的个数。 子数组是数组中元素的连续非空序列。 示例 1：
输入：nums = [1,1,1], k = 2
输出：2
示例 2：
输入：nums = [1,2,3], k = 3
输出：2
约束： 1 <= nums.length <= 2×10⁴；-1000 <= nums[i] <= 1000；-10⁷ <= k <= 10⁷。
239. 滑动窗口最大值【困难】 → sliding-window-maximum
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。 返回滑动窗口中的最大值。 示例 1：
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
窗口位置 最大值
[1 3 -1] -3 5 3 6 7 → 3
1 [3 -1 -3] 5 3 6 7 → 3
1 3 [-1 -3 5] 3 6 7 → 5
1 3 -1 [-3 5 3] 6 7 → 5
1 3 -1 -3 [5 3 6] 7 → 6
1 3 -1 -3 5 [3 6 7] → 7
示例 2：
输入：nums = [1], k = 1
输出：[1]
约束： 1 <= nums.length <= 10⁵；-10⁴ <= nums[i] <= 10⁴；1 <= k <= nums.length。
76. 最小覆盖子串【困难】 → minimum-window-substring
给你一个字符串 s、一个字符串 t。返回 s 中涵盖 t 所有字符（含重复字符）的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 ""。 注意：
- 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量
- 如果 s 中存在这样的子串，我们保证它是唯一的 示例 1：
输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'
示例 2：
输入：s = "a", t = "a"
输出："a"
示例 3：
输入：s = "a", t = "aa"
输出：""
解释：t 中两个字符 'a' 均应包含在 s 的子串中，因此没有符合条件的子字符串
约束： m == s.length，n == t.length；1 <= m, n <= 10⁵；s 和 t 由英文大小写字母组成。进阶：你能设计一个在 o(m+n) 时间内解决此问题的算法吗？
五、普通数组
53. 最大子数组和【中等】 → maximum-subarray
给你一个整数数组 nums，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。 子数组是数组中的一个连续部分。 示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6
示例 2：
输入：nums = [1]
输出：1
示例 3：
输入：nums = [5,4,-1,7,8]
输出：23
约束： 1 <= nums.length <= 10⁵；-10⁴ <= nums[i] <= 10⁴。进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。
56. 合并区间【中等】 → merge-intervals
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [startᵢ, endᵢ]。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。 示例 1：
输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6]
示例 2：
输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间
约束： 1 <= intervals.length <= 10⁴；intervals[i].length == 2；0 <= startᵢ <= endᵢ <= 10⁴。
189. 轮转数组【中等】 → rotate-array
给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。 示例 1：
输入：nums = [1,2,3,4,5,6,7], k = 3
输出：[5,6,7,1,2,3,4]
解释：
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]
示例 2：
输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释：
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]
约束： 1 <= nums.length <= 10⁵；-2³¹ <= nums[i] <= 2³¹ – 1；0 <= k <= 10⁵。进阶：
- 尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题
- 你可以使用空间复杂度为 O(1) 的原地算法解决这个问题吗？
238. 除自身以外数组的乘积【中等】 → product-of-array-except-self
给你一个整数数组 nums，返回数组 answer，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。 题目数据保证数组 nums 之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请不要使用除法，且在 O(n) 时间复杂度内完成此题。 示例 1：
输入：nums = [1,2,3,4]
输出：[24,12,8,6]
示例 2：
输入：nums = [-1,1,0,-3,3]
输出：[0,0,9,0,0]
约束： 2 <= nums.length <= 10⁵；-30 <= nums[i] <= 30；保证数组 nums 之中任意元素的全部前缀元素和后缀的乘积都在 32 位整数范围内。进阶：你可以在 O(1) 的额外空间复杂度内完成这个题目吗？（出于对空间复杂度分析的目的，输出数组不被视为额外空间。）
41. 缺失的第一个正数【困难】 → first-missing-positive
给你一个未排序的整数数组 nums，请你找出其中没有出现的最小的正整数。 请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。 示例 1：
输入：nums = [1,2,0]
输出：3
示例 2：
输入：nums = [3,4,-1,1]
输出：2
示例 3：
输入：nums = [7,8,9,11,12]
输出：1
约束： 1 <= nums.length <= 5×10⁵；-2³¹ <= nums[i] <= 2³¹ – 1。
六、矩阵
73. 矩阵置零【中等】 → set-matrix-zeroes
给定一个 m × n 的矩阵，如果一个元素为 0，则将其所在行和列的所有元素都设为 0。请使用原地算法。 示例 1：
输入：matrix = [[1,1,1],[1,0,1],[1,1,1]]
输出：[[1,0,1],[0,0,0],[1,0,1]]
示例 2：
输入：matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
输出：[[0,0,0,0],[0,4,5,0],[0,3,1,0]]
约束： m == matrix.length；n == matrix[0].length；1 <= m, n <= 200；-2³¹ <= matrix[i][j] <= 2³¹ – 1。进阶：
- 一个直观的解决方案是使用 O(mn) 的额外空间，但这并不是一个好的解决方案
- 一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案
- 你能想出一个仅使用常量空间的解决方案吗？
54. 螺旋矩阵【中等】 → spiral-matrix
给你一个 m 行 n 列的矩阵 matrix，请按照顺时针螺旋顺序，返回矩阵中的所有元素。 示例 1：
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]
示例 2：
输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出：[1,2,3,4,8,12,11,10,9,5,6,7]
约束： m == matrix.length；n == matrix[i].length；1 <= m, n <= 10；-100 <= matrix[i][j] <= 100。
48. 旋转图像【中等】 → rotate-image
给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。 你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。 示例 1：
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[[7,4,1],[8,5,2],[9,6,3]]
示例 2：
输入：matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
输出：[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]
约束： n == matrix.length == matrix[i].length；1 <= n <= 20；-1000 <= matrix[i][j] <= 1000。
240. 搜索二维矩阵 II【中等】 → search-a-2d-matrix-ii
编写一个高效的算法来搜索 m × n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性：
- 每行的元素从左到右升序排列
- 每列的元素从上到下升序排列 示例 1：
输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
输出：true
示例 2：
输入：matrix 同上, target = 20
输出：false
约束： m == matrix.length；n == matrix[i].length；1 <= n, m <= 300；-10⁹ <= matrix[i][j] <= 10⁹；每行的所有元素从左到右升序排列；每列的所有元素从上到下升序排列；-10⁹ <= target <= 10⁹。
七、链表
160. 相交链表【简单】 → intersection-of-two-linked-lists
给你两个单链表的头节点 headA 和 headB，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null。 题目数据保证整个链式结构中不存在环。 注意，函数返回结果后，链表必须保持其原始结构。 示例 1：
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 3, skipB = 2
输出：Intersected at '8'
解释：相交节点的值为 8。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。
在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 2 个节点。
示例 2：
输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Intersected at '2'
示例 3：
输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。这两个链表不相交。
约束： listA 中节点数目为 m，listB 中节点数目为 n；1 <= m, n <= 3×10⁴；1 <= Node.val <= 10⁵；0 <= skipA <= m；0 <= skipB <= n；如果 listA 和 listB 没有交点，intersectVal == 0。进阶：你能否设计一个时间复杂度 O(m + n)、仅用 O(1) 内存的解决方案？
206. 反转链表【简单】 → reverse-linked-list
给你单链表的头节点 head，请你反转链表，并返回反转后的链表。 示例 1：
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
示例 2：
输入：head = [1,2]
输出：[2,1]
示例 3：
输入：head = []
输出：[]
约束： 链表中节点的数目范围是 [0, 5000]；-5000 <= Node.val <= 5000。进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？
234. 回文链表【简单】 → palindrome-linked-list
给你一个单链表的头节点 head，请你判断该链表是否为回文链表。如果是，返回 true；否则，返回 false。 示例 1：
输入：head = [1,2,2,1]
输出：true
示例 2：
输入：head = [1,2]
输出：false
约束： 链表中节点数目在范围 [1, 10⁵] 内；0 <= Node.val <= 9。进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
141. 环形链表【简单】 → linked-list-cycle
给你一个链表的头节点 head，判断链表中是否有环。 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达它，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。 如果链表中存在环，则返回 true；否则，返回 false。 示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点（索引为 1）
示例 2：
输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点
示例 3：
输入：head = [1], pos = -1
输出：false
解释：链表中没有环
约束： 链表中节点的数目范围是 [0, 10⁴]；-10⁵ <= Node.val <= 10⁵；pos 为 -1 或者链表中的一个有效索引。进阶：你能用 O(1)（即，常量）内存解决此问题吗？
142. 环形链表 II【中等】 → linked-list-cycle-ii
给定一个链表的头节点 head，返回链表开始入环的第一个节点。如果链表无环，则返回 null。 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达它，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。 不允许修改链表。 示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点
示例 2：
输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
示例 3：
输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环
约束： 链表中节点的数目范围在 [0, 10⁴] 内；-10⁵ <= Node.val <= 10⁵；pos 的值为 -1 或者链表中的一个有效索引。进阶：你是否可以使用 O(1) 空间解决此题？
21. 合并两个有序链表【简单】 → merge-two-sorted-lists
将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例 1：
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
示例 2：
输入：l1 = [], l2 = []
输出：[]
示例 3：
输入：l1 = [], l2 = [0]
输出：[0]
约束： 两个链表的节点数目范围是 [0, 50]；-100 <= Node.val <= 100；l1 和 l2 均按非递减顺序排列。
2. 两数相加【中等】 → add-two-numbers
给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。 请你将两个数相加，并以相同形式返回一个表示和的链表。 你可以假设除了数字 0 之外，这两个数都不会以 0 开头。 示例 1：
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807
示例 2：
输入：l1 = [0], l2 = [0]
输出：[0]
示例 3：
输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]
约束： 每个链表中的节点数在范围 [1, 100] 内；0 <= Node.val <= 9；题目数据保证列表表示的数字不含前导零。
19. 删除链表的倒数第 N 个结点【中等】 → remove-nth-node-from-end-of-list
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。 示例 1：
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
示例 2：
输入：head = [1], n = 1
输出：[]
示例 3：
输入：head = [1,2], n = 1
输出：[1]
约束： 链表中结点的数目为 sz；1 <= sz <= 30；0 <= Node.val <= 100；1 <= n <= sz。进阶：你能尝试使用一趟扫描实现吗？
24. 两两交换链表中的节点【中等】 → swap-nodes-in-pairs
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。 示例 1：
输入：head = [1,2,3,4]
输出：[2,1,4,3]
示例 2：
输入：head = []
输出：[]
示例 3：
输入：head = [1]
输出：[1]
约束： 链表中节点的数目在范围 [0, 100] 内；0 <= Node.val <= 100。
25. K 个一组翻转链表【困难】 → reverse-nodes-in-k-group
给你链表的头节点 head，每 k 个节点一组进行翻转，请你返回修改后的链表。 k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。 示例 1：
输入：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5]
示例 2：
输入：head = [1,2,3,4,5], k = 3
输出：[3,2,1,4,5]
约束： 链表中的节点数目为 n；1 <= k <= n <= 5000；0 <= Node.val <= 1000。进阶：你可以设计一个只用 O(1) 额外内存空间的算法解决此问题吗？
138. 随机链表的复制【中等】 → copy-list-with-random-pointer
给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random，该指针可以指向链表中的任何节点或空节点。 构造这个链表的深拷贝。深拷贝应该正好由 n 个全新节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点。 例如，如果原链表中有 X 和 Y 两个节点，其中 X.random –> Y，那么在复制链表中对应的两个节点 x 和 y，同样有 x.random –> y。 返回复制链表的头节点。请不要修改原链表。 用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：val 是节点值；random_index 是随机指针指向的节点索引（范围从 0 到 n-1），null 表示不指向任何节点。 示例 1：
输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
示例 2：
输入：head = [[1,1],[2,1]]
输出：[[1,1],[2,1]]
示例 3：
输入：head = [[3,null],[3,0],[3,null]]
输出：[[3,null],[3,0],[3,null]]
约束： 0 <= n <= 1000；-10⁴ <= Node.val <= 10⁴；Node.random 为 null 或指向链表中的节点。
148. 排序链表【中等】 → sort-list
给你链表的头结点 head，请将其按升序排列并返回排序后的链表。 示例 1：
输入：head = [4,2,1,3]
输出：[1,2,3,4]
示例 2：
输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]
示例 3：
输入：head = []
输出：[]
约束： 链表中节点的数目在范围 [0, 5×10⁴] 内；-10⁵ <= Node.val <= 10⁵。进阶：你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？
23. 合并 K 个升序链表【困难】 → merge-k-sorted-lists
给你一个链表数组，每个链表都已经按升序排列。 请你将所有链表合并到一个升序链表中，返回合并后的链表。 示例 1：
输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
1->4->5,
1->3->4,
2->6
将它们合并到一个有序链表中得到：
1->1->2->3->4->4->5->6
示例 2：
输入：lists = []
输出：[]
示例 3：
输入：lists = [[]]
输出：[]
约束： k == lists.length；0 <= k <= 10⁴；0 <= lists[i].length <= 500；-10⁴ <= lists[i][j] <= 10⁴；lists[i] 按升序排列；lists[i].length 的总和不超过 10⁴。
146. LRU 缓存【中等】 → lru-cache
请你设计并实现一个满足 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) 的平均时间复杂度运行。 示例：
输入：
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出：
[null, null, null, 1, null, -1, null, -1, 3, 4]
解释：
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1); // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2); // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1); // 返回 -1 (未找到)
lRUCache.get(3); // 返回 3
lRUCache.get(4); // 返回 4
约束： 1 <= capacity <= 3000；0 <= key <= 10⁴；0 <= value <= 10⁵；最多调用 2×10⁵ 次 get 和 put。
八、二叉树
94. 二叉树的中序遍历【简单】 → binary-tree-inorder-traversal
给定一个二叉树的根节点 root，返回它的中序遍历结果。 示例 1：
输入：root = [1,null,2,3]
输出：[1,3,2]
示例 2：
输入：root = []
输出：[]
示例 3：
输入：root = [1]
输出：[1]
约束： 树中节点数目在范围 [0, 100] 内；-100 <= Node.val <= 100。进阶：递归算法很简单，你可以通过迭代算法完成吗？
104. 二叉树的最大深度【简单】 → maximum-depth-of-binary-tree
给定一个二叉树 root，返回其最大深度。 二叉树的最大深度是指从根节点到最远叶子节点的最长路径上的节点数。 示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：3
示例 2：
输入：root = [1,null,2]
输出：2
约束： 树中节点的数量在 [0, 10⁴] 区间内；-100 <= Node.val <= 100。
226. 翻转二叉树【简单】 → invert-binary-tree
给你一棵二叉树的根节点 root，翻转这棵二叉树，并返回其根节点。 示例 1：
输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]
示例 2：
输入：root = [2,1,3]
输出：[2,3,1]
示例 3：
输入：root = []
输出：[]
约束： 树中节点数目范围在 [0, 100] 内；-100 <= Node.val <= 100。
101. 对称二叉树【简单】 → symmetric-tree
给你一个二叉树的根节点 root，检查它是否轴对称。 示例 1：
输入：root = [1,2,2,3,4,4,3]
输出：true
示例 2：
输入：root = [1,2,2,null,3,null,3]
输出：false
约束： 树中节点数目在范围 [1, 1000] 内；-100 <= Node.val <= 100。进阶：你可以运用递归和迭代两种方法解决这个问题吗？
543. 二叉树的直径【简单】 → diameter-of-binary-tree
给你一棵二叉树的根节点，返回该树的直径。 二叉树的直径是指树中任意两个节点之间最长路径的边数。这条路径可能经过也可能不经过根节点 root。 两节点之间路径的长度由它们之间边数表示。 示例 1：
输入：root = [1,2,3,4,5]
输出：3
解释：最长路径为 [4,2,1,3] 或 [5,2,1,3]，长度为 3
示例 2：
输入：root = [1,2]
输出：1
约束： 树中节点数目在范围 [1, 10⁴] 内；-100 <= Node.val <= 100。
102. 二叉树的层序遍历【中等】 → binary-tree-level-order-traversal
给你二叉树的根节点 root，返回其节点值的层序遍历（即逐层地，从左到右访问所有节点）。 示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]
示例 2：
输入：root = [1]
输出：[[1]]
示例 3：
输入：root = []
输出：[]
约束： 树中节点数目在范围 [0, 2000] 内；-1000 <= Node.val <= 1000。
108. 将有序数组转换为二叉搜索树【简单】 → convert-sorted-array-to-binary-search-tree
给你一个整数数组 nums，其中元素已经按升序排列，请你将其转换为一棵高度平衡的二叉搜索树。 高度平衡二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1」的二叉树。 示例 1：
输入：nums = [-10,-3,0,5,9]
输出：[0,-3,9,-10,null,5]
解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案
示例 2：
输入：nums = [1,3]
输出：[3,1]
解释：[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树
约束： 1 <= nums.length <= 10⁴；-10⁴ <= nums[i] <= 10⁴；nums 按严格递增顺序排列。
98. 验证二叉搜索树【中等】 → validate-binary-search-tree
给你一个二叉树的根节点 root，判断其是否是一个有效的二叉搜索树。 有效二叉搜索树定义如下：
- 节点的左子树只包含小于当前节点的数
- 节点的右子树只包含大于当前节点的数
- 所有左子树和右子树自身必须也是二叉搜索树 示例 1：
输入：root = [2,1,3]
输出：true
示例 2：
输入：root = [5,1,4,null,null,3,6]
输出：false
解释：根节点的值是 5，但右子节点的值是 4
约束： 树中节点数目范围在 [1, 10⁴] 内；-2³¹ <= Node.val <= 2³¹ – 1。
230. 二叉搜索树中第 K 小的元素【中等】 → kth-smallest-element-in-a-bst
给定一个二叉搜索树的根节点 root，和一个整数 k，请你设计一个算法查找其中第 k 个最小的元素（从 1 开始计数）。 示例 1：
输入：root = [3,1,4,null,2], k = 1
输出：1
示例 2：
输入：root = [5,3,6,2,4,null,null,1], k = 3
输出：3
约束： 树中的节点数为 n；1 <= k <= n <= 10⁴；0 <= Node.val <= 10⁴。进阶：如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，你将如何优化算法？
199. 二叉树的右视图【中等】 → binary-tree-right-side-view
给定一个二叉树的根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。 示例 1：
输入：root = [1,2,3,null,5,null,4]
输出：[1,3,4]
示例 2：
输入：root = [1,2,3,4,null,null,null,5]
输出：[1,3,4,5]
示例 3：
输入：root = [1,null,3]
输出：[1,3]
示例 4：
输入：root = []
输出：[]
约束： 二叉树的节点个数的范围是 [0,100]；-100 <= Node.val <= 100。
114. 二叉树展开为链表【中等】 → flatten-binary-tree-to-linked-list
给你二叉树的根结点 root，请你将它展开为一个单链表：
- 展开后的单链表应该同样使用 TreeNode，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null
- 展开后的单链表应该与二叉树先序遍历顺序相同 示例 1：
输入：root = [1,2,5,3,4,null,6]
输出：[1,null,2,null,3,null,4,null,5,null,6]
示例 2：
输入：root = []
输出：[]
示例 3：
输入：root = [0]
输出：[0]
约束： 树中结点数在范围 [0, 2000] 内；-100 <= Node.val <= 100。进阶：你可以使用原地算法（O(1) 额外空间）展开这棵树吗？
105. 从前序与中序遍历序列构造二叉树【中等】 → construct-binary-tree-from-preorder-and-inorder-traversal
给定两个整数数组 preorder 和 inorder，其中 preorder 是二叉树的先序遍历，inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。 示例 1：
输入：preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出：[3,9,20,null,null,15,7]
示例 2：
输入：preorder = [-1], inorder = [-1]
输出：[-1]
约束： 1 <= preorder.length <= 3000；inorder.length == preorder.length；-3000 <= preorder[i], inorder[i] <= 3000；preorder 和 inorder 均无重复元素；inorder 均出现在 preorder 中；preorder 保证为二叉树的前序遍历序列，inorder 保证为二叉树的中序遍历序列。
437. 路径总和 III【中等】 → path-sum-iii
给定一棵二叉树的根节点 root 和一个整数 targetSum，求该二叉树里节点值之和等于 targetSum 的路径的数目。 路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。 示例 1：
输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
输出：3
解释：和等于 8 的路径有 3 条，如图所示
示例 2：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：3
约束： 二叉树的节点个数的范围是 [0,1000]；-10⁹ <= Node.val <= 10⁹；-1000 <= targetSum <= 1000。
236. 二叉树的最近公共祖先【中等】 → lowest-common-ancestor-of-a-binary-tree
给定一个二叉树，找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为：「对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。」 示例 1：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3
示例 2：
输入：root 同上, p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5（因为根据定义最近公共祖先节点可以为节点本身）
示例 3：
输入：root = [1,2], p = 1, q = 2
输出：1
约束： 树中节点数目在范围 [2, 10⁵] 内；-10⁹ <= Node.val <= 10⁹；所有 Node.val 互不相同；p != q；p 和 q 均存在于给定的二叉树中。
124. 二叉树中的最大路径和【困难】 → binary-tree-maximum-path-sum
二叉树中的路径被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中至多出现一次。该路径至少包含一个节点，且不一定经过根节点。 路径和是路径中各节点值的总和。 给你一个二叉树的根节点 root，返回其最大路径和。 示例 1：
输入：root = [1,2,3]
输出：6
解释：最优路径是 2 -> 1 -> 3，路径和为 2 + 1 + 3 = 6
示例 2：
输入：root = [-10,9,20,null,null,15,7]
输出：42
解释：最优路径是 15 -> 20 -> 7，路径和为 15 + 20 + 7 = 42
约束： 树中节点数目范围是 [1, 3×10⁴]；-1000 <= Node.val <= 1000。
九、图论
200. 岛屿数量【中等】 → number-of-islands
给你一个由 '1'（陆地）和 '0'（水）组成的二维网格 grid，请你计算网格中岛屿的数量。 岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。 你可以假设该网格的四条边均被水包围。 示例 1：
输入：grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
输出：1
示例 2：
输入：grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
输出：3
约束： m == grid.length；n == grid[i].length；1 <= m, n <= 300；grid[i][j] 的值为 '0' 或 '1'。
994. 腐烂的橘子【中等】 → rotting-oranges
在给定的 m × n 网格 grid 中，每个单元格可以有以下三个值之一：
- 值 0 代表空单元格
- 值 1 代表新鲜橘子
- 值 2 代表腐烂的橘子 每分钟，腐烂的橘子周围 4 个方向上相邻的新鲜橘子都会腐烂。 返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1。 示例 1：
输入：grid = [[2,1,1],[1,1,0],[0,1,1]]
输出：4
示例 2：
输入：grid = [[2,1,1],[0,1,1],[1,0,1]]
输出：-1
解释：左下角的橘子（第 2 行，第 0 列）永远不会腐烂，因为腐烂只会发生在 4 个方向上
示例 3：
输入：grid = [[0,2]]
输出：0
解释：因为 0 分钟时已经没有新鲜橘子了，所以答案就是 0
约束： m == grid.length；n == grid[i].length；1 <= m, n <= 10；grid[i][j] 仅为 0、1 或 2。
207. 课程表【中等】 → course-schedule
你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses – 1。 在选修某些课程之前需要一些先修课程。先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [aᵢ, bᵢ]，表示如果要学习课程 aᵢ 则必须先学习课程 bᵢ。
- 例如，先修课程对 [0, 1] 表示：想要学习课程 0，你需要先完成课程 1 请你判断是否可能完成所有课程的学习？如果可以，返回 true；否则，返回 false。 示例 1：
输入：numCourses = 2, prerequisites = [[1,0]]
输出：true
解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0，这是可能的
示例 2：
输入：numCourses = 2, prerequisites = [[1,0],[0,1]]
输出：false
解释：总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0；并且学习课程 0 之前，你还应先完成课程 1，这是不可能的
约束： 1 <= numCourses <= 2000；0 <= prerequisites.length <= 5000；prerequisites[i].length == 2；0 <= aᵢ, bᵢ < numCourses；prerequisites[i] 中的所有课程对互不相同。
208. 实现 Trie (前缀树)【中等】 → implement-trie-prefix-tree
Trie（发音类似 “try”）或者说前缀树是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补全和拼写检查。 请你实现 Trie 类：
- Trie() 初始化前缀树对象
- void insert(String word) 向前缀树中插入字符串 word
- boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即在检索之前已经插入）；否则，返回 false
- boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix，返回 true；否则，返回 false 示例：
输入：
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
输出：
[null, null, true, false, true, null, true]
解释：
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple"); // 返回 True
trie.search("app"); // 返回 False
trie.startsWith("app"); // 返回 True
trie.insert("app");
trie.search("app"); // 返回 True
约束： 1 <= word.length, prefix.length <= 2000；word 和 prefix 仅由小写英文字母组成；insert、search 和 startsWith 调用次数总计不超过 3×10⁴ 次。
十、回溯
46. 全排列【中等】 → permutations
给定一个不含重复数字的数组 nums，返回其所有可能的全排列。你可以按任意顺序返回答案。 示例 1：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
示例 2：
输入：nums = [0,1]
输出：[[0,1],[1,0]]
示例 3：
输入：nums = [1]
输出：[[1]]
约束： 1 <= nums.length <= 6；-10 <= nums[i] <= 10；nums 中的所有整数互不相同。
78. 子集【中等】 → subsets
给你一个整数数组 nums，数组中的元素互不相同。返回该数组所有可能的子集（幂集）。 解集不能包含重复的子集。你可以按任意顺序返回解集。 示例 1：
输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例 2：
输入：nums = [0]
输出：[[],[0]]
约束： 1 <= nums.length <= 10；-10 <= nums[i] <= 10；nums 中的所有元素互不相同。
17. 电话号码的字母组合【中等】 → letter-combinations-of-a-phone-number
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按任意顺序返回。 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
2: abc 3: def
4: ghi 5: jkl 6: mno
7: pqrs 8: tuv 9: wxyz
示例 1：
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
示例 2：
输入：digits = ""
输出：[]
示例 3：
输入：digits = "2"
输出：["a","b","c"]
约束： 0 <= digits.length <= 4；digits[i] 是范围 ['2', '9'] 的一个数字。
39. 组合总和【中等】 → combination-sum
给你一个无重复元素的整数数组 candidates 和一个目标整数 target，找出 candidates 中可以使数字和为目标数 target 的所有不同组合，并以列表形式返回。你可以按任意顺序返回这些组合。 candidates 中的同一个数字可以无限制重复被选取。如果至少一个数字的被选数量不同，则两种组合是不同的。 对于给定的输入，保证和为 target 的不同组合数少于 150 个。 示例 1：
输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7。注意 2 可以使用多次
7 也是一个候选，7 = 7。仅有这两种组合
示例 2：
输入：candidates = [2,3,5], target = 8
输出：[[2,2,2,2],[2,3,3],[3,5]]
示例 3：
输入：candidates = [2], target = 1
输出：[]
约束： 1 <= candidates.length <= 30；2 <= candidates[i] <= 40；candidates 的所有元素互不相同；1 <= target <= 40。
22. 括号生成【中等】 → generate-parentheses
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且有效的括号组合。 示例 1：
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
示例 2：
输入：n = 1
输出：["()"]
约束： 1 <= n <= 8。
79. 单词搜索【中等】 → word-search
给定一个 m × n 二维字符网格 board 和一个字符串单词 word。如果 word 存在于网格中，返回 true；否则，返回 false。 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中「相邻」单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。 示例 1：
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true
示例 2：
输入：board 同上, word = "SEE"
输出：true
示例 3：
输入：board 同上, word = "ABCB"
输出：false
约束： m == board.length；n == board[i].length；1 <= m, n <= 6；1 <= word.length <= 15；board 和 word 仅由大小写英文字母组成。进阶：你可以使用搜索剪枝的技术来优化解决方案，使其在 board 更大的情况下可以更快解决问题？
131. 分割回文串【中等】 → palindrome-partitioning
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文串。返回 s 所有可能的分割方案。 示例 1：
输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]
示例 2：
输入：s = "a"
输出：[["a"]]
约束： 1 <= s.length <= 16；s 仅由小写英文字母组成。
51. N 皇后【困难】 → n-queens
按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。 n 皇后问题研究的是如何将 n 个皇后放置在 n × n 的棋盘上，并且使皇后彼此之间不能相互攻击。 给你一个整数 n，返回所有不同的 n 皇后问题的解决方案。 每一种解法包含一个不同的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。 示例 1：
输入：n = 4
输出：[[".Q..","…Q","Q…","..Q."],["..Q.","Q…","…Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法
示例 2：
输入：n = 1
输出：[["Q"]]
约束： 1 <= n <= 9。
十一、二分查找
35. 搜索插入位置【简单】 → search-insert-position
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 示例 1：
输入：nums = [1,3,5,6], target = 5
输出：2
示例 2：
输入：nums = [1,3,5,6], target = 2
输出：1
示例 3：
输入：nums = [1,3,5,6], target = 7
输出：4
约束： 1 <= nums.length <= 10⁴；-10⁴ <= nums[i] <= 10⁴；nums 为无重复元素的升序排列数组；-10⁴ <= target <= 10⁴。
74. 搜索二维矩阵【中等】 → search-a-2d-matrix
给你一个满足下述两条属性的 m × n 整数矩阵：
- 每行中的整数从左到右按非严格递增顺序排列
- 每行的第一个整数大于前一行的最后一个整数 给你一个整数 target，如果 target 在矩阵中，返回 true；否则，返回 false。 示例 1：
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true
示例 2：
输入：matrix 同上, target = 13
输出：false
约束： m == matrix.length；n == matrix[i].length；1 <= m, n <= 100；-10⁴ <= matrix[i][j], target <= 10⁴。
34. 在排序数组中查找元素的第一个和最后一个位置【中等】 → find-first-and-last-position-of-element-in-sorted-array
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。 如果数组中不存在目标值 target，返回 [-1, -1]。 你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。 示例 1：
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]
示例 2：
输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]
示例 3：
输入：nums = [], target = 0
输出：[-1,-1]
约束： 0 <= nums.length <= 10⁵；-10⁹ <= nums[i] <= 10⁹；nums 是一个非递减数组；-10⁹ <= target <= 10⁹。
33. 搜索旋转排序数组【中等】 → search-in-rotated-sorted-array
整数数组 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。 你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。 示例 1：
输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4
示例 2：
输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1
示例 3：
输入：nums = [1], target = 0
输出：-1
约束： 1 <= nums.length <= 5000；-10⁴ <= nums[i] <= 10⁴；nums 中的每个值都独一无二；nums 必定会在某个下标上旋转；-10⁴ <= target <= 10⁴。
153. 寻找旋转排序数组中的最小值【中等】 → find-minimum-in-rotated-sorted-array
已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次旋转后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：
- 若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
- 若旋转 7 次，则可以得到 [0,1,2,4,5,6,7] 注意，数组 [a[0], a[1], a[2], …, a[n-1]] 旋转一次的结果为数组 [a[n-1], a[0], a[1], …, a[n-2]]。 给你元素值互不相同的数组 nums，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的最小元素。 你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。 示例 1：
输入：nums = [3,4,5,1,2]
输出：1
解释：原数组为 [1,2,3,4,5]，旋转 3 次得到输入数组
示例 2：
输入：nums = [4,5,6,7,0,1,2]
输出：0
示例 3：
输入：nums = [11,13,15,17]
输出：11
约束： n == nums.length；1 <= n <= 5000；-5000 <= nums[i] <= 5000；nums 中的所有整数互不相同；nums 原来是一个升序排序的数组，并进行了 1 至 n 次旋转。
4. 寻找两个正序数组的中位数【困难】 → median-of-two-sorted-arrays
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。 算法的时间复杂度应该为 O(log (m+n))。 示例 1：
输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3]，中位数 2
示例 2：
输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4]，中位数 (2 + 3) / 2 = 2.5
约束： 0 <= m, n <= 1000；1 <= m + n <= 2000；-10⁶ <= nums1[i], nums2[i] <= 10⁶。
十二、栈
20. 有效的括号【简单】 → valid-parentheses
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s，判断字符串是否有效。 有效字符串需满足：
输入：s = "()"
输出：true
示例 2：
输入：s = "()[]{}"
输出：true
示例 3：
输入：s = "(]"
输出：false
示例 4：
输入：s = "([])"
输出：true
约束： 1 <= s.length <= 10⁴；s 仅由括号 '()[]{}' 组成。
155. 最小栈【中等】 → min-stack
设计一个支持 push、pop、top 操作，并能在常数时间内检索到最小元素的栈。 实现 MinStack 类：
- MinStack() 初始化堆栈对象
- void push(int val) 将元素 val 推入堆栈
- void pop() 删除堆栈顶部的元素
- int top() 获取堆栈顶部的元素
- int getMin() 获取堆栈中的最小元素 示例 1：
输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
输出：
[null,null,null,null,-3,null,0,-2]
解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // 返回 -3
minStack.pop();
minStack.top(); // 返回 0
minStack.getMin(); // 返回 -2
约束： -2³¹ <= val <= 2³¹ – 1；pop、top 和 getMin 操作总是在非空栈上调用；最多调用 3×10⁴ 次 push、pop、top 和 getMin 操作。
394. 字符串解码【中等】 → decode-string
给定一个经过编码的字符串，返回它解码后的字符串。 编码规则为：k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。 你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。 此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k，例如不会出现像 3a 或 2[4] 的输入。 示例 1：
输入：s = "3[a]2[bc]"
输出："aaabcbc"
示例 2：
输入：s = "3[a2[c]]"
输出："accaccacc"
示例 3：
输入：s = "2[abc]3[cd]ef"
输出："abcabccdcdcdef"
约束： 1 <= s.length <= 30；s 由小写英文字母、数字和方括号 '[]' 组成；s 保证是一个有效的输入；s 中所有整数的取值范围为 [1, 300]。
739. 每日温度【中等】 → daily-temperatures
给定一个整数数组 temperatures，表示每天的温度，返回一个数组 answer，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。 示例 1：
输入：temperatures = [73,74,75,71,69,72,76,73]
输出：[1,1,4,2,1,1,0,0]
示例 2：
输入：temperatures = [30,40,50,60]
输出：[1,1,1,0]
示例 3：
输入：temperatures = [30,60,90]
输出：[1,1,0]
约束： 1 <= temperatures.length <= 10⁵；30 <= temperatures[i] <= 100。
84. 柱状图中最大的矩形【困难】 → largest-rectangle-in-histogram
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1。 求在该柱状图中，能够勾勒出来的矩形的最大面积。 示例 1：
输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10
示例 2：
输入：heights = [2,4]
输出：4
约束： 1 <= heights.length <= 10⁵；0 <= heights[i] <= 10⁴。
十三、堆
215. 数组中的第K个最大元素【中等】 → kth-largest-element-in-an-array
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。 请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。 你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。 示例 1：
输入：nums = [3,2,1,5,6,4], k = 2
输出：5
示例 2：
输入：nums = [3,2,3,1,2,4,5,5,6], k = 4
输出：4
约束： 1 <= k <= nums.length <= 10⁵；-10⁴ <= nums[i] <= 10⁴。
347. 前 K 个高频元素【中等】 → top-k-frequent-elements
给你一个整数数组 nums 和一个整数 k，请你返回其中出现频率前 k 高的元素。你可以按任意顺序返回答案。 示例 1：
输入：nums = [1,1,1,2,2,3], k = 2
输出：[1,2]
示例 2：
输入：nums = [1], k = 1
输出：[1]
约束： 1 <= nums.length <= 10⁵；k 的取值范围是 [1, 数组中不相同的元素的个数]；题目数据保证答案唯一。进阶：你所设计算法的时间复杂度必须优于 O(n log n)，其中 n 是数组大小。
295. 数据流的中位数【困难】 → find-median-from-data-stream
中位数是有序整数列表中的中间值。如果列表的长度是偶数，则中位数是两个中间值的平均值。
- 例如，arr = [2,3,4] 的中位数是 3
- 例如，arr = [2,3] 的中位数是 (2 + 3) / 2 = 2.5 实现 MedianFinder 类：
- MedianFinder() 初始化 MedianFinder 对象
- void addNum(int num) 将数据流中的整数 num 添加到数据结构中
- double findMedian() 返回到目前为止所有元素的中位数 示例 1：
输入：
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
[[], [1], [2], [], [3], []]
输出：
[null, null, null, 1.50000, null, 2.00000]
解释：
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1); // arr = [1]
medianFinder.addNum(2); // arr = [1, 2]
medianFinder.findMedian(); // 返回 1.5 ((1 + 2) / 2)
medianFinder.addNum(3); // arr = [1, 2, 3]
medianFinder.findMedian(); // 返回 2.0
约束： -10⁵ <= num <= 10⁵；在调用 findMedian 之前，数据结构中至少有一个元素；最多调用 5×10⁴ 次 addNum 和 findMedian。进阶：
- 如果数据流中所有整数都在 0 到 100 范围内，你将如何优化你的算法？
- 如果数据流中 99% 的整数都在 0 到 100 范围内，你将如何优化你的算法？
十四、贪心算法
121. 买卖股票的最佳时机【简单】 → best-time-to-buy-and-sell-stock
给定一个数组 prices，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。 你只能选择某一天买入这只股票，并选择在未来的某一个不同的日子卖出该股票。设计一个算法来计算你所能获取的最大利润。 返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0。 示例 1：
输入：prices = [7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）买入，在第 5 天（股票价格 = 6）卖出，最大利润 = 6 – 1 = 5。
注意利润不能是 7-1 = 6，因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
示例 2：
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下，没有交易完成，所以最大利润为 0
约束： 1 <= prices.length <= 10⁵；0 <= prices[i] <= 10⁴。
55. 跳跃游戏【中等】 → jump-game
给你一个非负整数数组 nums，你最初位于数组的第一个下标。数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个下标，如果可以，返回 true；否则，返回 false。 示例 1：
输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1，然后再从下标 1 跳 3 步到达最后一个下标
示例 2：
输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0，所以永远不可能到达最后一个下标
约束： 1 <= nums.length <= 10⁴；0 <= nums[i] <= 10⁵。
45. 跳跃游戏 II【中等】 → jump-game-ii
给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。 每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处（0 <= j <= nums[i] 且 i + j < n）。 返回到达 nums[n – 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n – 1]。 示例 1：
输入：nums = [2,3,1,1,4]
输出：2
解释：跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
示例 2：
输入：nums = [2,3,0,1,4]
输出：2
约束： 1 <= nums.length <= 10⁴；0 <= nums[i] <= 1000；保证可以到达 nums[n-1]。
763. 划分字母区间【中等】 → partition-labels
给你一个字符串 s。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。例如 "ababcc" 能够被分为 ["abab", "cc"]，但类似 ["aba", "bcc"] 或 ["ab", "ab", "cc"] 是无效的划分。 注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s。 返回一个表示每个字符串片段的长度的列表。 示例 1：
输入：s = "ababcbacadefegdehijhklij"
输出：[9,7,8]
解释：
划分结果为 "ababcbaca"、"defegde"、"hijhklij"。
每个字母最多出现在一个片段中。
像 "ababcbacadefegde"、"hijhklij" 的划分是错误的，因为划分的片段数较少。
示例 2：
输入：s = "eccbbbbdec"
输出：[10]
约束： 1 <= s.length <= 500；s 仅由小写英文字母组成。
十五、动态规划
70. 爬楼梯【简单】 → climbing-stairs
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？ 示例 1：
输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶：
1. 1 阶 + 1 阶
2. 2 阶
示例 2：
输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶：
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶
约束： 1 <= n <= 45。
118. 杨辉三角【简单】 → pascals-triangle
给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。 在「杨辉三角」中，每个数是它左上方和右上方的数的和。 示例 1：
输入：numRows = 5
输出：[[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
示例 2：
输入：numRows = 1
输出：[[1]]
约束： 1 <= numRows <= 30。
198. 打家劫舍【中等】 → house-robber
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下，一夜之内能够偷窃到的最高金额。 示例 1：
输入：nums = [1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1)，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4
示例 2：
输入：nums = [2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12
约束： 1 <= nums.length <= 100；0 <= nums[i] <= 400。
279. 完全平方数【中等】 → perfect-squares
给你一个整数 n，返回和为 n 的完全平方数的最少数量。 完全平方数是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。 示例 1：
输入：n = 12
输出：3
解释：12 = 4 + 4 + 4
示例 2：
输入：n = 13
输出：2
解释：13 = 4 + 9
约束： 1 <= n <= 10⁴。
322. 零钱兑换【中等】 → coin-change
给你一个整数数组 coins，表示不同面额的硬币；以及一个整数 amount，表示总金额。 计算并返回可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。 你可以认为每种硬币的数量是无限的。 示例 1：
输入：coins = [1,2,5], amount = 11
输出：3
解释：11 = 5 + 5 + 1
示例 2：
输入：coins = [2], amount = 3
输出：-1
示例 3：
输入：coins = [1], amount = 0
输出：0
约束： 1 <= coins.length <= 12；1 <= coins[i] <= 2³¹ – 1；0 <= amount <= 10⁴。
139. 单词拆分【中等】 → word-break
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s。 注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。 示例 1：
输入：s = "leetcode", wordDict = ["leet", "code"]
输出：true
解释：返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成
示例 2：
输入：s = "applepenapple", wordDict = ["apple", "pen"]
输出：true
解释：返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。
注意，你可以重复使用字典中的单词。
示例 3：
输入：s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出：false
约束： 1 <= s.length <= 300；1 <= wordDict.length <= 1000；1 <= wordDict[i].length <= 20；s 和 wordDict[i] 仅有小写英文字母组成；wordDict 中的所有字符串互不相同。
300. 最长递增子序列【中等】 → longest-increasing-subsequence
给你一个整数数组 nums，找到其中最长严格递增子序列的长度。 子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。 示例 1：
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4
示例 2：
输入：nums = [0,1,0,3,2,3]
输出：4
示例 3：
输入：nums = [7,7,7,7,7,7,7]
输出：1
约束： 1 <= nums.length <= 2500；-10⁴ <= nums[i] <= 10⁴。进阶：
- 你能将算法的时间复杂度降低到 O(n log(n)) 吗？
152. 乘积最大子数组【中等】 → maximum-product-subarray
给你一个整数数组 nums，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。 测试用例的答案是一个 32 位 整数。 示例 1：
输入：nums = [2,3,-2,4]
输出：6
解释：子数组 [2,3] 有最大乘积 6
示例 2：
输入：nums = [-2,0,-1]
输出：0
解释：结果不能为 2，因为 [-2,-1] 不是子数组
约束： 1 <= nums.length <= 2×10⁴；-10 <= nums[i] <= 10；nums 的任何前缀或后缀的乘积都保证是一个 32 位整数。
416. 分割等和子集【中等】 → partition-equal-subset-sum
给你一个只包含正整数的非空数组 nums。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。 示例 1：
输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11]
示例 2：
输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集
约束： 1 <= nums.length <= 200；1 <= nums[i] <= 100。
32. 最长有效括号【困难】 → longest-valid-parentheses
给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。 示例 1：
输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"
示例 2：
输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"
示例 3：
输入：s = ""
输出：0
约束： 0 <= s.length <= 3×10⁴；s[i] 为 '(' 或 ')'。
十六、多维动态规划
62. 不同路径【中等】 → unique-paths
一个机器人位于一个 m × n 网格的左上角（起始点在下图中标记为 “Start”）。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。 问总共有多少条不同的路径？ 示例 1：
输入：m = 3, n = 7
输出：28
示例 2：
输入：m = 3, n = 2
输出：3
解释：从左上角开始，总共有 3 条路径可以到达右下角：
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下
示例 3：
输入：m = 7, n = 3
输出：28
示例 4：
输入：m = 3, n = 3
输出：6
约束： 1 <= m, n <= 100；题目数据保证答案小于等于 2×10⁹。
64. 最小路径和【中等】 → minimum-path-sum
给定一个包含非负整数的 m × n 网格 grid，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。 说明：每次只能向下或者向右移动一步。 示例 1：
输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小
示例 2：
输入：grid = [[1,2,3],[4,5,6]]
输出：12
约束： m == grid.length；n == grid[i].length；1 <= m, n <= 200；0 <= grid[i][j] <= 200。
1143. 最长公共子序列【中等】 → longest-common-subsequence
给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。如果不存在公共子序列，返回 0。 一个字符串的子序列是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
- 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列 字符串的公共子序列是这两个字符串所共同拥有的子序列。 示例 1：
输入：text1 = "abcde", text2 = "ace"
输出：3
解释：最长公共子序列是 "ace"，它的长度为 3
示例 2：
输入：text1 = "abc", text2 = "abc"
输出：3
解释：最长公共子序列是 "abc"，它的长度为 3
示例 3：
输入：text1 = "abc", text2 = "def"
输出：0
解释：两个字符串没有公共子序列，返回 0
约束： 1 <= text1.length, text2.length <= 1000；text1 和 text2 仅由小写英文字符组成。
72. 编辑距离【困难】 → edit-distance
给你两个单词 word1 和 word2，请返回将 word1 转换成 word2 所使用的最少操作数。 你可以对一个单词进行如下三种操作：
- 插入一个字符
- 删除一个字符
- 替换一个字符 示例 1：
输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')
示例 2：
输入：word1 = "intention", word2 = "execution"
输出：5
解释：
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')
约束： 0 <= word1.length, word2.length <= 500；word1 和 word2 由小写英文字母组成。
5. 最长回文子串【中等】 → longest-palindromic-substring
给你一个字符串 s，找到 s 中最长的回文子串。 示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案
示例 2：
输入：s = "cbbd"
输出："bb"
约束： 1 <= s.length <= 1000；s 仅由数字和英文字母组成。
十七、技巧
136. 只出现一次的数字【简单】 → single-number
给你一个非空整数数组 nums，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。 你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。 示例 1：
输入：nums = [2,2,1]
输出：1
示例 2：
输入：nums = [4,1,2,1,2]
输出：4
示例 3：
输入：nums = [1]
输出：1
约束： 1 <= nums.length <= 3×10⁴；-3×10⁴ <= nums[i] <= 3×10⁴；除了某个元素只出现一次以外，其余每个元素均出现两次。
169. 多数元素【简单】 → majority-element
给定一个大小为 n 的数组 nums，返回其中的多数元素。多数元素是指在数组中出现次数大于 ⌊n/2⌋ 的元素。 你可以假设数组是非空的，并且给定的数组总是存在多数元素。 示例 1：
输入：nums = [3,2,3]
输出：3
示例 2：
输入：nums = [2,2,1,1,1,2,2]
输出：2
约束： n == nums.length；1 <= n <= 5×10⁴；-10⁹ <= nums[i] <= 10⁹。进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。
75. 颜色分类【中等】 → sort-colors
给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。 我们使用整数 0、1 和 2 分别表示红色、白色和蓝色。 必须在不使用库内置的 sort 函数的情况下解决这个问题。 示例 1：
输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]
示例 2：
输入：nums = [2,0,1]
输出：[0,1,2]
约束： n == nums.length；1 <= n <= 300；nums[i] 为 0、1 或 2。进阶：
- 你可以不使用代码库中的排序函数来解决这道题吗？
- 你能想出一个仅使用常数空间的一趟扫描算法吗？
31. 下一个排列【中等】 → next-permutation
整数数组的一个排列就是将其所有成员的序列进行排序。 整数数组的下一个排列是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的下一个排列就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么数字必须重新排成字典序最小的排列（即，其元素按升序排列）。
- 例如，arr = [1,2,3] 的下一个排列是 [1,3,2]
- 类似地，arr = [2,3,1] 的下一个排列是 [3,1,2]
- 而 arr = [3,2,1] 的下一个排列是 [1,2,3]，因为 [3,2,1] 不存在一个字典序更大的排列 给你一个整数数组 nums，找出 nums 的下一个排列。 必须原地修改，只允许使用额外常数空间。 示例 1：
输入：nums = [1,2,3]
输出：[1,3,2]
示例 2：
输入：nums = [3,2,1]
输出：[1,2,3]
示例 3：
输入：nums = [1,1,5]
输出：[1,5,1]
约束： 1 <= nums.length <= 100；0 <= nums[i] <= 100。
287. 寻找重复数【困难】 → find-the-duplicate-number
给定一个包含 n + 1 个整数的数组 nums，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。 假设 nums 只有一个重复的整数，返回这个重复的数。 你设计的解决方案必须不修改数组 nums 且只用常量级 O(1) 的额外空间。 示例 1：
输入：nums = [1,3,4,2,2]
输出：2
示例 2：
输入：nums = [3,1,3,4,2]
输出：3
示例 3：
输入：nums = [3,3,3,3,3]
输出：3
约束： 1 <= n <= 10⁵；nums.length == n + 1；1 <= nums[i] <= n；nums 中只有一个整数出现两次或多次，其余整数均只出现一次。进阶：
- 如何证明 nums 中至少存在一个重复的数字？
- 你可以设计一个逻辑级（非位运算级别）的解决方案吗？
评论前必须登录！
注册