Given an integer n, return 1 - n in lexicographical order.
For example, given 13, return: [1,10,11,12,13,2,3,4,5,6,7,8,9].
Please optimize your algorithm to use less time and space. The input size may be as large as 5,000,000.
Solution
递归的思路如下:
1
2
3
4
| def solve(m):
result.append(m)
if m * 10 <= n: solve(m * 10)
if m < n and m % 10 < 9: solve(m + 1)
|
(Lexicographical-Numbers.py) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution(object):
def lexicalOrder(self, n):
"""
:type n: int
:rtype: List[int]
"""
stack = [1]
ret = []
while stack:
top = stack.pop()
ret.append(top)
#各位数字小于9
# 一定要先插个位数字小于９的，再插top*10
if top < n and top % 10 < 9:
stack.append(top+1)
if top * 10 <= n:
stack.append(top*10)
return ret
|