The sword refers to offer17---print the n digits from 1 to the largest

题目考点：The original title set the array againINT32的范围内,所以可以直接使用for循环依次求出;But if the value exceeds INT32,就需要使用long型;如果数字比longwhat about bigger;无论是 short / int / long … 任意变量类型,数字的取值范围都是有限的.因此,大数的表示应用字符串 String 类型

1. 递归求解1

#include<iostream>
#include<vector>
#include<queue>

using namespace std;
class Solution {
    
public:
    string path = "";
    vector<string> res;
    vector<char> strs = {
    '0','1','2','3','4','5','6','7','8','9'};
    void printNums(int n)
    {
    
        dfs(0, n);
        for (auto str : res)
            cout << str << endl;
        return;
    }

    void dfs(int idx, int n)
    {
    
       if (path.size() == n)
       {
    
           res.push_back(path);
           return;
       }
       for (int i =0; i <= 9; i++)
       {
    
           path.push_back(strs[i]);
           dfs(i, n);
           path.pop_back();
       }
    }
};

int main()
{
    
    Solution S;
    S.printNums(2);
    return 0;
}

00
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20

2. 递归解法2

#include<iostream>
#include<vector>
#include<queue>

using namespace std;
class Solution {
    
public:
    string path = "";
    vector<string> res;
    vector<char> strs = {
    '0','1','2','3','4','5','6','7','8','9'};
    void printNums(int n)
    {
    
        res = {
     "1","2","3","4","5","6","7","8","9" };
        dfs(0, n);
        for (auto str : res)
            cout << str << endl;
        return;
    }
	//添加第idx个数字,目标长度为n
    void dfs(int idx, int n)
    {
    
       if (idx==n)
       {
    
           res.push_back(path);
           return;
       }
       //第一个数字不能为0
       int start = idx == 0 ? 1 : 0;
       for (int i =start; i <= 9; i++)
       {
    
           path.push_back(strs[i]);
           dfs(idx + 1, n);
           path.pop_back();
       }
    }
};

int main()
{
    
    Solution S;
    S.printNums(2);
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21