原文链接: https://leetcode-cn.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. For example, 01 has one leading zero and is invalid.

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]

Example 3:

Input: n = 2, k = 0
Output: [11,22,33,44,55,66,77,88,99]

Example 4:

Input: n = 2, k = 2
Output: [13,20,24,31,35,42,46,53,57,64,68,75,79,86,97]

 

Constraints:

• 2 <= n <= 9
• 0 <= k <= 9

中文题目

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

统计信息

通过次数	提交次数	AC比率
8053	17162	46.9%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言