如果一个整数上的每一位数字与其相邻位上的数字的绝对差都是 1,那么这个数就是一个「步进数」。
例如,321 是一个步进数,而 421 不是。
给你两个整数,low 和 high,请你找出在 [low, high] 范围内的所有步进数,并返回 排序后 的结果。
示例:
输入:low = 0, high = 21
输出:[0,1,2,3,4,5,6,7,8,9,10,12,21]
提示:
0 <= low <= high <= 2 * 10^9
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/stepping-numbers 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
class Solution {
vector<int> ans;
public:
vector<int> countSteppingNumbers(int low, int high) {
if(low == 0) ans.push_back(0);
queue<int> q;
for(int i = 1; i <= 9; ++i)
q.push(i);
long long tp, last;//防止溢出 longlong
while(!q.empty())
{
tp = q.front();
q.pop();
if(tp >= low && tp <= high)
ans.push_back(tp);
last = tp%10;
if(last!=0 && tp*10+last-1 <= high)
q.push(tp*10+last-1);
if(last!=9 && tp*10+last+1 <= high)//两个if顺序保证有序
q.push(tp*10+last+1);
}
return ans;
}
};
40 ms 14.5 MB
class Solution {
vector<int> ans;
public:
vector<int> countSteppingNumbers(int low, int high) {
if(low == 0) ans.push_back(0);
for(int i = 1; i <= 9; ++i)
dfs(i, low, high);
sort(ans.begin(), ans.end());
return ans;
}
void dfs(long long n, int low, int high)
{
int last = n%10;
if(n >= low && n <= high)
ans.push_back(n);
if(last!=0 && n*10+last-1 <= high)
dfs(n*10+last-1, low, high);
if(last!=9 && n*10+last+1 <= high)
dfs(n*10+last+1, low, high);
}
};
40 ms 13.7 MB