Hot100

这里收录 Hot100 中与贪心相关的题目，重点理解局部选择为什么足以推出全局答案，以及扫描过程中应该冻结哪些状态。 推荐阅读顺序 LeetCode 121：买卖股票的最佳时机，从历史最低价推出一次交易贪心 LeetCode 55：跳跃游戏，用最远覆盖范围判断能否到达终点 LeetCode 45：跳跃游戏 II，从可达边界升级到最少跳数 LeetCode 435：无重叠区间，从删除最少转成保留最多 LeetCode 452：用最少数量的箭引爆气球，从共同交集推出区间贪心

这里收录 Hot100 中与并查集相关的模板和题目，重点理解集合代表、路径压缩、合并条件、连通性判断和连通分量计数。 推荐阅读顺序 并查集模板：find / union / count 从零推导 LeetCode 547：省份数量，把邻接矩阵看成图的连通分量

这里收录 Hot100 中与 Trie 相关的题目和模板，重点理解节点字段、children 路径、结束标记和循环 invariant。

这里收录 Hot100 中与回溯相关的题目，统一按 ACERS 结构整理，强调“从题目目标一步一步推到代码结果”的 guided-build 学习方式，以及“模板稳定 + 剪枝明确 + 工程迁移”。

这里收录 Hot100 中与二叉树相关的题目，统一按 ACERS 结构整理。

这里收录 Hot100 中与链表相关的题目，统一按 ACERS 结构整理。

题目要求 设计一个栈 MinStack，支持以下操作： MinStack()：初始化栈。 push(value)：把 value 压入栈顶。 pop()：删除栈顶元素。 top()：返回栈顶元素。 getMin()：返回栈中的最小元素。 题目要求每个操作的时间复杂度都是 O(1)。 pop、top 和 getMin 只会在栈非空时调用，因此不需要为这些方法设计额外的空栈返回值。 示例 输入操作： ["MinStack", "push", "push", "push", "getMin", "pop", "top", "getMin"] 输入参数： [[], [-2], [0], [-3], [], [], [], []] 输出： [null, null, null, null, -3, null, 0, -2] 对应的执行过程是： min_stack = MinStack() min_stack.push(-2) min_stack.push(0) min_stack.push(-3) min_stack.getMin() # -3 min_stack.pop() min_stack.top() # 0 min_stack.getMin() # -2 约束 -2^31 <= value <= 2^31 - 1 最多调用 3 * 10^4 次 push、pop、top 和 getMin pop、top 和 getMin 调用时栈一定非空 Step 1：弹出最小值后，前一个最小值从哪里回来 普通栈已经能保存值，并按照后进先出的顺序执行 push、pop 和 top。当前 baseline 是： ...

题目要求 给定一个只包含以下六种字符的字符串 s： ( ) { } [ ] 判断这个字符串是否有效。有效字符串必须同时满足三个条件： 每个左括号都由相同类型的右括号闭合。 左括号必须按照正确顺序闭合。 每个右括号都有一个对应的同类型左括号。 满足全部条件时返回 True，否则返回 False。 示例 输入 输出 "()" True "()[]{}" True "(]" False "([])" True "([)]" False 约束 1 <= s.length <= 10^4 s 只包含 ()[]{} 中的字符 LeetCode 提供的方法签名是： class Solution: def isValid(self, s: str) -> bool: pass Step 1：数量相同为什么仍然无效 先看两个字符串： ()[]{} ([)] 它们都有一个 ( 和一个 )、一个 [ 和一个 ]。如果只分别统计三种左括号和右括号的数量，这两个字符串都会通过检查。 当前 baseline 是： 分别统计每种左括号和右括号；数量全部相同就认为字符串有效。 这个 baseline 会在 ([)] 上给出错误答案。问题不在括号数量，而在闭合顺序：读到一个右括号时，它必须闭合最近遇到、但还没有被闭合的左括号。 把这个规则用于 ([)]： ...

题目要求 给定一个编码字符串 s，返回它解码后的字符串。 编码规则是： k[encoded_string] 方括号中的 encoded_string 需要连续重复 k 次，其中 k 是正整数。编码可以嵌套，也可以与普通小写字母相邻。 题目保证： 输入字符串始终有效，方括号完整配对且没有多余空格。 原始文本不包含数字，数字只表示重复次数。 不会出现 3a 或 2[4] 这类不符合编码规则的输入。 解码后的字符串长度不会超过 10^5。 示例 输入 输出 "3[a]2[bc]" "aaabcbc" "3[a2[c]]" "accaccacc" "2[abc]3[cd]ef" "abcabccdcdcdef" 约束 1 <= s.length <= 30 s 只包含小写英文字母、数字和 [] 所有重复次数都在 [1, 300] 范围内 LeetCode 提供的方法签名是： class Solution: def decodeString(self, s: str) -> str: pass Step 1：进入内层以后，外层信息去了哪里 先从没有嵌套的输入开始： 3[a] 读到 3 后知道下一段需要重复三次；读完方括号中的 a，得到： a * 3 = aaa 当前 baseline 是： 读出一个重复次数，再收集后续方括号中的文本，遇到 ] 时执行重复。 这个 baseline 可以处理一层 3[a]，却会在 3[a2[c]] 上中断。外层已经读到重复次数 3 和普通字母 a，此时又遇到了内层编码 2[c]。如果直接把当前次数改成 2、当前文本改成 c，外层的 3 和 a 就丢失了。 ...

题目要求 输入给出一个非空整数数组 nums。数组中的元素互不相同；旋转前，数组按严格递增顺序排列。 数组会被旋转 1 到 nums.length 次。每旋转一次，就把最后一个元素移到数组最前面；因此，旋转 nums.length 次后，数组恢复为原来的递增顺序。返回旋转后数组中的最小值。题目要求算法的运行时间为 O(log n)。 LeetCode 使用以下方法契约： class Solution: def findMin(self, nums: List[int]) -> int: 官方示例 输入：nums = [3,4,5,1,2] 输出：1 输入：nums = [4,5,6,7,0,1,2] 输出：0 输入：nums = [11,13,15,17] 输出：11 约束 1 <= nums.length <= 5000 -5000 <= nums[i] <= 5000 nums 中的所有整数互不相同。 旋转前，nums 按严格递增顺序排列。 nums 被旋转 1 到 nums.length 次。 Step 1：先得到一个肯定正确的最小值 对于 [3,4,5,1,2]，为什么不能直接返回第一个元素？ 压力 这个数组的第一个元素是 3，但最小值是旋转后移到中间的 1。旋转保留了所有值，却不保证最小值仍在下标 0，所以直接返回 nums[0] 会得到错误答案。 ...

题目要求 输入给出一个整数数组 nums 和一个整数 target。nums 中的元素互不相同；旋转前，数组严格递增。调用方法前，数组可能在某个未知下标 k（0 <= k < nums.length）处旋转为： [nums[k], ..., nums[n-1], nums[0], ..., nums[k-1]] 如果 target 存在，返回它在旋转后数组中的下标；否则返回 -1。题目要求算法的运行时间为 O(log n)。 LeetCode 使用以下方法契约： class Solution: def search(self, nums: List[int], target: int) -> int: 官方示例 输入：nums = [4,5,6,7,0,1,2], target = 0 输出：4 输入：nums = [4,5,6,7,0,1,2], target = 3 输出：-1 输入：nums = [1], target = 0 输出：-1 约束 1 <= nums.length <= 5000 -10^4 <= nums[i], target <= 10^4 nums 中的每个值都互不相同。 nums 旋转前按严格递增顺序排列。 Step 1：先正确搜索每一种旋转 对于 [4,5,6,7,0,1,2]，怎样先得到一个不受旋转位置影响的正确答案？ ...

题目要求 给定一个非负整数数组 heights。每个 heights[i] 表示宽度为 1 的柱子高度，所有柱子紧挨排列。 题目要求返回柱状图中能够形成的最大矩形面积。 一个合法矩形必须覆盖一段连续柱子。它的宽度是这段区间包含的柱子数量，高度不能超过区间中的最矮柱。 LeetCode 提供的方法接口是： largestRectangleArea(heights: List[int]) -> int 示例 1 输入：heights = [2,1,5,6,2,3] 输出：10 下标 2 和 3 的两根柱子高度分别是 5 和 6，可以形成高度 5、宽度 2、面积 10 的矩形。 示例 2 输入：heights = [2,4] 输出：4 可以选择高度 4、宽度 1，也可以选择高度 2、宽度 2，最大面积都是 4。 约束 1 <= heights.length <= 10^5 0 <= heights[i] <= 10^4 Step 1：矩形面积不是柱高之和 先看一个小柱状图： heights = [2,1,2] 如果矩形覆盖全部三根柱子，它的宽度是 3，但高度最多只能是 1： height = 1 width = 3 area = 1 * 3 = 3 不能把三根柱高相加得到 5。柱状图矩形覆盖的是一块完整矩形区域，中间高度为 1 的柱子会限制整个区间的矩形高度。 ...

题目要求 给你一个非空整数数组 nums。 数组中只有一个元素出现一次，其余每个元素都恰好出现两次。题目要求返回那个只出现一次的元素。 LeetCode 提供的方法接口是： singleNumber(nums: List[int]) -> int 除了返回正确答案，解法还需要满足两个要求： 时间复杂度是 O(n)。 只使用 O(1) 额外空间。 示例 1 输入：nums = [2,2,1] 输出：1 2 出现两次，只有 1 出现一次。 示例 2 输入：nums = [4,1,2,1,2] 输出：4 1 和 2 都能找到相同的另一个元素，最后只有 4 没有配对。 示例 3 输入：nums = [1] 输出：1 数组只有一个元素时，它就是答案。 约束 1 <= nums.length <= 3 * 10^4 -3 * 10^4 <= nums[i] <= 3 * 10^4 除一个元素只出现一次外，其余元素都恰好出现两次。 Step 1：先把“只出现一次”说准确 先看： nums = [4,1,2,1,2] 在这个很小的数组里，我们可以用眼睛寻找相同的数字： ...

题目要求 给定一个非负整数 n，返回一个长度为 n + 1 的数组 answer。 其中： answer[i] = 整数 i 的二进制表示中 1 的数量 需要回答的范围包含 0 和 n。 LeetCode 提供的方法接口是： countBits(n: int) -> List[int] 示例 1 输入：n = 2 输出：[0,1,1] 对应关系是： 0 -> 0 -> 0 个 1 1 -> 1 -> 1 个 1 2 -> 10 -> 1 个 1 示例 2 输入：n = 5 输出：[0,1,1,2,1,2] 约束 0 <= n <= 10^5 Step 1：这次要回答 0 到 n 的所有数字 LeetCode 191 只要求统计一个整数。现在看 n = 5： ...

题目要求 给定一个整数数组 temperatures，其中 temperatures[i] 表示第 i 天的温度。 返回数组 answer，其中： answer[i] = 从第 i 天开始，需要等待多少天才会遇到更高温度 如果之后没有更高温度，answer[i] = 0。 这里的“更高”是严格大于。相同温度不能结算等待中的日期。 LeetCode 提供的方法接口是： dailyTemperatures(temperatures: List[int]) -> List[int] 示例 输入：temperatures = [73,74,75,71,69,72,76,73] 输出：[1,1,4,2,1,1,0,0] 约束 1 <= temperatures.length <= 10^5 30 <= temperatures[i] <= 100 Step 1：答案不是更高温度，而是等待天数 先看一个更小的输入： temperatures = [73,71,72,76] 逐天回答： 第 0 天是 73，右侧第一个更高温度是第 3 天的 76，等待 3 天。 第 1 天是 71，第 2 天的 72 更高，等待 1 天。 第 2 天是 72，第 3 天的 76 更高，等待 1 天。 第 3 天右侧没有日期，答案是 0。 所以结果是： ...

题目要求 给你一个 n x n 的矩阵 isConnected，其中有 n 个城市。 如果 isConnected[i][j] == 1，说明城市 i 和城市 j 直接相连；如果两个城市可以通过若干个直接相连的城市互相到达，它们就属于同一个省份。 题目要求返回省份的总数。 这里最容易误解的一点是：题目不是让我们数矩阵里有多少个 1，也不是只看直接相连的城市对。它真正要数的是： 直接或间接连接在一起的城市组有多少个。 换成图的语言，就是： 给定一个无向图的邻接矩阵，返回这个图的连通分量数量。 输入输出 输入：isConnected: List[List[int]] 输出：省份数量 int 城市编号可以按 0..n-1 理解。 isConnected[i][j] == 1 表示城市 i 和城市 j 之间有边。 isConnected[i][j] == 0 表示城市 i 和城市 j 没有直接边。 示例 1 输入：isConnected = [ [1, 1, 0], [1, 1, 0], [0, 0, 1] ] 输出：2 城市 0 和城市 1 直接相连，所以它们属于同一个省份。 ...