返回所有长度为 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]
|
提示：
C++
DP
class Solution {
public:
vector<int> numsSameConsecDiff(int n, int k) {
vector<vector<int>> dp(n);
dp[0] = {0,1,2,3,4,5,6,7,8,9};
for(int i = 1; i < n; i ++) {
for(auto e: dp[i - 1]) {
string s = to_string(e);
auto ss = s;
if(s[0] == '0') continue;
if(ss.back() - k - '0' >= 0) {
char temp = ss.back() - k;
ss += temp;
int t = stoi(ss);
dp[i].push_back(t);
}
if(k == 0) continue;
if(s.back() + k - '0' <= 9) {
char temp = s.back() + k;
s += temp;
int t = stoi(s);
dp[i].push_back(t);
}
}
}
return dp[n - 1];
}
};
|
回溯
class Solution {
public:
string path = "";
vector<int> res;
vector<int> numsSameConsecDiff(int n, int k) {
for(int i = 0; i <= 9; i ++){
path = "";
path += i + '0';
backtrack(n, k);
}
return res;
}
void backtrack(int n, int k) {
if(path.size() == n) {
if(path[0] != '0')
res.push_back(stoi(path));
return;
}
for(int i = 0; i <= 9; i ++) {
if(path.size() == 0 && i) path += i + '0';
if(abs(path.back() - i - '0') == k) {
path += i + '0';
backtrack(n, k);
path.pop_back();
}
}
}
};
|