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.

链接：https://leetcode.com/problems/lexicographical-numbers/#/description

4/17/2017

自己的做法，超时

通过变为list of string，针对string排序，再转为list of integer

 1 public class Solution {
 2     public List<Integer> lexicalOrder(int n) {
 3         List<String> l = new ArrayList<String>();
 4         for (int i = 1; i <= n; i++) {
 5             l.add(Integer.toString(i));
 6         }
 7         Collections.sort(l);
 8         List<Integer> ret = new ArrayList<Integer>();
 9         for (int i = 0; i < l.size(); i++) {
10             ret.add(Integer.parseInt(l.get(i)));
11         }
12         return ret;
13     }
14 }

只好看别人的算法，真的是很厉害

https://discuss.leetcode.com/topic/55184/java-o-n-time-o-1-space-iterative-solution-130ms

加入某一值v之后，先判断v*10在不在范围内，若有，更新v接着计算10倍的值；若没有，并且v不是以9结尾，如果v+1在n的范围内就更新v值为v+1；若v是以9结尾，那么从尾向前找第一个不是9的位，然后将其＋1作为新的v

The basic idea is to find the next number to add.
Take 45 for example: if the current number is 45, the next one will be 450 (450 == 45 * 10)(if 450 <= n), or 46 (46 == 45 + 1) (if 46 <= n) or 5 (5 == 45 / 10 + 1)(5 is less than 45 so it is for sure less than n).
We should also consider n = 600, and the current number = 499, the next number is 5 because there are all "9"s after "4" in "499" so we should divide 499 by 10 until the last digit is not "9".
It is like a tree, and we are easy to get a sibling, a left most child and the parent of any node.

 1 public List<Integer> lexicalOrder(int n) {
 2         List<Integer> list = new ArrayList<>(n);
 3         int curr = 1;
 4         for (int i = 1; i <= n; i++) {
 5             list.add(curr);
 6             if (curr * 10 <= n) {
 7                 curr *= 10;
 8             } else if (curr % 10 != 9 && curr + 1 <= n) {
 9                 curr++;
10             } else {
11                 while ((curr / 10) % 10 == 9) {
12                     curr /= 10;
13                 }
14                 curr = curr / 10 + 1;
15             }
16         }
17         return list;
18     }

用DFS的做法，n叉树的DFS。个人比较喜欢的思路。

注意：2次循环是不同的，第一次从1开始，第二次是0开始。第一次是输出的第一个值，也是因为heading 0是不对的，在dfs里面代表的是非首位的选择，所以是从0到9

https://discuss.leetcode.com/topic/55377/simple-java-dfs-solution

 1 public class Solution {
 2     public List<Integer> lexicalOrder(int n) {
 3         List<Integer> res = new ArrayList<>();
 4         for(int i=1;i<10;++i){
 5           dfs(i, n, res); 
 6         }
 7         return res;
 8     }
 9     
10     public void dfs(int cur, int n, List<Integer> res){
11         if(cur>n)
12             return;
13         else{
14             res.add(cur);
15             for(int i=0;i<10;++i){
16                 if(10*cur+i>n)
17                     return;
18                 dfs(10*cur+i, n, res);
19             }
20         }
21     }
22 }

跟第一种解法类似，第11，12行的意思是比如n=23，当23做完之后下一个值应该是3，跟第14行很像，都是需要前进到之前的某个比自己小的值

https://discuss.leetcode.com/topic/55131/ac-200ms-c-solution-beats-98

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

Python大哥的贴子可以了解很多Python的细节，他的贴子和跟别人的讨论

https://discuss.leetcode.com/topic/55090/python-with-sorting

https://discuss.leetcode.com/topic/55118/python-with-dfs

以tree pre-order traversal来解题：

https://discuss.leetcode.com/topic/55196/recursive-java-solution-using-pre-order-traversal

 1 public class Solution {
 2     public List<Integer> lexicalOrder(int n) {
 3         List<Integer> res = new ArrayList<>();
 4         lexicalOrderHelper(res, 1, n);
 5         return res;
 6     }
 7 
 8     private void lexicalOrderHelper(List<Integer> res, int i, int n) {
 9         if(i > n) return;
10         res.add(i);
11         lexicalOrderHelper(res, i * 10, n);
12         if(i + 1 <= (i / 10) * 10 + 9) lexicalOrderHelper(res, i + 1, n);
13         else return;
14     }
15 }