386 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.

Solution

class Solution {
public:
    vector<int> lexicalOrder(int n) {
        vector<int> res(1, 1);
        while ( int(res.size()) < n ) {
            int last = res[res.size()-1];
            if ( last*10 <= n ) {res.push_back(last*10); continue;}
            while ( last != 0 ) {
                if ( last%10 != 9 and last+1 <= n) { res.push_back(last+1); break;}
                last /= 10;
            }
        }
        return res;
    }
};

自己想出来的解法哈哈，不过在处理last+1的时候有点小疏忽，一开始是直接用last+1作为下一个数的candidate，如果不valid就往前挪一位（last /= 10）再+1。给了13这个例子的时候并没有问题，但是在给了34这样的例子的时候，19之后就添加了20而不是我们想要的2。这里就额外判断last最后一位是不是9，如果是9也往前挪一位。