Leetcode 1215:步进数(超详细的解法!!!)
in leetcode with 0 comment

Leetcode 1215:步进数(超详细的解法!!!)

in leetcode with 0 comment

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

例如,321 是一个步进数,而 421 不是。

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

示例:

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

提示:

解题思路

首先不难先出暴力解法,也就是遍历[low,high]这个区间中的每个数,然后判断其是不是步进数即可。

class Solution:
    def countSteppingNumbers(self, l: int, r: int) -> List[int]:
        def check(x):
            pre, cur = x%10, 0
            x //= 10
            while x:
                cur = x%10
                if abs(pre - cur) != 1:
                    return False
                x //= 10
                pre = cur
            return True
        
        return [i for i in range(l, r + 1) if check(i)]

但是这么做的话会超时。我们首先分析一下这个问题,对于给定的数$U$,如果它最后一位是$l_t$,那么可以通过它产生两个步进数$U*10+l_t+1$和$U*10+l_t-1$。那么我们可以遍历[0,9],通过这10个数来生成所有的步进数。这实际上是一个DFS的问题。

另外,还需要思考两个边界,也就是当U==0U==9的时候。当U==0时,此时只可以产生一个步进数$U*10+l_t+1$;当U==9的时候,此时也只可以产生一个步进数$U*10+l_t-1$。

from functools import lru_cache
class Solution:
    def countSteppingNumbers(self, l: int, r: int) -> List[int]:
        res = []
        @lru_cache(None)
        def dfs(s):
            if s == 0 or s > r:
                return 
            if s <= r and s >= l:
                res.append(s)
                
            lt = s % 10
            s1, s2 = s * 10 + lt - 1, s*10 + lt + 1
            if lt == 0:
                dfs(s2)
            elif lt == 9:
                dfs(s1)
            else:
                dfs(s1)
                dfs(s2)
                
        for i in range(10):
            dfs(i)
        return sorted(res)

当然我们也可以通过bfs来处理。

class Solution:
    def countSteppingNumbers(self, l: int, r: int) -> List[int]:
        res = []
        def bfs(s):
            q = [s]
            while len(q):
                pre = q.pop(0)
                if pre <= r and pre >= l:
                    res.append(pre)
                if pre == 0 or pre > r:
                    return   

                lt = pre % 10
                s1, s2 = pre * 10 + lt - 1, pre*10 + lt + 1
                if lt == 0:
                    q.append(s2)
                elif lt == 9:
                    q.append(s1)
                else:
                    q.append(s1)
                    q.append(s2)
                
        for i in range(10):
            bfs(i)
        return sorted(res)

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题,希望大家指出!!!

「如果我的文章对你有很大帮助,那么不妨~!」

coordinate

谢谢老板O(∩_∩)O~

使用微信扫描二维码完成支付

Responses