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.
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]
Note:
1 <= N <= 90 <= K <= 9
class Solution {
public:
vector<int> numsSameConsecDiff(int N, int K){
vector<int> ans;
if (N == 1) ans.push_back(0);
for (int i = 1; i <= 9; i++)
dfs(N - 1, K, i, ans);
return ans;
}
private:
void dfs(int N, int K, int cur, vector<int>& ans) {
if (N == 0) {
ans.push_back(cur);
return;
}
int last = cur % 10;
if (last + K <= 9)
dfs(N - 1, K, cur * 10 + (last + K), ans);
if (last - K >= 0 && K != 0)
dfs(N - 1, K, cur * 10 + (last - K), ans);
}
};
-------------------------------------------------------------------------------------
class Solution {
public:
vector<int> numsSameConsecDiff(int N, int K){
// vector<int> v,res;
// int i=1;
// if(K<6)
// {
// while(i<10){
// v.push_back(i);
// ++i;
// }
// }
// else
// {
// v.push_back(1);
// v.push_back(K);
// i=1;
// if(i+K<10)
// v.push_back(i+K);
// ++i;
// while(i+K<10)
// {
// v.push_back(i));
// v.push_back(i+K);
// ++i;
// }
// }
// for(int i=0;i<N-1;++i)
// {
// int n=v.size();
// for(int j=0;j<n;++j)
// {
// int x=v[j]%10;
// if(x-K>=0)
// res.push_back(v[j]*10+(x-K));
// if(x+K<10)
// res.push_back(v[j]*10+(x+K));
// }
// v.clear();
// sort(res.begin(),res.end());
// auto ip=unique(res.begin(),res.end());
// res.resize(distance(res.begin(),ip));
// v=res;
// res.clear();
// }
// vector<int> ans;
// if(N==1)
// {
// return {0,1,2,3,4,5,6,7,8,9};
// }
//
// if(N==1)
// ans.push_back(0);
// return ans;
// }
};
