LEETCODE 1215. Stepping Numbers 解题思路分析

题目大意:

步进数

如果一个整数上的每一位数字与其相邻位上的数字的绝对差都是 1,那么这个数就是一个 步进数。例如,321 是一个步进数,而 421 不是。

给你两个整数,low 和 high,请你找出在 [low, high] 范围内的所有步进数,并返回 排序后 的结果。

示例1:

输入:low = 0, high = 21
输出:[0,1,2,3,4,5,6,7,8,9,10,12,21]

提示:

  • 0 <= low <= high <= 2 * 10^9

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1215

解题思路分析:

这道题可以利用递归思路来解题。我们循环遍历所有以1开头,以2开头。。。,以9开头的数字,取得当前数字的末位数(个位),将末尾数加1或者减1(注意保证加减之后的数字在0-9之间),然后拼接到当前数字的末尾即可,如果拼接后的数字大于high,退出当前递归,如果在low和high区间内,将其加入结果集,如果小于high,继续递归。举个例子,比如:我们现从数字1开始循环,将数字1带入递归方法,这时,1的个位为1,我们可以在1后面接上2或者0,即:

1 -> 10
1 -> 12

接下来我们将10和12分别带入递归:

10 -> 101
// 10 -> 10(-1) 注意-1是不合理解

12 -> 121
12 -> 120

递归的结束条件是当前数大于high。当前递归结束后,继续循环下一位开头的数字(从1循环到9)。所有循环结束后,将返回结果排序即是答案。

实现代码:

List<Integer> res=new ArrayList<>(); // 返回结果
public List<Integer> countSteppingNumbers(int low, int high) {
    // 如果low为0,将0加入返回结果,因为以0开头的数只有0
    if(low==0) res.add(0);
    // 循环递归所有以1到9的数字
    for(int i=1;i<=9;i++) helper(low,high,i);
    Collections.sort(res); // 排序
    return res;
}

void helper(int low, int high, long current){
    // 如果当前数字大于high,结束递归
    if(current>high) return;
    // 如果当前数字大于等于low,加入结果集
    if(current>=low) res.add((int)current);
    // 取得当前数字的个位
    int lastDigit = (int)(current % 10);
    // 如果个位小于9,将个位加1后拼接到当前数后面,向下递归
    if(lastDigit<9){
        helper(low, high, current*10+lastDigit+1);
    }
    // 如果个位大于0,将个位减1后拼接到当前数后面,向下递归
    if(lastDigit>0){
        helper(low, high, current*10+lastDigit-1);
    }
}

本题解法执行时间为11ms。

Runtime: 11 ms, faster than 93.63% of Java online submissions for Stepping Numbers.

Memory Usage: 36.8 MB, less than 100.00% of Java online submissions for Stepping Numbers.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: https://leetcode.jp/leetcode-1215-stepping-numbers-解题思路分析/
此条目发表在leetcode分类目录,贴了, , 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。