Leetcode

相同组大小的人可以放在一起，但一个桶不一定就是一个组。用两个连续版本理解容量分组，并学会验证不唯一的答案。

用 Python 从两个字符串的异位词判断出发，先写出逐组扫描的正确解，再推导排序键与字符计数键，理解哈希表分组为什么成立。

重复的是文件内容，返回的却是完整路径。通过五个连续检查点，把输入解析、正确分组、哈希优化和平台提交串起来。

题目要求 给定整数数组 nums，找到一个乘积最大的非空连续子数组，返回这个最大乘积。 “连续”意味着选中的元素必须挨在一起，不能跳过中间的数；“非空”意味着至少选一个元素。只需返回乘积，不需要返回区间或区间长度。 输入：nums = [2, 3, -2, 4] 输出：6 解释：连续子数组 [2, 3] 的乘积最大，为 2 * 3 = 6。 输入：nums = [-2, 0, -1] 输出：0 解释：不能跳过 0，把 -2 和 -1 当作一个子数组；选择 [0] 可得到 0。 约束为 1 <= len(nums) <= 20000、-10 <= nums[i] <= 10。题目保证任意子数组的乘积都在 32 位有符号整数范围内。输入不会为空，但可能包含负数和零。 第 1 步：先枚举每个非空连续区间 对 [2, 3, -2, 4]，如果直接把整个数组乘起来，得到的是 -48，而答案是前两个元素的乘积 6。因此，当前“把所有元素相乘”的做法缺少真正需要做的选择：从哪里开始，到哪里结束。 先不尝试猜哪个区间更好。最直接的正确办法，是枚举每一个合法区间，计算乘积，再保留最大的值。 固定左端点 left 后，让右端点 right 逐个向右移动。原来区间的乘积只需再乘上新加入的 nums[right]，就能得到扩展后区间的乘积。这样每次扩展不必从头乘一遍。 加入这个完整的枚举函数： def max_product_bruteforce(nums: list[int]) -> int: answer = nums[0] for left in range(len(nums)): product = 1 for right in range(left, len(nums)): product *= nums[right] answer = max(answer, product) return answer 这里有两个不同的初始化： ...

题目要求 给定一个正整数 n，返回若干个正的完全平方数相加得到 n 时，所需的最少数量。完全平方数是整数的平方，例如 1 = 1²、4 = 2²、9 = 3²、16 = 4²。 和必须刚好等于 n。 同一个完全平方数可以使用任意次。 只返回数量，不需要返回具体分解；加数的先后顺序不影响答案。 约束：1 <= n <= 10^4。 输入：n = 12 输出：3 解释：12 = 4 + 4 + 4，需要 3 个完全平方数。 输入：n = 13 输出：2 解释：13 = 9 + 4，需要 2 个完全平方数。 下面使用 Python 3.9+ 逐步构建解法，适合已经理解函数、循环和基础递归，希望进一步理解动态规划的读者。 Step 1：先确定剩余和为 0 的答案 先拿最大的平方数，会不会让数量最少？对 n = 12，这一选择得到： 12 -> 先拿 9 -> 剩下 3 -> 再拿 1 + 1 + 1 总共：9 + 1 + 1 + 1，4 个 但是 4 + 4 + 4 只需要 3 个。当前的想法是“每次选不超过剩余和的最大平方数”，它在 12 上已经失败：单次拿得更多，不保证最后用得更少。 ...

题目要求 输入输出 输入：字符串 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。 ...