笺札

131. 分割回文串 - Palindrome Partitioning 🎯 问题描述（来源于LeetCode） 描述： 给定一个字符串 s，将 s 分割成若干子串，使得每个子串都是回文串。 返回所有可能的分割方案。 说明： 子串是原字符串中连续的一段。 回文串是正读反读相同的字符串。 示例： 示例 1： 12输入: s = "aab"输出: [["a","a","b"],["aa","b"]] 示例 2： 12输入: s = "a"输出: [["a"]] 💻 解题思路 思路：回溯法（DFS）扩展子串 + 回文判断 算法步骤 获取字符串长度 n，初始化结果列表 ans 和当前路径列表 path。 定义递归函数 dfs(i, left)，其中 i 表示当前扫描到的右边界，left 表示当前子串的起始位置： 如果 i == n，说明所有字符已被分割完毕（此时 left == n），将 path 的...

784. 字母大小写全排列 - Letter Case Permutation 🎯 问题描述（来源于LeetCode） 描述： 给定一个字符串 s，通过将字符串中的每个字母转变大小写，我们可以获得一个新的字符串。 返回所有可能得到的字符串集合。 答案可以按任意顺序返回。 说明： 字母以外的字符（数字）保持不变。 大小写转换仅针对英文字母。 示例： 示例 1： 12输入: s = "a1b2"输出: ["a1b2", "a1B2", "A1b2", "A1B2"] 示例 2： 12输入: s = "3z4"输出: ["3z4", "3Z4"] 💻 解题思路 思路：回溯法（DFS） 算法步骤 将字符串 s 转换为字符列表 path（便于原地修改）。 定义递归函数 dfs(i)，表示当前处理到第 i 个字符： 如果 i == n，将当前 path 拼接成字符串加入答案列表，返回。 如果当前字符 pa...

78. 子集 - Subsets 🎯 问题描述（来源于LeetCode） 描述： 给定一个整数数组 nums，数组中的元素互不相同。返回该数组所有可能的子集（幂集）。 解集不能包含重复的子集，可以按任意顺序返回答案。 说明： 子集包括空集和原集合本身。 示例： 示例 1： 12输入: nums = [1,2,3]输出: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]] 示例 2： 12输入: nums = [0]输出: [[],[0]] 💻 解题思路 思路一：枚举“选哪个”（组合型回溯） 算法步骤 获取数组长度 n，初始化结果列表 ans 和当前路径列表 path。 定义递归函数 dfs(i)，表示当前考虑从下标 i 开始的元素进行选择： 首先将当前 path 的副本加入 ans（对应“不选后面的任何元素”）。 然后从 i 到 n-1 遍历元素：将 nums[j] 加入 path，递归调用 dfs(j+1)，然后弹出 path 最后一个元素（回溯）。 从 dfs(0) 开始搜索。 返回 ans。 思路一：代...

1863. 找出所有子集的异或总和再求和 - Sum of All Subset XOR Totals 🎯 问题描述（来源于LeetCode） 描述： 给定一个整数数组 nums，数组中的元素互不相同。 定义子集的异或总和为该子集中所有元素的按位异或（XOR）值。 请计算所有子集（包括空集）的异或总和之和，并返回结果。 说明： 空集的异或总和定义为 0。 示例： 示例 1： 123输入: nums = [1,3]输出: 6解释: 子集为：[], XOR=0；[1], XOR=1；[3], XOR=3；[1,3], XOR=2；总和=0+1+3+2=6。 示例 2： 12输入: nums = [5,1,6]输出: 28 💻 解题思路 思路一：回溯法（选或不选分支） 算法步骤 获取数组长度 n，初始化全局答案 ans = 0，当前异或值 path = 0。 定义递归函数 dfs(i)，表示处理到下标 i 的元素： 如果 i == n（所有元素都已处理），将 path 累加到 ans 并返回。 否则，进行两个分支： 不选 nums[i]：直接递归 dfs...

2698. 求一个整数的惩罚数 - Find the Punishment Number of an Integer 🎯 问题描述（来源于LeetCode） 描述： 给定一个正整数 n，返回 1 到 n 之间所有惩罚数的平方和。 惩罚数的定义为：若一个整数 i 的平方 i*i 的十进制表示可以分割成若干连续子串，使得这些子串对应的整数值之和等于 i，则 i 是惩罚数。 说明： 分割时子串必须连续，且必须使用所有数字。 例如 1 是惩罚数，因为 1²=1 可分割为 "1"，和为 1。 例如 9 是惩罚数，因为 9²=81 可分割为 "8"+"1"，和为 9。 示例： 示例 1： 123输入: n = 10输出: 182解释: 惩罚数为 1 和 9，平方和为 1+81=82？实际 LeetCode 示例输出为 82，请以题目为准。 示例 2： 123输入: n = 37输出: 1478解释: 惩罚数有 1, 9, 10, 36，平方和为 1+81+100+1296=1478。 💻 解题思路 思路：DF...

17. 电话号码的字母组合 - Letter Combinations of a Phone Number 🎯 问题描述（来源于LeetCode） 描述： 给定一个仅包含数字 2-9 的字符串 digits，返回所有它能表示的字母组合。答案可以按任意顺序返回。 数字到字母的映射如下（与电话按键相同）： 2: “abc” 3: “def” 4: “ghi” 5: “jkl” 6: “mno” 7: “pqrs” 8: “tuv” 9: “wxyz” 注意：1 不对应任何字母，0 也不对应。 说明： 输入字符串可能为空，此时返回空列表。 示例： 示例 1： 12输入: digits = "23"输出: ["ad","ae","af","bd","be","bf","cd","ce","cf"] 示例 2： 12输入: digits = ""输出:...

3566. 等积子集的划分方案 - Partition Array into Two Equal Product Subsets 🎯 问题描述（来源于LeetCode） 描述： 给定一个只包含不同正整数的数组 nums 和一个整数 target。你必须把 nums 所有元素分成两个非空且不相交的子集，每个元素恰好属于其中一个子集，使得两个子集的元素乘积都等于 target。若能找到则返回 true，否则返回 false。 说明： 每个元素只能属于其中一组，且两组都不能为空。 所有 nums 中的元素互不相同。 元素乘积可能非常大，需注意溢出（可使用 Python 大整数，或使用 target 的质因数分解优化，但本题数据范围小，暴力回溯即可）。 示例： 示例 1： 123输入: nums = [3,1,6,8,4], target = 24输出: true解释: 子集 [3, 8] 和 [1, 6, 4] 的乘积均为 24。 示例 2： 123输入: nums = [2,5,3,7], target = 15输出: false解释: 无法分割成两个乘积均为 15...

2684. 矩阵中移动的最大次数 - Maximum Number of Moves in a Grid 🎯 问题描述（来源于LeetCode） 描述： 给定一个 m x n 的整数矩阵 grid，从第一列的任意单元格出发，每次可以向右上、右、右下三个方向移动到相邻列，且要求目标单元格的值严格大于当前单元格的值。 问最多可以移动多少步（即到达的列数减1）？如果不能移动，返回 0。 说明： 每一步只能移动到下一列，不能停留在同一列。 行索引变化为 -1, 0, +1，列索引变化固定为 +1。 起点可以是第一列任意行。 示例： 示例 1： 123输入: grid = [[2,4,3,5],[5,4,9,3],[3,4,2,11],[10,9,13,15]]输出: 3解释: 可以从第0行第0列出发：2→4→9→15（步数3） 示例 2： 123输入: grid = [[3,2,4],[2,1,9],[1,1,7]]输出: 0解释: 无法从任何起点移动。 💻 解题思路 思路1：记忆化搜索（DFS + 缓存） 算法步骤 获取网格尺寸 m, n。 定义递归函数 d...

39. 组合总和 - Combination Sum 🎯 问题描述（来源于LeetCode） 描述： 给定一个无重复元素的整数数组 candidates 和一个目标整数 target，找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的数字可以无限制重复选取。 解集不能包含重复的组合（顺序不同的相同组合视为同一组合）。 说明： 所有数字（包括 target）都是正整数。 每个组合中的数字可以按任意顺序排列，但解集中不能有重复组合。 示例： 示例 1： 123输入: candidates = [2,3,6,7], target = 7输出: [[2,2,3],[7]]解释: 2+2+3=7，7=7。 示例 2： 12输入: candidates = [2,3,5], target = 8输出: [[2,2,2,2],[2,3,3],[3,5]] 💻 解题思路 思路：回溯法（DFS）允许重复选取 算法步骤 获取数组长度 n，初始化结果列表 ans 和当前路径列表 path。 定义递归函数 dfs(i, lea...

1905. 统计子岛屿 - Count Sub Islands 🎯 问题描述（来源于LeetCode） 描述： 给定两个 m x n 的二进制矩阵 grid1 和 grid2，其中 1 表示陆地，0 表示水域。 如果 grid2 中的一个岛屿（由四方向相连的 1 组成）的所有格子，在 grid1 的对应位置也都是陆地（即 grid1 中也全为 1），则称该岛屿是 grid2 的一个子岛屿。 请返回 grid2 中子岛屿的数量。 说明： 岛屿定义为四方向连通的 1 组成的区域。 子岛屿的所有格子必须在 grid1 中也是陆地，但 grid1 中可能存在额外的陆地（不在该岛屿内）。 示例： 示例 1： 1234输入: grid1 = [[1,1,1,0,0],[0,1,1,1,1],[0,0,0,0,0],[1,0,0,0,0],[1,1,0,1,1]], grid2 = [[1,1,1,0,0],[0,0,1,1,1],[0,1,0,0,0],[1,0,1,1,0],[0,1,0,1,0]]输出: 3解释: grid2 中有三个子岛屿（分别位于左上、右下...