

LeetCode: 967. 连续差相同的数字

• LeetCode: 967. 连续差相同的数字
  • 1、题目描述
  • 2、解题思路

1、题目描述

返回所有长度为 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]

提示：

• $1 <= N <= 9$
• $0 <= K <= 9$

2、解题思路

• 从第一位开始生成
• 每次添加下一位有效位即可

class Solution:
    def numsSameConsecDiff(self, N, K):
        """
        :type N: int
        :type K: int
        :rtype: List[int]
        """
        if N == 1:
            return list(range(10))
        temp_set = set()
        for i in range(1, 10):
            if 0 <= i - K <= 9 or 0 <= i + K <= 9:
                temp_set.add(str(i))

        for i in range(1, N):

            next_step = set()

            for cur in temp_set:
                num = int(cur[-1])
                if 0 <= num + K <= 9:
                    next_step.add(cur + str(num + K))
                if 0 <= num - K <= 9:
                    next_step.add(cur + str(num - K))
            temp_set = next_step
        return list(map(int, temp_set))