当前位置：网站首页>386字典序排数，学会用递归的思想

386字典序排数，学会用递归的思想

2022-04-21 07:15:00 【糊涂不是傻】

刚拿到这个问题的时候，我想到的只是第一位字典序排序，所以我把第一位为1的数字按照从小到大的顺序排下去了，很明显这样是有问题的，下面举个例子：
1,10,11.。。。100，但是100应该是在10后面的，按照字典序的原则，0一样，这样的话单纯的迭代可能就解决不了这个问题了，因为每次在结果列表里面放入一个数之后，应该考虑比它位数多的数字里面有没有前几位和它一样的数。
想到这里我也想到了用链表来求解这个问题，因为链表在插入的时候只需要O（n）的复杂度，这个问题跟桶排序有点类似，但又有点不同，因为它不是排序，而是排数。
所以这题选用递归，因为递归这东西好用，比如我现在从10跳到了100，在100这里的递归结束之后还能再回到10，这就节省了后续搜索插入的时间。

class Solution:
    def lexicalOrder(self, n: int) -> List[int]:
        count = 0
        result = []
        def function(x,n):
            if x<=n:
                result.append(x)
                for i in range(x*10,x*10+10):
                    function(i,n)	#递归

        while(int(n/math.pow(10,count))>0):
            count+=1
        for j in range(1,10):
            function(j,n)
        return result

版权声明
本文为[糊涂不是傻]所创，转载请带上原文链接，感谢
https://blog.csdn.net/weixin_43872912/article/details/124305641

边栏推荐

猜你喜欢

随机推荐