跳转至

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

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))