967.连续差相同的数字

链接：967.连续差相同的数字
难度：Medium
标签：广度优先搜索、回溯
简介：返回所有长度为 n 且满足其每两个连续位上的数字之间的差的绝对值为 k 的 非负整数 。

题解 1 - cpp

• 编辑时间：2021-12-30
• 内存消耗：8.5MB
• 编程语言：cpp
• 解法介绍：dfs。

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

题解 2 - cpp

• 编辑时间：2022-02-18
• 内存消耗：8.3MB
• 编程语言：cpp
• 解法介绍：dfs。

class Solution {
   public:
    int n, k;
    vector<int> ans;
    void dfs(int cur, int cnt, int last) {
        if (cnt == 0) {
            ans.push_back(cur);
            return;
        }
        if (last + k < 10) dfs(cur * 10 + last + k, cnt - 1, last + k);
        if (k != 0 && last - k >= 0)
            dfs(cur * 10 + last - k, cnt - 1, last - k);
    }
    vector<int> numsSameConsecDiff(int n, int k) {
        this->n = n;
        this->k = k;
        for (int i = 1; i <= 9; i++) dfs(i, n - 1, i);
        return ans;
    }
};