题目描述
如果一个整数上的每一位数字与其相邻位上的数字的绝对差都是 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
算法
(递归回溯) $O(2^{\log_{10} high} \cdot \log_{10} high)$
- 我们通过递归回溯的方式直接构造符合条件的数字。
- 特殊考虑
0
,如果low == 0
,则直接加入0
。 - 然后以字符串
1
到9
作为起始字符串开始递归回溯,每次最多有两种选择。 - 如果当前字符串组成的数字超过了
high
,则回溯。如果当前数字大于等于low
则加入到答案中。
时间复杂度
- 最多有 $\log_{10} high$ 层,每层最多两个选择,所以答案个数不会超过 $2^{\log_{10} high}$。
- 由于最后需要排序,所以时间复杂度为 $O(2^{\log_{10} high} \cdot \log_{10} high)$。
空间复杂度
- 答案数组需要 $O(2^{\log_{10} high})$ 的空间,递归系统栈和参数字符串需要 $O(\log_{10} high)$ 的空间。
- 故总空间复杂度为 $O(2^{\log_{10} high})$
C++ 代码
class Solution {
public:
void solve(string &s, long long cur, int low, int high, vector<int>& ans) {
if (cur > high)
return;
if (low <= cur) {
ans.push_back(cur);
}
int last = s.back() - '0';
if (last > 0) {
s += (last - 1) + '0';
solve(s, cur * 10 + (last - 1), low, high, ans);
s.pop_back();
}
if (last < 9) {
s += (last + 1) + '0';
solve(s, cur * 10 + (last + 1), low, high, ans);
s.pop_back();
}
}
vector<int> countSteppingNumbers(int low, int high) {
vector<int> ans;
if (low == 0)
ans.push_back(0);
for (int i = 1; i <= 9; i++) {
string s;
s += i + '0';
solve(s, i, low, high, ans);
}
sort(ans.begin(), ans.end());
return ans;
}
};
这里可以用队列做,避免排序,代码有点乱见谅,单周赛结束之后再来解释
这个从结果数组里找答案就相当于排序了,不过队列做还是可以的
如果我们生成全部的数字,生成的结果可以是排好序的。
差不多是这个意思,就是自然生成排好序的数字,就不用sort啦,由于比赛的时间比较紧,能AC就没来得及写。。。