打印从1到最大的n位数

输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。

思路：

数字n代表n位十进制数，当n等于100的时候，就有100位十进制数，最大的数有100个9，int、long等是满足不了需求的。所以只能用字符串表示数字。

当n为1时，打印1,2,3,4,5,6,7,8,9。当n为2时，打印1,2,3,……,99。当n为3时，打印1,2,3,……,999。观察规律发现，其实就是有n个位置，每个位置从0到9取一遍。就可以得到答案。得到每一个字符串时，有可能出现0001等情况，此时多一步处理把前面的0去掉。

代码：

class PrintNumber {
private:
    vector<string> ans;
public:
    //去掉前面的0
    string prettyNumber(string& str) {
        string newS;
        bool zero = true;
        for(const auto& s:str) {
            if (s != '0') {
                zero = false;
            }
            if (zero == false) {
                newS.push_back(s);
            }
        }
        return newS;
    }
    //深度优先遍历每个位置
    void dfs(int n,string& str,int index) {
        if(index == n) {
            ans.emplace_back(prettyNumber(str));
            return;
        }
        for(int i = 0;i < 10;i++) {
            str[index] = '0'+i;
            dfs(n,str,index+1);
        }
    }
    vector<string> printNumbers(int n) {
        string s(n,'0');
        dfs(n,s,0);
        return ans;
    }
};