笺札

213. 打家劫舍 II - House Robber II 🎯 问题描述（来源于LeetCode） 描述： 你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈，这意味着第一间房屋和最后一间房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被闯入，系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组 nums，请计算 在不触动警报装置的情况下，今晚能够偷窃到的最高金额。 说明： 环形：第一间和最后一间不能同时偷。 数组长度至少为 1。 示例： 示例 1： 123输入: nums = [2,3,2]输出: 3解释: 你不能先偷窃 1 号房屋（金额=2），然后偷窃 3 号房屋（金额=2），因为他们是相邻的。所以最优是偷 2 号房屋 (金额=3)。 示例 2： 123输入: nums = [1,2,3,1]输出: 4解释: 偷 1 号 (1) 和 3 号 (3) 得到 4；或者偷 2 号 (2) 和 4 号 (1) 得到 3。最大值是 4。 💻 解题思路 思路：环形问题拆解为...

198. 打家劫舍 - House Robber 🎯 问题描述（来源于LeetCode） 描述： 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组 nums，请计算不触动警报装置的情况下，一夜之内能够偷窃到的最高金额。 说明： 不能偷窃相邻的房屋。 数组长度至少为 1。 示例： 示例 1： 123输入: nums = [1,2,3,1]输出: 4解释: 偷窃 1 号房屋 (金额=1) ，然后偷窃 3 号房屋 (金额=3)。总金额 = 1+3 = 4。 示例 2： 123输入: nums = [2,7,9,3,1]输出: 12解释: 偷窃 1 号房屋 (2), 3 号房屋 (9)，接着偷 5 号房屋 (1)。总金额 = 2+9+1 = 12。 💻 解题思路 思路：动态规划 算法步骤 定义 dp[i] 表示偷窃前 i 间房屋（房屋编号从 1 到 i，即 nums[0..i-1]）能获得的最大金额。 初始化 ...

3693. 爬楼梯 II - Climbing Stairs II 🎯 问题描述（来源于LeetCode） 描述： 你正在爬一个楼梯，需要 n 阶才能到达楼顶。但是这次的楼梯有点特别，你不仅要支付每级台阶的成本 costs[i]，而且每次移动的代价和步数的平方成正比（即步数的平方）。题目的核心是求出从第 0 级台阶到第 n 级台阶的最小总成本。 说明： costs 数组的长度为 n，costs[i-1] 是第 i 级台阶的成本。 你一次可以向上爬 1、2 或 3 个台阶。 如果在一次移动中爬了 k 个台阶，除了到达的目标台阶成本外，还需要额外支付 k² 的步数成本。 起始点为第 0 级台阶，到达该点的初始成本为 0。 示例： 示例 1： 12345输入: n = 3, costs = [1, 2, 3]输出: 9解释: 从0开始：- 1步到1级：总成本 = 0 + 1² + costs[0] = 1 + 1 = 2- 1步到1级，再从1到3（2步）：总成本 = 2 + 2² + costs[2] = 2 + 4 + 3 = 9 示例 2： 12输入: n = 5...

377. 组合总和 Ⅳ - Combination Sum IV 🎯 问题描述（来源于LeetCode） 描述： 给你一个由不同整数组成的数组 nums 和一个目标整数 target。请你从 nums 中找出并返回总和为 target 的元素组合的个数。 题目数据保证答案符合 32 位整数范围。 说明： 顺序不同的序列被视作不同的组合（即排列）。 每个元素可以使用无限次。 示例： 示例 1： 12345678910输入: nums = [1,2,3], target = 4输出: 7解释: 所有组合为：(1,1,1,1)(1,1,2)(1,2,1)(1,3)(2,1,1)(2,2)(3,1) 示例 2： 12输入: nums = [9], target = 3输出: 0 💻 解题思路 思路：动态规划（爬楼梯思想） 算法步骤 定义 dp[i] 表示总和为 i 的组合个数。 初始化 dp[0] = 1（空组合）。 对于 i 从 1 到 target： 遍历 nums 中的每个数字 k，如果 k <= i，则 dp[i] += dp[i - k]（相...

2320. 统计放置房子的方式数 🎯 问题描述（来源于LeetCode） 描述： 给定一个长度为 n 的街道，街道两侧都有一排相同数量的地块。每侧的地块编号从 1 到 n。 你可以在每个地块上放置房子，但同一侧相邻地块不能同时放置房子（即不能有相邻的房子）。 两侧的放置是独立的，问有多少种放置方案。答案对 10^9+7 取模。 说明： 两侧可以放置不同数量的房子。 同一侧不能出现相邻的房子（类似打家劫舍的约束）。 示例： 示例 1： 123输入: n = 1输出: 4解释: 每侧有2种方案（放或不放），总方案数为 2*2=4。 示例 2： 123输入: n = 2输出: 9解释: 每侧方案数为3（00,01,10），总方案数 3*3=9。 💻 解题思路 思路：动态规划（斐波那契） + 独立乘法定理 算法步骤 先考虑单侧：在长度为 n 的一排地块上，不能放置相邻的房子，问有多少种放置方案。 这等价于经典的“房屋染色”问题，方案数满足斐波那契递推： 设 dp[i] 表示前 i 个地块的方案数。 若第 i 块不放房子，则方案数为 dp[i-1]。 若第 i...

2466. 统计构造好字符串的方法数 - Count Ways To Build Good Strings 🎯 问题描述（来源于LeetCode） 描述： 给你整数 low、high、zero 和 one。请你构造字符串，每次操作可以添加 zero 个 '0' 或添加 one 个 '1'。 求最终字符串的长度在 [low, high] 之间的不同构造方法数。答案对 10^9+7 取模。 说明： 空字符串是允许的初始状态。 每次操作必须添加恰好 zero 个 '0' 或恰好 one 个 '1'，不能部分添加。 示例： 示例 1： 123输入: low = 3, high = 3, zero = 1, one = 1输出: 8解释: 长度为3的字符串有8种（每位可以是0或1）。 示例 2： 123输入: low = 2, high = 3, zero = 1, one = 2输出: 5解释: 长度为2：00,11；长度为3：000,011,110；共5种。 💻 解题思路 思路：动态规划（爬楼梯变种） 算法步骤 定义 dp[i] 表示构造长度为 i 的字符串...

47. 全排列 II - Permutations II 🎯 问题描述（来源于LeetCode） 描述： 给定一个可包含重复数字的序列 nums，按任意顺序返回所有不重复的全排列。 说明： 序列中可能包含重复数字。 结果中不能有重复的排列。 示例： 示例 1： 12输入: nums = [1,1,2]输出: [[1,1,2],[1,2,1],[2,1,1]] 示例 2： 12输入: nums = [1,2,3]输出: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] 💻 解题思路 思路：回溯法（DFS） + 同一层去重 算法步骤 获取数组长度 n，初始化结果列表 ans、路径列表 path（长度为 n，预先分配空间）和 selected 布尔数组（标记元素是否已被使用）。 定义递归函数 dfs(i)，表示当前正在填充第 i 个位置（0‑indexed）： 如果 i == n，说明已填满所有位置，将 path 的副本加入 ans 并返回。 否则，使用一个集合 used 记录在当前递归层已经尝试过的元素值...

46. 全排列 - Permutations 🎯 问题描述（来源于LeetCode） 描述： 给定一个不含重复数字的数组 nums，返回其所有可能的全排列。你可以按任意顺序返回答案。 说明： 所有整数互不相同。 每个排列是数组中所有元素的一种顺序排列。 示例： 示例 1： 12输入: nums = [1,2,3]输出: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] 示例 2： 12输入: nums = [0,1]输出: [[0,1],[1,0]] 💻 解题思路 思路：回溯法（DFS） + 标记数组 算法步骤 获取数组长度 n，初始化结果列表 ans、当前路径列表 path 和 selected 布尔数组（标记元素是否已被使用）。 定义递归函数 dfs(i)，其中 i 表示当前已选中的元素个数（即 path 的长度）： 如果 i == n，说明已选中所有元素，将 path 的副本加入 ans 并返回。 否则，遍历每个元素的下标 j： 如果 selected[j] 为 False，则将该元素加入 p...

3799. 单词方块 II - Word Squares II 🎯 问题描述（来源于LeetCode） 描述： 给定一个字符串数组 words，每个单词长度固定为 4，且都由小写字母组成。 从 words 中选出 4 个互不相同 的单词，分别作为 top、left、right、bottom，并将它们排列成一个 2×2 的单词方块。 方块必须满足四个角上的字符对应相等： top[0] == left[0] （左上角） top[3] == right[0] （右上角） bottom[0] == left[3] （左下角） bottom[3] == right[3] （右下角） 返回所有满足条件的 4‑元组（top, left, right, bottom），结果按字典序升序排列。 说明： 每个单词只能使用一次。 单词列表中的单词互不相同。 示例： 12输入: words = ["area","lead","wall","lady","ball"]输出: [("w...

1286. 字母组合迭代器 - Iterator for Combination 🎯 问题描述（来源于LeetCode） 描述： 设计一个迭代器类 CombinationIterator，它接收一个字符串 characters（由不同的小写字母组成）和一个整数 combinationLength。 要求按字典序生成所有长度为 combinationLength 的组合（每个组合是 characters 中按原顺序的子序列），并提供 next() 和 hasNext() 方法。 说明： 组合中的字母顺序必须与 characters 中的顺序一致（即只能取子序列，不能重排）。 生成的组合按字典序排列（即相当于先按第一个字符排序，再按第二个，等等）。 示例： 12345输入:["CombinationIterator", "next", "hasNext", "next", "hasNext", "next", "hasNext"][[&...