0967-连续差相同的数字

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

方法一：暴力法

让我们尝试着一个数字一个数字的构造答案。

除了第一个数字外，每个数字最多有两种选择。这意味着 9 位的数字我们最多有 9 * 2^8 的情况。该可能性足够小到可以使用暴力法去解决它。

算法：

一个 N 位的数字可以看作 N-1 位数字加上最后一个数字。如果 N-1 位数字以数字 d 结尾，则 N 位数字将以 d-K 或 d+K 结尾（前提是这些数字在 [0,9] 范围内）。我们将这些数字存储在 Set 中，以避免重复。

另外，我们应该注意前导 0 – 只有 1 位数字以 0 开头。

[solution1-Python]

class Solution(object):
    def numsSameConsecDiff(self, N, K):
        ans = {x for x in range(1, 10)}
        for _ in xrange(N-1):
            ans2 = set()
            for x in ans:
                d = x % 10
                if d - K >= 0:
                    ans2.add(10*x + d-K)
                if d + K <= 9:
                    ans2.add(10*x + d+K)
            ans = ans2

        if N == 1:
            ans.add(0)

        return list(ans)

[solution1-Java]

class Solution {
    public int[] numsSameConsecDiff(int N, int K) {
        Set<Integer> cur = new HashSet();
        for (int i = 1; i <= 9; ++i)
            cur.add(i);

        for (int steps = 1; steps <= N-1; ++steps) {
            Set<Integer> cur2 = new HashSet();
            for (int x: cur) {
                int d = x % 10;
                if (d-K >= 0)
                    cur2.add(10*x + (d-K));
                if (d+K <= 9)
                    cur2.add(10*x + (d+K));
            }

            cur = cur2;
        }

        if (N == 1)
            cur.add(0);

        int[] ans = new int[cur.size()];
        int t = 0;
        for (int x: cur)
            ans[t++] = x;
        return ans;
    }
}

复杂度分析

• 时间复杂度：O(2^N)。
• 空间复杂度：O(2^N)。