leetcode-386

发表于   |   分类于

Lexicographical Numbers

题目戳这

题意

给定一个n，将1-n共n个数字按照字典序排序。

解法

有两种解法，一种是用递归，一种直接循环即可。。

无论是啥，首先我们得知道这个题目的思路。既然按照字典序，我们首先举个n=100的例子

1
2
3
4
5
6
7
8
9
10
[1,10,100,11,12,13,14,15,16,17,
18,19,2,20,21,22,23,24,25,26,
27,28,29,3,30,31,32,33,34,35,
36,37,38,39,4,40,41,42,43,44,
45,46,47,48,49,5,50,51,52,53,
54,55,56,57,58,59,6,60,61,62,
63,64,65,66,67,68,69,7,70,71,
72,73,74,75,76,77,78,79,8,80,
81,82,83,84,85,86,87,88,89,9,
90,91,92,93,94,95,96,97,98,99]

从上面我们可以看出，首先一个给定当前的数字cur,那么我们首先看cur*10是否<=n，如果满足条件，那么我们肯定首先取cur*10，因为它的字典序最小，否则我们就看当前数字是否是以9结尾的，如果不是9结尾的且cur+1<=n，那么取cur+1。如果是以9结尾的，比如看59这个数字，后面跟的是6，就是将59//10+1，就是要对10取商取到结尾不为9的时候，然后+1.

这上面其实是循环的思路，递归的思路其实是一样的。就是枚举数字的开头，也就是1-9，然后如果对枚举的数字*10+i(0<=i<10)，符合条件的就递归。

代码

非递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution(object):
    def lexicalOrder(self, n):
        """
        :type n: int
        :rtype: List[int]
        """
        nlist = []
        cur = 1
        for i in range(1,n+1):
            nlist.append(cur)
            if cur*10 <= n:
                cur *= 10
            elif cur%10 != 9 and cur+1 <= n:
                cur += 1
            else:
                while (cur//10)%10 == 9:
                    cur //= 10
                cur = cur//10 + 1
        # print n
        return nlist

递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(object):
    def dfs(self,cur,n,nlist):
        if cur>n:
            return
        else:
            nlist.append(cur)
            for i in range(0,10):
                if 10*cur+i > n:
                    return
                self.dfs(10*cur+i,n,nlist)
    def lexicalOrder(self, n):
        """
        :type n: int
        :rtype: List[int]
        """
        nlist = []
        for i in range(1,10):
            self.dfs(i,n,nlist)
        
            
        return nlist