0967._Numbers_With_Same_Consecutive_Differences.md

967. Numbers With Same Consecutive Differences

难度: Medium

刷题内容

原题连接

• https://leetcode.com/problems/numbers-with-same-consecutive-differences/

内容描述

Return all non-negative integers of length N such that the absolute difference between every two consecutive digits is K.

Note that every number in the answer must not have leading zeros except for the number 0 itself. For example, 01 has one leading zero and is invalid, but 0 is valid.

You may return the answer in any order.

 

Example 1:

Input: N = 3, K = 7
Output: [181,292,707,818,929]
Explanation: Note that 070 is not a valid number, because it has leading zeroes.
Example 2:

Input: N = 2, K = 1
Output: [10,12,21,23,32,34,43,45,54,56,65,67,76,78,87,89,98]
 

Note:

1 <= N <= 9
0 <= K <= 9

解题方案

思路 1 - 时间复杂度: O((10-K)^N)- 空间复杂度: O(1)******

beats 100%

class Solution:
    def numsSameConsecDiff(self, N, K):
        """
        :type N: int
        :type K: int
        :rtype: List[int]
        """
        if N == 1:
            return [i for i in range(10)]
        if K == 0:
            return [int(str(i)*N) for i in range(1, 10)]
        
        self.res = []
        self.dfs('', N, K)
        return [int(i) for i in self.res]
    
    def dfs(self, path, N, K):
        if len(path) == 0:
            for i in range(1, 10):
                self.dfs(path+str(i), N, K)
            return

        if len(path) == N:
            self.res.append(path)
            return

        if int(path[-1]) + K <= 9:
            self.dfs(path + str(int(path[-1]) + K), N, K)
        if int(path[-1]) - K >= 0:
            self.dfs(path + str(int(path[-1]) - K), N, K)

又学到了，lee215

连那些corner case都全部考虑进去了，真的🐂p

class Solution:
    def numsSameConsecDiff(self, N, K):
        """
        :type N: int
        :type K: int
        :rtype: List[int]
        """
        cur = range(10)
        for i in range(N - 1):
            cur = {x * 10 + y for x in cur for y in [x % 10 + K, x % 10 - K] if x and 0 <= y <= 9}
        return list(cur)