题目描述
给你一个整数 n
,按字典序返回范围 [1, n]
内所有整数。
你必须设计一个时间复杂度为 O(n)
且使用 O(1)
额外空间的算法。
示例 1:
输入:n = 13
输出:[1,10,11,12,13,2,3,4,5,6,7,8,9]
示例 2:
输入:n = 2
输出:[1,2]
提示:
解法
方法一:DFS
1
2
3
4
5
6
7
8
9
10
11
12
13 | class Solution:
def lexicalOrder(self, n: int) -> List[int]:
def dfs(u):
if u > n:
return
ans.append(u)
for i in range(10):
dfs(u * 10 + i)
ans = []
for i in range(1, 10):
dfs(i)
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 | class Solution {
public List<Integer> lexicalOrder(int n) {
List<Integer> ans = new ArrayList<>();
for (int i = 1; i < 10; ++i) {
dfs(i, n, ans);
}
return ans;
}
private void dfs(int u, int n, List<Integer> ans) {
if (u > n) {
return;
}
ans.add(u);
for (int i = 0; i < 10; ++i) {
dfs(u * 10 + i, n, ans);
}
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14 | class Solution {
public:
vector<int> lexicalOrder(int n) {
vector<int> ans;
for (int i = 1; i < 10; ++i) dfs(i, n, ans);
return ans;
}
void dfs(int u, int n, vector<int>& ans) {
if (u > n) return;
ans.push_back(u);
for (int i = 0; i < 10; ++i) dfs(u * 10 + i, n, ans);
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 | func lexicalOrder(n int) []int {
var ans []int
var dfs func(u int)
dfs = func(u int) {
if u > n {
return
}
ans = append(ans, u)
for i := 0; i < 10; i++ {
dfs(u*10 + i)
}
}
for i := 1; i < 10; i++ {
dfs(i)
}
return ans
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 | impl Solution {
fn dfs(mut num: i32, n: i32, res: &mut Vec<i32>) {
if num > n {
return;
}
res.push(num);
for i in 0..10 {
Self::dfs(num * 10 + i, n, res);
}
}
pub fn lexical_order(n: i32) -> Vec<i32> {
let mut res = vec![];
for i in 1..10 {
Self::dfs(i, n, &mut res);
}
res
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 | /**
* @param {number} n
* @return {number[]}
*/
var lexicalOrder = function (n) {
let ans = [];
function dfs(u) {
if (u > n) {
return;
}
ans.push(u);
for (let i = 0; i < 10; ++i) {
dfs(u * 10 + i);
}
}
for (let i = 1; i < 10; ++i) {
dfs(i);
}
return ans;
};
|
方法二