本文共 1702 字，大约阅读时间需要 5 分钟。

1. 题目

如果一个整数上的每一位数字与其相邻位上的数字的绝对差都是 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

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

2.1 BFS

• 0 是特殊的，单独检查
• 然后从1-9开始入度，每次乘以10+末尾数（±1，为9的时候不加，为0的时候不减）

class Solution {
   	vector
   
     ans;public:    vector
    
      countSteppingNumbers(int low, int high) {
           if(low == 0) ans.push_back(0);        queue
     
       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

2.2 DFS

class Solution {
   	vector
   
     ans;public:    vector
    
      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

我的CSDN

长按或扫码关注我的公众号（Michael阿明），一起加油、一起学习进步！

转载地址：https://michael.blog.csdn.net/article/details/107581522 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！