LeetCode 1215. 步进数(BFS/DFS)
发布日期:2021-07-01 03:30:08
浏览次数:2
分类:技术文章
本文共 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 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
哈哈,博客排版真的漂亮呢~
[***.90.31.176]2024年04月21日 08时29分51秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
Android--W/System.err: java.net.UnknownServiceException: CLEARTEXT communication to 10.114.35.103
2019-05-02
休息的艺术
2019-05-02
计算机科学经典文章
2019-05-02
Python 大全
2019-05-02
在python 解释器中学习linux系统函数调用
2019-05-02
[bash]: 删除代码注释
2019-05-02
Vmware虚拟机下三种网络模式配置
2019-05-02
今日整理PDF电子书资料
2019-05-02
在赛凡新的Warmup!
2019-05-02
Dtrace 资源库 URL 大全
2019-05-02
C问题集
2019-05-02
Bash 编程问题集
2019-05-02
怎么样学习代码
2019-05-02
URL: 技术图书清单
2019-05-02