题目描述
如果一个整数上的每一位数字与其相邻位上的数字的绝对差都是 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
算法分析
DFS
1、通过直接找的方式来实现,而并非从low循环到high找
2、通过从一个数以及它的末尾数来找到下一个有效数,深度搜索
3、实现dfs方法,number表示给定的数,x表示该number的末尾数,high表示步进数的最小上界
4、调用dfs方法时
-
若x > 0 则搜索下一深度dfs(number * 10 + x - 1,x - 1,high) 例如: 32 得到下一个number为32 * 10 + 1 = 321
-
若x < 9 则搜索下一深度dfs(number * 10 + x + 1,x + 1,high) 例如: 32 得到下一个number为32 * 10 + 3 = 323
5、由于最后需要进行从小到大排序,所以用集合来收集,并且还需要将不在[low,high]范围内的数排除
注意:number需要使用long类型,否则number * 10 + x - 1或者number * 10 + x + 1会溢出
Java 代码
class Solution {
Set<Long> all = new HashSet<Long>();
public List<Integer> countSteppingNumbers(int low, int high) {
all.add(0l);
for (int i = 1; i < 10; i++) {
dfs(i,i,high);
}
List<Integer> res = new ArrayList<>();
for (long a: all) {
if (a >= low && a <= high) {
res.add((int)a);
}
}
Collections.sort(res);
return res;
}
//number表示传进来完整的数 x表示末尾数
public void dfs(long number,int x,int high)
{
if(number > high) return;
all.add(number);
if(x > 0) dfs(number * 10 + x - 1,x - 1,high);
if(x < 9) dfs(number * 10 + x + 1,x + 1,high);
}
}