AI summary
type
status
date
slug
summary
category
tags
icon
password

967. 连续差相同的数字

返回所有长度为 n 且满足其每两个连续位上的数字之间的差的绝对值为 k 的 非负整数 。
请注意，除了 数字 0 本身之外，答案中的每个数字都 不能 有前导零。例如，01 有一个前导零，所以是无效的；但 0 是有效的。
你可以按 任何顺序 返回答案。
其实可以直接套框架秒掉对吧，其实就是考察前文 回溯算法描述排列组合的 9 种变体 中的「元素无重可复选的排列」。
看出来了么？相当于给你 n 个盒子，然后你有 0~9 种球（元素）可以放进盒子，每个盒子只能放一个球，但每种球的数量无限，可以使用无数次。
不过这道题比标准的「元素无重可复选的排列」多了两个剪枝逻辑：
  1. 第一个数字不能是 0，因为题目要求数字不能以 0 开头；
  1. 相邻两个数字的差的绝对值必须等于 k。
你把前文「元素无重可复选的排列」的代码框架 copy 过来，把这两个剪枝逻辑加上就行了，两分钟搞定。

980. 不同路径 III

在二维网格 grid 上，有 4 种类型的方格：
  • 1 表示起始方格。且只有一个起始方格。
  • 2 表示结束方格，且只有一个结束方格。
  • 0 表示我们可以走过的空方格。
  • 1 表示我们无法跨越的障碍。
返回在四个方向（上、下、左、右）上行走时，从起始方格到结束方格的不同路径的数目。
每一个无障碍方格都要通过一次，但是一条路径中不能重复通过同一个方格。
这道题不难，套回溯的框架直接出来了，真没啥可说的，我没太理解为啥这题难度是困难。
当然，可以通过记忆化搜索+状态压缩来优化。
用一个二进制数字 st 来表示路径还未经过的点（初始状态下为所有值为 0 的点和终点），点的坐标需要和二进制数字的位一一对应。定义函数 dp，输入参数为当前坐标 i,j 和未经过的点的二进制集合 st，返回值即为从点 (i,j) 出发，经过 st 代表的点的集合，最终到达终点的路径的条数。
由于暴力回溯已经 AC 了，懒得折腾了，代码略。

526. 优美的排列

假设有从 1 到 n 的 n 个整数。用这些整数构造一个数组 perm（下标从 1 开始），只要满足下述条件 之一 ，该数组就是一个 优美的排列 ：
  • perm[i] 能够被 i 整除
  • i 能够被 perm[i] 整除
给你一个整数 n ，返回可以构造的 优美排列 的 数量 。
这个题就是标准的回溯算法。要么站在索引的视角，让每个索引来选择元素；要么站在元素的视角，让每个元素来选择要去的索引。
不过考虑到本题中，元素和索引差不多，都是 1~n，所以这两种视角没有太大区别，我就写一个索引视角的回溯算法吧。
这里是把 track 设为实例变量，比第一题中作为回溯函数的参数效率略高。

491. 非递减子序列

给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。
数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。
其实这道题就是前文讲过的「元素可重不可复选」的组合问题。
只不过这里又有一个额外的条件：组合中所有元素都必须是递增顺序。我们只需要添加一个剪枝条件即可。
另外，前文是利用排序的方式防止重复使用相同元素的，但这道题不能改变 nums 的原始顺序，所以不能用排序的方式，而是用 used 集合来避免重复使用相同元素。
综上，只要把 40. 组合总和 II 的解法稍改一下即可完成这道题。
注意，这里的 used 集合是回溯函数内部的，表示减掉同一节点的相同孩子，不参与回溯过程。如下图所示：
notion image

131. 分割回文串

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
我们就按照最直接粗暴的方式思考就行了：
从 s 的头部开始暴力穷举，如果发现 s[0..i] 是一个回文子串，那么我们就可以把 s 切分为 s[0..i] 和 s[i+1..]，然后我们去尝试把 s[i+1..] 去暴力切分成多个回文子串即可。
PS: 至于如何判断一个字符串是否是回文串，我在 数组双指针技巧汇总 中的左右指针部分有讲解，很简单。
把这个思路抽象成回溯树，树枝上是每次从头部穷举切分出的子串，节点上是待切分的剩余字符串：
notion image
只有树枝上的子串是回文串时才能继续往下走，最后如果能够走到空串节点，就说明整个 s 完成了切分，也就是得到了一个合法的答案。
只要套用回溯算法框架，按照上述规则遍历整棵回溯树即可找到所有合法切分，直接看代码吧。

93. 复原 IP 地址

有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。
  • 例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。
给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。
做这道题之前我建议你先做一下 131. 分割回文串，因为稍微改改 131 题就可以解决这道题了。
131 题的要求是：让你把字符串 s 切分成若干个合法的回文串，返回所有的切分方法。
本题的要求是：让你把字符串 s 切分成 4 个合法的 IP 数字，返回所有的切分方法。
所以我们只要把 131 题的解法稍微改改，重写一个 isValid 函数判断合法的 IP 数字，并保证整棵回溯树只有 4 层（即 track 中只有 4 个子串）即可。
具体看代码吧，基本逻辑和 131 题一模一样。

89. 格雷编码

n 位格雷码序列是一个由 个整数组成的序列，其中：
  • 每个整数都在范围 [0, 2^n - 1] 内（含 0 和 2^n - 1）
  • 第一个整数是 0
  • 一个整数在序列中出现 不超过一次
  • 每对 相邻 整数的二进制表示 恰好一位不同 ，且
  • 第一个 和 最后一个 整数的二进制表示 恰好一位不同
给你一个整数 n ，返回任一有效的 n 位格雷码序列 。
不说数学相关的技巧，我们就用回溯算法框架暴力搜索，直接秒杀这道题。回溯树每个数字的子节点是对每个二进制位分别翻转得到的。
注意，题目只要求一个答案，所以找到答案后即可减掉剩下的所有树枝。
上面的暴力回溯算法 AC 地有些勉强，可以记一下公式：
二进制码→格雷码（编码）：
此方法从对应的n位二进制码字中直接得到n位格雷码码字，步骤如下：
  1. 对n位二进制的码字，从右到左，以0到n-1编号
  1. 如果二进制码字的第 i 位和 i+1 位相同，则对应的格雷码的第 i 位为 0，否则为 1（当 i+1=n 时，二进制码字的第 n 位被认为是 0，即第 n-1 位不变）

17. 电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
notion image
还是套框架，甚至不用剪枝，没什么好说的，秒了：

79. 单词搜索

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
这道题和 一文秒杀所有岛屿题目 中讲到的题目非常类似，递归暴力搜索就行了。
注意我们要对已经匹配过的字符做标记，比如用一个额外的 visited 布尔数组，或者使用其他方法标记 board 中已经匹配过的字符，比如改成小写，或者加上特殊符号。

473. 火柴拼正方形

你将得到一个整数数组 matchsticks ，其中 matchsticks[i] 是第 i 个火柴棒的长度。你要用 所有的火柴棍 拼成一个正方形。你 不能折断 任何一根火柴棒，但你可以把它们连在一起，而且每根火柴棒必须 使用一次 。
如果你能拼成这个正方形，则返回 true ，否则返回 false 。
这道题，说到底就是问是否可以把数组 matchsticks 分成 4 个和相等的子集。
前文 回溯算法实践 解决了集合划分问题。在集合划分问题中，我们实现了一个函数 canPartitionKSubsets，它的作用是判断是否能将一个数组分割成 k 个和相等的子集。
那么这道题就可以直接秒了，我们调用 canPartitionKSubsets(matchsticks, 4) 即可计算本题的答案。