连续差相同的数字-LeetCode

967. 连续差相同的数字 - Numbers With Same Consecutive Differences

🎯 问题描述（来源于LeetCode）

描述：
返回所有长度为 n 的非负整数（不含前导零），其相邻两个数字的差的绝对值恰好为 k。
可以按任意顺序返回答案。

说明：

• n 的范围是 [2, 9]（实际题目中 n 可能为 1，但本题要求长度为 n，且不含前导零，因此 n=1 时答案为 0..9，但通常 n≥2）。
• k 的范围是 [0, 9]。
• 结果中的整数不应有前导零（即第一位不能为 0）。

示例：

• 示例 1：

输入: n = 3, k = 7
输出: [181,292,707,818,929]
解释: 所有满足条件的3位数：1-8-1, 2-9-2, 7-0-7, 8-1-8, 9-2-9。

• 示例 2：

输入: n = 2, k = 1
输出: [10,12,21,23,32,34,43,45,54,56,65,67,76,78,87,89,98]

💻 解题思路

思路：回溯法（DFS）逐位构建

算法步骤

1. 初始化结果列表 ans。
2. 定义递归函数 dfs(path)，其中 path 是当前构建的数字字符串列表（或字符串）：
   • 如果 len(path) == n，将 path 拼接成整数并加入 ans，返回。
   • 否则，取出当前最后一位数字 last = int(path[-1])，计算下一个可能数字 r = last + k 和 l = last - k。
   • 如果 r <= 9，则递归 dfs(path + [str(r)])。
   • 如果 l != r 且 l >= 0，则递归 dfs(path + [str(l)])。
3. 枚举第一位数字从 1 到 9（避免前导零），对每个起始数字调用 dfs([str(i)])。
4. 返回 ans。

代码实现

from typing import List

class Solution:
    def numsSameConsecDiff(self, n: int, k: int) -> List[int]:
        ans = []
        def dfs(path):
            if len(path) == n:
                num = int("".join(path))
                ans.append(num)
                return
            last = int(path[-1])
            r = last + k
            l = last - k
            if r <= 9:
                dfs(path + [str(r)])
            if l != r and l >= 0:
                dfs(path + [str(l)])
        for i in range(1, 10):
            dfs([str(i)])
        return ans

📊 性能分析

• 时间复杂度：最坏情况下每个位置最多产生两个分支，因此总状态数约为 $9 \times 2^{n-1}$，对于 n ≤ 9 完全可行。
• 空间复杂度：$O(n)$，递归栈深度和路径存储。

思考

该解法通过回溯逐位构建数字，利用数学关系 last ± k 生成下一个数字，并自动处理边界条件（0 ≤ digit ≤ 9）。
优点：

• 代码简洁，直接模拟数字构建过程。
• 通过 l != r 避免重复添加相同数字（当 k=0 时，l == r，只添加一次）。
• 首位从 1 到 9 枚举，避免了前导零。