386.Lexicographical-Numbers

386. Lexicographical Numbers

题目地址

https://leetcode.com/problems/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.

代码

Approach #1 DFS

Time: O(1) && Space: O(1)

public class Solution {
    public List<Integer> lexicalOrder(int n) {
        List<Integer> res = new ArrayList<>(n);
        //  from  1 to 9.
        //  0 is can't be a soution.
        dfs(1, 9, n, res);
        return res;
    }
    private void dfs(int start, int end, int n, List<Integer> res){
        // <= n make the solution can't bigger than n
        for (int i = start; i <= end && i <= n; i++){
            res.add(i);
            // 10 -> next recursion: 100(->next recursion 1000), 101,102....
            // next loop: 11 -> next recursion: 110,  111,112....
            // next loop: 12 -> next recursion: 120,  121,122....
            // from 0 to 9 different from the dfs call in method lexicalOrder
            dfs(i * 10, i * 10 + 9, n, res);
        }
    }
}

public class Solution {
    public List<Integer> lexicalOrder(int n) {
        List<Integer> res = new ArrayList<>();
        for(int i=1;i<10;++i){
          dfs(i, n, res); 
        }
        return res;
    }

    public void dfs(int cur, int n, List<Integer> res){
        if(cur>n)
            return;
        else{
            res.add(cur);
            for(int i=0;i<10;++i){
                if(10*cur+i>n)
                    return;
                dfs(10*cur+i, n, res);
            }
        }
    }
}

Approach #2 Iteration

public class Solution {
    public List<Integer> lexicalOrder(int n) {
        List<Integer> ans = new ArrayList<>(n);
        ans.add(1);
        for (int i = 1, prev = 1; i < n; ++i) {
            if (prev * 10 <= n) {
                prev *= 10;
            } else {
                while (prev % 10 == 9 || prev == n) prev /= 10;
                prev++;
            }
            ans.add(prev);
        }
        return ans;
    }
}