## 题目描述：

LeetCode 386. Lexicographical Numbers

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.

## 解题思路：

```def solve(m):
result.append(m)
if m * 10 <= n: solve(m * 10)
if m < n and m % 10 < 9: solve(m + 1)```

## Java代码：

``````public class Solution {
private List<Integer> result;
private int n;
public List<Integer> lexicalOrder(int n) {
this.result = new ArrayList<Integer>();
this.n = n;
solve(1);
return result;
}
private void solve(int m) {
if (m * 10 <= n) solve(m * 10);
if (m < n && m % 10 < 9) solve(m + 1);
}
}
``````

## Python代码：

``````class Solution(object):
def lexicalOrder(self, n):
"""
:type n: int
:rtype: List[int]
"""
result = []
def solve(m):
result.append(m)
if m * 10 <= n: solve(m * 10)
if m < n and m % 10 < 9: solve(m + 1)
solve(1)
return result
``````

## Python代码：

``````class Solution(object):
def lexicalOrder(self, n):
"""
:type n: int
:rtype: List[int]
"""
result = []
stack = [1]
while stack:
y = stack.pop()
result.append(y)
if y < n and y % 10 < 9:
stack.append(y + 1)
if y * 10 <= n:
stack.append(y * 10)
return result
``````

## Python代码：

``````class Solution(object):
def lexicalOrder(self, n):
"""
:type n: int
:rtype: List[int]
"""
result = []
stack = []
x = 1
while x <= n:
stack.append(x)
result.append(x)
x *= 10
while stack:
y = stack.pop()
if y % 10 == 9: continue
y += 1
while y <= n:
stack.append(y)
result.append(y)
y *= 10
return result
``````

Pingbacks已关闭。