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.
一道没有标签的题，第一个想到的思路就是深度优先搜索。很直接的把0-9的数字都想象成节点，每个节点下面又连着0-9的节点。这样开始从0遍历到9（除了最开始是从1遍历），每遇到一个节点就继续遍历和它连通的0-9的节点，直到到达n。用图的思想想这道题非常的简单，也很清晰。直接上代码，见解法一。
如果用一个比较大的数观察一下添加数字的顺序，比如112，不难发现一些规律。每次添加完一个数字，下一个数字总是对应着几种情况（下一个数字一定要比n小）：
1. 上次添加过的数字的10倍；
2. 上次添加过的数字+1；
3. 上次添加过的数字除以10（整数除法）+1。
同时这三种情况如果都小于n，那么总是按照上面的顺序依次添加。以112为例，添加完数字1之后，情况1的10，情况2的2，以及情况三的1都符合条件，那么就要首先添加情况1的10。这样添加完，下一个需要添加的数字就是基于10而继续根据情况1，2，3产生的数字。如果情况1不满足，自然要添加情况2产生的数字。那什么时候从情况2转化成情况3呢？通过观察，从情况2到情况3的转化永远发生在个位数为9，或者当上一个添加的数是n的情况。转化完成之后，继续按照情况1，2，3的顺序添加下一个数字。
总结完规律，只要按规律连续添加n个数即可。见解法二。
解法一（Java）
class Solution { public List<Integer> lexicalOrder(int n) { List<Integer> res = new ArrayList<>(n); for (int i = 1; i <= 9; i++) { if (i > n) break; dfs(i, res, n); } return res; } private void dfs(int i, List<Integer> res, int n) { res.add(i); for (int m = 0; m <= 9; m++) { if (i * 10 + m > n) break; dfs(i * 10 + m, res, n); } } }
解法二（Java）
class Solution { public List<Integer> lexicalOrder(int n) { List<Integer> res = new ArrayList<>(n); res.add(1); int pre = 1; for (int i = 1; i < n; i++) { if (pre * 10 <= n) pre *= 10; else { while (pre % 10 == 9 || pre == n) pre /= 10; pre++; } res.add(pre); } return res; } }