剑指 Offer 17. 打印从1到最大的n位数

难度简单88
输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。
示例 1:
输入: n = 1
输出: [1,2,3,4,5,6,7,8,9]
说明：

  • 用返回一个整数列表来代替打印
  • n 为正整数
    1. class Solution {
    2. public:
    3.   void DFS(int index, int len, vector<int>& ans, string& s){
    4.       if(index == len){
    5.           int x = stoi(s);
    6.           if(x != 0)
    7.               ans.emplace_back(x);
    8.           return;
    9.       }
    10.       for(int i = 0; i <= 9; ++ i){
    11.           s[index] = '0' + i;
    12.           DFS(index + 1, len, ans, s);
    13.       }
    14.   }
    15.   vector<int> printNumbers(int n) {
    16.       vector<int> ans;
    17.       string s(n, '0');
    18.       DFS(0, n, ans, s);     
    19.       return ans;
    20.   }
    21. };
    或者
    1. class Solution {
    2. public:
    3.   void DFS(int index, int len, vector<int>& ans, string& s){
    4.       if(index == len){
    5.           turnToInt(ans, s);
    6.           return;
    7.       }
    8.       for(int i = 0; i <= 9; ++ i){
    9.           s[index] = '0' + i;
    10.           DFS(index + 1, len, ans, s);
    11.       }
    12.   }
    13.   void turnToInt(vector<int>& ans, string s){
    14.       int n = s.size();
    15.       int res = 0;
    16.       string tmp = "";
    17.       bool zerobegin = true;
    18.       for(int i = 0; i < n; ++ i){
    19.           if(zerobegin && s[i] != '0'){
    20.               zerobegin = false;
    21.           }
    22.           if(!zerobegin){
    23.               tmp += s[i];
    24.           }
    25.       }
    26.       //不是全0
    27.       if(tmp != ""){
    28.           int x = stoi(tmp);
    29.           ans.push_back(x);
    30.       }
    31.   }
    32.   vector<int> printNumbers(int n) {
    33.       vector<int> ans;
    34.       string s(n, '0');
    35.       DFS(0, n, ans, s);     
    36.       return ans;
    37.   }
    38. };