【leetcode】967. 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

解题思路：题目本身很简单，利用BFS/DFS都可以。但是有两点要注意的，一是K = 0 的情况会造成重复（+0和-0的值一样），二是N等于1的时候，别忘了0也是其中一个结果。

解题思路：

class Solution(object):

    def numsSameConsecDiff(self, N, K):

        """

        :type N: int

        :type K: int

        :rtype: List[int]

        """

        res = []

        for i in range(1,10):

            queue = [str(i)]

            while len(queue) > 0:

                item = queue.pop(0)

                if len(item) == N:

                    res.append(item)

                    continue

                last = int(item[-1])

                if (last - K) >= 0:

                    queue.append(item + str(last - K))

                if K != 0 and abs(last + K) < 10:

                    queue.append(item + str(last + K))

        if N == 1:

            res.insert(0,'')

        return [int(i) for i in res]

巴特西

【leetcode】967. Numbers With Same Consecutive Differences

最新文章

热门文章