Lexicographical Numbers Solutions in C++

// Source : https://leetcode.com/problems/lexicographical-numbers/
// Author : Hao Chen
// Date   : 2016-08-23


class Solution {
    
//Solution 1: convert the int to string for sort, Time complexity is high (Time Limited Error)
public:
    vector<int> lexicalOrder01(int n) {
        vector<int> result;
        for (int i=1; i<=n; i++) {
            result.push_back(i);
        }
        sort(result.begin(), result.end(), this->myComp);
        return result;
    }
private:
    static bool myComp(int i,int j) { 
        static char si[32]={0}, sj[32]={0};
        sprintf(si, "%d\0", i);
        sprintf(sj, "%d\0", j);
        return (strcmp(si, sj)<0); 
    }
    
    
//Solution 2 : using recursive way to solution the problem, 540ms
public:
    vector<int> lexicalOrder02(int n) {
        vector<int> result;
        for (int i=1; i<=n && i<=9; i++) {
            result.push_back(i);
            lexicalOrder_helper(i, n, result);
        }
        return result;
    }
    
private:
    void lexicalOrder_helper(int num, int& n, vector<int>& result) {
        for (int i=0; i<=9; i++) {
            int tmp = num * 10 + i;
            if (tmp > n) {
                break;
            }
            result.push_back(tmp);
            lexicalOrder_helper(tmp, n, result);
        }
    }

//Solution 3: no recursive way, but the code is not easy to read
public :
    vector<int> lexicalOrder03(int n) {
        vector<int> result;
        int curr = 1;
        while (result.size()<n) {
            // Step One
            // ---------
            //Adding all of the possible number which multiply 10 as much as possible 
            // such as: curr = 1, then 1, 10, 100, 1000 ...
            //          curr = 12, then 12, 120, 1200, ...
            for (; curr <= n; curr*=10 ) {
                result.push_back(curr);
            }
            
            // Step Two
            // ---------
            // After find the number which multiply 10 greater than `n`, then go back the previous one,
            // and keep adding 1 until it carry on to next number
            // for example:
            //    curr = 100, then we need evalute:  11,12,13,14,15,16,17,18,19, but stop at 20
            //    curr = 230, then we need evaluate: 24,25,26,27,28,29, but stop at 30.
            curr = curr/10 + 1;
            for (;  curr <= n &&  curr % 10 != 0; curr++) {
                result.push_back(curr);
            }

            // Step Three
            // ----------
            // Now, we finished all of the number, we need go back for next number
            // Here is a bit tricky.
            // 
            // Assuming the n is 234, and Step One evaluted 190, and Step Two, evaluted 191,192,...,199
            // Now, the `curr` is 200, and we need start from 2 instead of 20, that's why need keep dividing 10
            for (; curr%10 == 0; curr/=10);
           
        }
        return result;
    }
    
    
//start point
public:
    vector<int> lexicalOrder(int n) {
        srand(time(NULL));
        if (rand()%2) 
            return lexicalOrder02(n); // recursive way  560ms
        else 
            return lexicalOrder03(n); // non-recursive way, 460ms
    }

};

/// Source : https://leetcode.com/problems/lexicographical-numbers/description/
/// Author : liuyubobobo
/// Time   : 2017-10-16

#include <iostream>
#include <vector>

using namespace std;

/// Time Complexity: O(n)
/// Space Complexity: O(n)
class Solution {

public:
    vector<int> lexicalOrder(int n) {
        vector<int> res;
        for(int i = 1 ; i < 10 ; i ++)
            if(i <= n)
                generateRes(res, i, n);

        return res;
    }

private:
    void generateRes(vector<int>& res, int pre, int n){

        res.push_back(pre);
        for(int i = 0 ; i < 10 ; i ++)
            if(pre*10+i <= n)
                generateRes(res, pre*10+i, n);
    }
};

int main() {

    vector<int> res1 = Solution().lexicalOrder(13);
    for(int num: res1)
        cout << num << " ";
    cout << endl;

    vector<int> res2 = Solution().lexicalOrder(100);
    for(int num: res2)
        cout << num << " ";
    cout << endl;

    return 0;
}