leetcode:Lexicographical Numbers

柔情只为你懂 2022-07-17 02:47 23阅读 0赞

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.

Subscribe to see which companies asked this question

给出一个数字n，列出这个数字 1- n内的字典顺序  
发现了一个情况  
我提交第一份递归代码的时候是没有通过的

public class Solution {
       public List<Integer> lexicalOrder(int n) {
                List<Integer> ans = new LinkedList<>();
                for(int i = 1; i < 10; ++i)
                    order(n, i, ans);
                return ans;
        }
    
         public void order(int n, int base, List<Integer> list){
             if(base > n){
                 return;
             }
             list.add(base);
             for(int i = 0; i < 10; ++i){
                 order(n, base * 10 + i,list);
             }
         }
    }

当改成static类变量的时候通过了

public class Solution {
       static List<Integer> ans = new LinkedList<>();
       public List<Integer> lexicalOrder(int n) {
            ans.clear();
            for(int i = 1; i < 10; ++i)
                order(n, i, ans);
            return ans;
        }
    
         public void order(int n, int base, List<Integer> list){
             if(base > n){
                 return;
             }
             list.add(base);
             for(int i = 0; i < 10; ++i){
                 order(n, base * 10 + i, list);
             }
         }
    }