[LeetCode] 386. Lexicographical Numbers

https://leetcode.com/contest/warm-up-contest/problems/lexicographical-numbers/

Solution:
The idea is to think in a "tree" like structure: the root is 0, then its leaves are from 1 to 9; then for the next layer, each element from the upper layer will has 10 leaves, respectively. For example, for 1 as the root, the 10 leaves for it will be 10, to 19; for 2 as the root, the 10 leaves will be 20 to 29; ... Then we just need to travel this "virtual tree" recursively by root-first and leaves-second way.

However, we may don't need to build a tree for this question, and we can do this in vector. But the idea is similar. Firstly, we will put 1-9 into the vector. Then we will iterate the vector from the beginning. For 1, we will add 10-19 after it; for 2, we will add 20-29 after it; ... Of course, all the newly added elements need to be no larger than n. See code below.

We can also use a queue structure to implement this. So the algorithm involved is some sort of BSF fashion. 

Code:

class Solution {
public:
    vector<int> lexicalOrder(int n) {
        vector<int> res;
        int l = min(n, 9);
        for(int i=1; i<=l; ++i) res.push_back(i);
        if(n>9){
            vector<int> t;
            int layer = 1;
            while(res.size()<n){
                 for(auto a:res){
                     t.push_back(a);
                     if(a>=layer && a*10<=n){
                         for(int j=0; j<=9; ++j){
                             int val = a*10 + j;
                             if(val<=n) t.push_back(val);
                             else break;
                         }
                     }
                 }
                 layer *=10;
                 res.clear();
                 res = t;
                 t.clear();
            }
        }
        return res;
    }
};