剑指offer17---打印从1到最大的n位数

题目考点：原题设定数组再INT32的范围内,所以可以直接使用for循环依次求出；但是如果数值超过INT32,就需要使用long型；如果数字比long更大怎么办；无论是 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