Hot100

题目要求 输入输出 输入：字符串 s 和字符串列表 wordDict wordDict 中的每个元素都是一个可以使用的单词；同一个单词可以重复使用 输出：如果 s 可以被拆成一个或多个字典单词，返回 True；否则返回 False 拆分必须覆盖整个字符串，不能跳过字符，也不能改变字符顺序 示例 输入：s = "leetcode", wordDict = ["leet", "code"] 输出：True 解释："leetcode" 可以拆成 "leet" + "code" 输入：s = "applepenapple", wordDict = ["apple", "pen"] 输出：True 解释："apple" + "pen" + "apple"；同一个单词可以重复使用 输入：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 中的单词互不相同 Step 1：先让“已完成的前缀”变得可见 先只问一个具体问题：对于 s = "leetcode"，在确认整串能否拆开之前，我们能不能先记录“已经拆完了哪一段”？ ...

题目要求 输入输出 输入：整数数组 nums，nums[i] 表示第 i 间房子的金额。 房子首尾相连，不能偷相邻的两间房子，因此第 0 间和第 n - 1 间也不能同时偷。 输出：在不触发警报的前提下，最多能偷到的金额。 约束：1 <= nums.length <= 100，0 <= nums[i] <= 1000。 示例 输入：nums = [2,3,2] 输出：3 解释：第 0 间和第 2 间首尾相邻，不能同时偷；选择金额 3 的房子。 输入：nums = [1,2,3,1] 输出：4 解释：可以偷下标 0 和下标 2，也可以偷下标 1 和下标 3。 输入：nums = [1,2,3] 输出：3 这篇只用 Python，先从最小的首尾冲突开始。 Step 1：先处理首尾相邻的冲突 先问一个具体问题：nums = [2,3,2] 时，能不能沿用直线街道的做法，直接在整个数组上选择不相邻的房子？ 当前基线只有一条规则：相邻房子不能同时偷。若把这三个数当成直线，可能会把下标 0 和下标 2 当成彼此不相邻，从而错误地选择两端，得到金额 4。 这在环形输入上就会失败：首尾也相邻，0 和 2 必须互斥。要消除这一个冲突，只增加一个分支规则：任何合法方案至少属于下面一个候选分支。 ...

题目要求 给定一个整数数组 coins，其中 coins[i] 是一种硬币的面额；再给定一个非负整数 amount，要求凑出刚好等于 amount 的金额。 每种硬币都可以使用任意次。 返回凑出 amount 所需的最少硬币数量。 如果无法凑出，返回 -1。 如果 amount = 0，不需要使用硬币，答案是 0。 约束是：1 <= coins.length <= 12、1 <= coins[i] <= 2^31 - 1、0 <= amount <= 10^4。硬币面额互不相同。 例如： 输入：coins = [1, 2, 5], amount = 11 输出：3 解释：5 + 5 + 1 一共使用 3 枚硬币。 输入：coins = [2], amount = 3 输出：-1 解释：只使用面额 2 无法凑出 3。 输入：coins = [1], amount = 0 输出：0 解释：目标金额已经是 0，不需要再选硬币。 Step 1：先把目标金额拆成更小的问题 先看一个会逼出问题结构的小例子： ...

题目要求 输入输出 输入：整数数组 nums 输出：返回 nums 的最长严格递增子序列长度 子序列保持原数组中的相对顺序，但不要求连续，可以跳过元素 如果选择的下标是 i_1 < i_2 < ... < i_k，还必须满足 nums[i_1] < nums[i_2] < ... < nums[i_k] 子序列非空，因此至少选择一个元素 约束：1 <= nums.length <= 2500，-10^4 <= nums[i] <= 10^4 示例 输入：nums = [10,9,2,5,3,7,101,18] 输出：4 解释：[2,5,7,101] 是一个长度为 4 的严格递增子序列；它不要求在原数组中连续。 输入：nums = [0,1,0,3,2,3] 输出：4 解释：[0,1,2,3] 的长度为 4；`[0,1,3]` 也是合法但更短的选择。 这篇只用 Python，从“每个位置结尾能形成多长”这个局部问题开始，逐步写出可运行解法。 Step 1：先问“以哪个位置结束？” 先看第一个例子： 下标： 0 1 2 3 4 5 6 7 数值： 10 9 2 5 3 7 101 18 答案 [2,5,7,101] 跳过了 9 和 3。当我们走到值为 7 的位置时，不能只问“它左边相邻的数是谁”，而要问： ...

题目要求 给定一个只包含正整数的数组 nums，判断能不能把所有元素分成两个子集，使两个子集的元素总和相等。 输入与输出 输入：整数数组 nums 输出：如果能平分，返回 True；否则返回 False 每个元素必须放入两个子集之一，不能丢弃，也不能把同一个元素使用两次 示例 输入：nums = [1,5,11,5] 输出：True 解释：[1,5,5] 和 [11] 的总和都是 11 输入：nums = [1,2,3,5] 输出：False 解释：总和是 11，奇数不能平分 输入：nums = [1,1] 输出：True 解释：两个子集分别拿一个 1 约束 按 LeetCode 416 题面： 1 <= nums.length <= 200 1 <= nums[i] <= 100 sum(nums) <= 20000 Step 1：先排除总和为奇数的数组 先问一个还不涉及选数的问题：两个整数子集的和相等时，整个数组的总和必须满足什么条件？ 问题压力 看 nums = [1,2,3,5]。它的总和是 11。如果两个子集的和都叫 x，那么必须有： 2 * x = 11 整数 x 不可能满足这个等式，所以这个输入可以在尝试任何选数之前直接判定为 False。 ...

题目要求 设计一个栈 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]，怎样先得到一个不受旋转位置影响的正确答案？ ...