LeetCode 题解工作台
连续差相同的数字
返回所有长度为 n 且满足其每两个连续位上的数字之间的差的绝对值为 k 的 非负整数 。 请注意， 除了 数字 0 本身之外，答案中的每个数字都 不能 有前导零。例如， 01 有一个前导零，所以是无效的；但 0 是有效的。 你可以按 任何顺序 返回答案。 示例 1： 输入： n = 3, k = 7…
2
题型
6
代码语言
3
相关题
当前训练重点
中等 · 回溯·pruning
答案摘要
我们可以枚举所有长度为 的数字的第一个数字，然后使用深度优先搜索的方法，递归地构造所有符合条件的数字。 具体地，我们首先定义一个边界值 $\textit{boundary} = 10^{n-1}$，表示我们需要构造的数字的最小值。然后，我们从 到 枚举第一个数字，对于每一个数字 ，我们递归地构造以 为第一个数字的长度为 的数字。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 回溯·pruning 题型思路
题目描述
返回所有长度为 n 且满足其每两个连续位上的数字之间的差的绝对值为 k 的 非负整数 。
请注意，除了 数字 0 本身之外，答案中的每个数字都 不能 有前导零。例如，01 有一个前导零，所以是无效的；但 0 是有效的。
你可以按 任何顺序 返回答案。
示例 1：
输入：n = 3, k = 7 输出：[181,292,707,818,929] 解释：注意，070 不是一个有效的数字，因为它有前导零。
示例 2：
输入：n = 2, k = 1 输出：[10,12,21,23,32,34,43,45,54,56,65,67,76,78,87,89,98]
示例 3：
输入：n = 2, k = 0 输出：[11,22,33,44,55,66,77,88,99]
示例 4：
输入：n = 2, k = 2 输出：[13,20,24,31,35,42,46,53,57,64,68,75,79,86,97]
提示：
2 <= n <= 90 <= k <= 9
解题思路
方法一：DFS
我们可以枚举所有长度为 的数字的第一个数字，然后使用深度优先搜索的方法，递归地构造所有符合条件的数字。
具体地，我们首先定义一个边界值 ，表示我们需要构造的数字的最小值。然后，我们从 到 枚举第一个数字，对于每一个数字 ，我们递归地构造以 为第一个数字的长度为 的数字。
时间复杂度 ，其中 表示数字集合，本题中 。空间复杂度 。
class Solution:
def numsSameConsecDiff(self, n: int, k: int) -> List[int]:
def dfs(x: int):
if x >= boundary:
ans.append(x)
return
last = x % 10
if last + k <= 9:
dfs(x * 10 + last + k)
if last - k >= 0 and k != 0:
dfs(x * 10 + last - k)
ans = []
boundary = 10 ** (n - 1)
for i in range(1, 10):
dfs(i)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(2^N) because each digit can generate up to two candidates for the next position, leading to exponential growth. Space complexity is also O(2^N) to store the valid sequences in the result array and the recursion or BFS queue. |
| 空间 | \mathcal{O}(2^{N}) |
面试官常问的追问
外企场景- question_mark
Can you optimize by pruning paths that violate the consecutive difference constraint?
- question_mark
How would you systematically generate all numbers without recursion stack overflow?
- question_mark
Do you handle edge cases like n-digit numbers starting with zero or k = 0?
常见陷阱
外企场景- error
Forgetting to disallow numbers with leading zeros, generating invalid numbers like 02 or 043.
- error
Not pruning early, causing unnecessary exploration and exponential time wastage.
- error
Misapplying the difference k, resulting in sequences where consecutive digits do not meet the required difference.
进阶变体
外企场景- arrow_right_alt
Find all numbers with consecutive differences forming an arithmetic sequence with variable differences per step.
- arrow_right_alt
Count the number of valid n-digit numbers without generating the actual numbers to optimize space.
- arrow_right_alt
Return numbers sorted in increasing order or with additional constraints like odd/even digit placement.