C++, O(n) time, O(1) space, finite state machine, 192ms


  • 0
    A

    I use a finite state machine to know the current state.
    Now we have three things to do.
    State 0. Add zeros as more as possible
    State 1. Increment the number
    State 2. When the number has a carry bit, remove all zeros, return to state 0. Or, if the number equals to the input, divide it by ten (I did it in state 0)

    class Solution {
    public:
        vector<int> lexicalOrder(int n) {
            vector<int> answer;
            if(n < 1) return answer;
            int num = 1;
            
            int state = 0;
            int cnt = n;
            
            while(cnt != 0){
                switch(state){
                    case 0: // Append zero
                        if(num <= n){
                            answer.push_back(num);
                            cnt--;
                            num *= 10;
                        }
                        else{
                            num /= 10;
                            state = 1;
                        }
                        break;
                    case 1: // Increasing
                        if(num % 10 != 9 && num < n ){
                            num++;
                            answer.push_back(num);
                            cnt--;
                        }
                        else{
                            num++;
                            state = 2;
                        }
                        break;
                    case 2: // If carry bit is necessary, remove all zeros.
                        while(num % 10 == 0){
                            num /= 10;
                        }
                        state = 0;                    
                }    
            }
            return answer;
        }
    };
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.