[LeetCode] 967. Numbers With Same Consecutive Differences

[grandyang]

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]

Example 3:

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

Example 4:

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

Example 5:

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的多位数。其实这就是个拼数的问题，就一位一位来凑数字就行了，题目中说了n是大于等于2的，所以至少是个两位数，所以第一位数肯定不是0，所以把1到9放到数组中开始凑数字。总共n位，现在已经有了一位了，还需要凑 n-1 位，所以循环 n-1 次。在循环中，新建一个数组 cur，然后遍历 res 数组中的数字，用对 10 取余的方法取出末尾数字 digit，然后看 digit 加上k是否小于等于9，是的话将 digit+k 加到末尾位，并将新数组加入数组 cur。然后再判断，若k不等于0，且 digit 减k大于等于0，则将 digit-k 加到末尾位，并将新数组加入数组 cur。判断k不等于0的原因是为了避免 digit+k 和 digit-k 相等，从而产生重复结果。遍历完了结果 res 中的数字，将 res 更新为 cur 数组，参见代码如下：

解法一：

class Solution {
public:
    vector<int> numsSameConsecDiff(int n, int k) {
        vector<int> res{1, 2, 3, 4, 5, 6, 7, 8, 9};
        for (int i = 1; i < n; ++i) {
            vector<int> cur;
            for (int num : res) {
                int digit = num % 10;
                if (digit + k <= 9) cur.push_back(num * 10 + digit + k);
                if (k != 0 && digit - k >= 0) cur.push_back(num * 10 + digit - k);
            }
            res = cur;
        }
        return res;
    }
};

我们也可以使用递归的写法，对于每个起始数字1到9，都调用一个递归函数，整体思路和上面的迭代解法大同小异，可以参考上面的讲解，参见代码如下：

解法二：

class Solution {
public:
    vector<int> numsSameConsecDiff(int n, int k) {
        vector<int> res;
        for (int i = 1; i <= 9; ++i) {
            helper(i, n - 1, k, res);
        }
        return res;
    }
    void helper(int num, int n, int k, vector<int>& res) {
        if (n == 0) {
            res.push_back(num);
            return;
        }
        int digit = num % 10;
        if (digit + k <= 9) helper(num * 10 + digit + k, n - 1, k, res);
        if (k != 0 && digit - k >= 0) helper(num * 10 + digit - k, n - 1, k, res);
        
    }
};

Github 同步地址:

#967

参考资料：

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

https://leetcode.com/problems/numbers-with-same-consecutive-differences/discuss/211193/C%2B%2B-DFS

https://leetcode.com/problems/numbers-with-same-consecutive-differences/discuss/211183/JavaC%2B%2BPython-Iterative-Solution

LeetCode All in One 题目讲解汇总(持续更新中...)