[Leetcode]967. Numbers With Same Consecutive Differences (C++)

题目描述

题目链接：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.

例子

例子 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.

例子 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

解题思路

这道题本质上是一道找特定组合数字的问题，这样的题我们通常都可以用回溯来做，而且题目还说明了 N最大位数只有 9，不用担心会超时。回溯的基本思想就是在通过循环的调用自身，大体上满足这样一个套路：

0.如果当前数组已经符合要求，则添加进结果并返回 -> 这道题是看数字长度是否满足 N
1.往当前数组添加下一个可能的元素 -> 这道题是往数字后面添加当前最后一位数字 +/- K 的数字
2.在新添加的元素后面递归调用自身 -> 这道题是针对新产生的数字进行递归调用自身
3.上一步处理完成后，要把添加的元素推出去，恢复原来的状态 -> 这道题是将新增加的数字去掉
4.重复 1 步骤

除此之外，要注意一些 Edge cases,比如 N = 1 或者 K = 0 的情况，代码如下：

#include <vector>
#include <string>

class Solution {
public:
    std::vector<int> numsSameConsecDiff(int N, int K) {
        if (N == 1) {
            return {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
        }
        std::string curr_num;
        std::vector<int> candidates;
        for (int i = 1; i < 10; i++) {
            curr_num = std::to_string(i);
            findNumbers(N, K, curr_num, candidates);
        }
        return candidates;
    }

private:
    void findNumbers(int N, int K, std::string& curr_num, std::vector<int>& candidates) {
        if (curr_num.length() == N) {
            candidates.push_back(std::stoi(curr_num));
            return;
        }

        char last_digit = curr_num.back();
        char next_digit = last_digit - K;
        if (std::isdigit(next_digit)) {
            curr_num.push_back(next_digit);
            findNumbers(N, K, curr_num, candidates);
            curr_num.pop_back();
        }

        if (K != 0) {
            next_digit = last_digit + K;
            if (std::isdigit(next_digit)) {
                curr_num.push_back(next_digit);
                findNumbers(N, K, curr_num, candidates);
                curr_num.pop_back();
            }
        }
    }
};

时间复杂度：O(2^n)
空间复杂度：O(n) <- 不算输出结果的空间，只算堆栈产生的空间