难度：★★★☆☆
类型：数组
方法：队列

题目

力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录

返回所有长度为 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 <= 9
0 <= k <= 9

解答

我们用队列来解决这个问题。

准备一个队列，并初始化为10个列表，列表中都包含从0到9的一个数字，队列中每个元素都是列表的原因是，我们要根据n的数值来添加位，直接用数字表示是不好算的，因此用整数列表来表征一个数字的各个位。

代表数字的列表从队列中一个个出队，需要做下面的判断：

第一，特殊情况，也就是列表中的数字的个数已经达到n，这意味着，这个列表代表的数字已经满足位数条件，可以加入到结果中了；

第二，除了上面的特殊情况，还需要做下面的分类：

2.1 如果k是零，说明最后需要所有数字的每一位都是一样的，也就是列表中的每个元素都一样，因此，需要将当前列表lst最后一位数字复制一遍，并加入到本身的结尾；

2.2 如果k不是零，就需要判断，对于lst中的最后一位数字，加上或者减去k以后，是否能够满足在0到9区间，如果可以，则将加上或者减去k以后的数字添加到当前列表中。

我们用while循环来循环的终止，只要队列中还有元素，就要进行上面的流程，每轮流程结束后，满足条件的新列表需要及时的加入到队尾中。

class Solution:
    def numsSameConsecDiff(self, n: int, k: int):
        def merge(lst):
            s = 0
            for num in lst:
                s = s * 10 + num
            return s

        queue = []
        for i in range(1, 10):
            queue.append([i])
        res = []
        while queue:
            lst = queue.pop(0)
            if len(lst) == n:
                res.append(merge(lst))
            elif k == 0:
                lst.append(lst[-1])
                queue.append(lst)
            else:
                if lst[-1] - k >= 0:
                    t = lst.copy()
                    t.append(t[-1] - k)
                    queue.append(t)
                if lst[-1] + k < 10:
                    t = lst.copy()
                    t.append(t[-1] + k)
                    queue.append(t)
        return res

如有疑问或建议，欢迎评论区留言~

有关更多力扣中等题的python解决方案，请移步力扣中等题解析