Code & Fun

第73天。

今天的题目是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.

emmm,lexicographical是字典序的意思。

首先,这种有规律的题目一般用递归来写会比较简单(但是可能会超时),我们先找出它的规律,在不到n的时候,没加入一个数字i,我们就要看i*10 ~ i*10 + 9是否小于n,如果小于我们就把它加入,然后在递归的进行判断。

有一点需要注意的就是,它是从1开始的,所以我们一开始就要尝试的把1 ~ 9加入,而不是0 ~ 9

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
vector<int> lexicalOrder(int n) {
vector<int> ret;
//lexicalOrder(ret,n,1);
for(int i = 1;i < 10 && i <= n;i++) {
ret.push_back(i);
lexicalOrder(ret,n,i*10);
}
return ret;
}
void lexicalOrder(vector<int> &vec,int n,int base) {
for(int i = 0;i < 10;i++,base++) {
if (base > n){ return; }
vec.push_back(base);
lexicalOrder(vec,n,10*base);
}
}

然后是在dicuss中看到的迭代解法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
vector<int> lexicalOrder(int n) {
vector<int> res(n);
int cur = 1;
for (int i = 0; i < n; i++) {
res[i] = cur;
if (cur * 10 <= n) {
cur *= 10;
} else {
if (cur >= n)
cur /= 10;
cur += 1;
while (cur % 10 == 0)
cur /= 10;
}
}
return res;
}

本文首发于Code & Fun