題目

難度：★★★☆☆
類(lèi)型：數(shù)組
方法：深度優(yōu)先搜索

傳送門(mén)

給定一個(gè)整數(shù) n, 返回從 1 到 n 的字典順序。

例如，

給定 n =1 3，返回 [1,10,11,12,13,2,3,4,5,6,7,8,9] 。

請(qǐng)盡可能的優(yōu)化算法的時(shí)間復(fù)雜度和空間復(fù)雜度。 輸入的數(shù)據(jù) n 小于等于 5,000,000。

解答

從解決問(wèn)題的角度來(lái)說(shuō)，python很友好：

class Solution:
    def lexicalOrder(self, n):
        return sorted(range(1, n+1), key=str)

但是從學(xué)習(xí)的角度來(lái)說(shuō)，我們用深度優(yōu)先搜索來(lái)做：

我們從1位數(shù)開(kāi)始，位數(shù)逐漸增加，用深度優(yōu)先搜索遍歷所有的情況：
1位數(shù)：0到9；
2位數(shù)：10到99:；
3位數(shù)：100到999；
...

定義結(jié)果列表，用于按題目要求順序添加整數(shù)，定義深度優(yōu)先搜索函數(shù)，函數(shù)輸入為10的倍數(shù)，在入口處設(shè)置判斷，排除已經(jīng)超過(guò)給定值的情況，然后將該數(shù)乘以10，研究以該數(shù)為十位數(shù)的所有數(shù)字。通過(guò)遞歸調(diào)用實(shí)現(xiàn)所有數(shù)字的添加。

class Solution:
    def lexicalOrder(self, n):
        res = []

        def dfs(cur):
            if cur > n:
                return
            else:
                res.append(cur)
                for i in range(10):
                    if 10 * cur + i > n:
                        return
                    dfs(10 * cur + i)

        for i in range(1, 10):
            dfs(i)

        return res

如有疑問(wèn)或建議，歡迎評(píng)論區(qū)留言~

有關(guān)更多力扣中等題的python解決方案，請(qǐng)移步力扣中等題解析