难度: Medium
返回所有长度为 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运行时间: 27 ms
内存: 16.2 MB
class Solution:
def numsSameConsecDiff(self, n: int, k: int) -> List[int]:
res=[]
def dfs(bit,num,pos):
if pos==n:
res.append(num)
return
if bit+k<=9:
dfs(bit+k,num*10+bit+k,pos+1)
if bit-k>=0 and k!=0:
dfs(bit-k,num*10+bit-k,pos+1)
for i in range(1,10):
dfs(i,i,1)
return res
# if n==2:
# for i in range(10,99+1):
# if abs((i-i%10)//10-i%10)==k:
# res.append(i)
# else:
# def f(num1,num2):
# num=0
# for j in range(n):
# if j%2==0:
# num=num*10+num1
# else:num=num*10+num2
# return num
# for i in range(1,10):
# if i+k<=9:
# res.append(f(i,i+k))
# if i-k>=0 and k!=0:
# res.append(f(i,i-k))
这个题解采用了深度优先搜索（DFS）的方法来解决问题。首先，题解定义了一个递归函数 dfs，该函数用于构建满足条件的数字。函数的参数包括当前位的数字（bit）、到目前为止构建的数字（num）以及当前的位置（pos）。如果当前的位置等于n，意味着已经构建了一个长度为n的数字，将其添加到结果列表res中。否则，递归地尝试在当前数字后添加bit+k和bit-k（如果它们在0到9的范围内且合法）。整个搜索从1到9的每个数字开始，避免了前导零的问题。通过这种方式，可以生成所有符合条件的数字。
时间复杂度: O(2^n)
空间复杂度: O(n)
class Solution:
def numsSameConsecDiff(self, n: int, k: int) -> List[int]:
res = []
def dfs(bit, num, pos):
# Base case: if the number has reached the required digits (n), add to results
if pos == n:
res.append(num)
return
# If the next digit bit + k is valid, continue building the number
if bit + k <= 9:
dfs(bit + k, num * 10 + bit + k, pos + 1)
# If the next digit bit - k is valid and not the same as bit + k, continue building
if bit - k >= 0 and k != 0:
dfs(bit - k, num * 10 + bit - k, pos + 1)
# Start building numbers from each digit 1-9 to avoid leading zero
for i in range(1, 10):
dfs(i, i, 1)
return res
在DFS函数中确保生成的数字没有前导零是通过从1到9的每个数字开始递归搜索实现的。这意味着每个数字的第一位总是在1到9之间，从而排除了任何前导零的可能性。这种方法自然而然地避免了生成以0开头的数字，因为递归的起始点排除了0。
检查`bit + k <= 9`和`bit - k >= 0`是为了确保添加到数字中的每个新位都是有效的十进制数字（即介于0到9之间）。这些条件确保在递归过程中构造的数字不会包含非法的数字位。例如，如果`bit + k`的结果超过9或`bit - k`的结果小于0，则相应的位将不符合数字的标准格式，因此这些情况被排除在递归逻辑之外。
当`pos == n`时，意味着已经构建了一个长度为n的数字，此时将`num`添加到结果列表中是符合题目要求的。这里的基本情况确实考虑了所有边界条件，因为只有当数字长度恰好为n时，此数字才被认为是完全构建的并被添加到结果中。这个检查确保了不会有长度不足或过长的数字被添加到结果集。
当`k != 0`时，`bit - k`和`bit + k`产生的结果是不同的，这代表着数字可以在增加和减少的方向上拓展。但如果`k = 0`，则`bit + k`和`bit - k`都将产生相同的结果，即`bit`本身。这会导致重复的递归调用，因为两种情况下添加到数字中的值是一样的。为了避免这种不必要的重复和可能的性能问题，当`k = 0`时，只需考虑`bit + k`的情况，从而避免重复添加相同的数字位。