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

发表于 | 更新于

题意

输入n，按顺序打印从1到最大的n位10进制数，如n=3,则输出1,2,3…999。

题解

n表示的是位数，所以可能很大，直接整数表示肯定不行。
1.用字符串模拟加法，只需要模拟加一即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution{
private:
    void addOne(vector<char> &orign){
        int p=0;
        while(orign[p]=='9'){
            orign[p]='0';
            p++;
        }
        orign[p]++;
    }
    void printStrNum(vector<char> &num){
        int p=num.size()-1;
        while(num[p]=='0') p--;
        for(int i=p;i>=0;i--){
            printf("%c",num[i]);
        }
        printf("\n");
    }
public:
    void print_1_to_max_n_digit_seq(int n){
        vector<char> num(n+1,'0');
        while(1){
            addOne(num);
            if(num[n]=='1') break;
            printStrNum(num);
        }
    }
};

2.递归输出每一位0-9

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution{
private:
    void printStrNum(vector<char> &num){
        int p=0;
        while(num[p]=='0') p++;
        for(int i=p;i<num.size();i++){
            printf("%c",num[i]);
        }
        if(p<num.size())printf("\n");
    }
    void dfs(vector<char> num,int index){
        if(index==num.size()){
            printStrNum(num);
            return ;
        }
        for(int i=0;i<10;i++){
            num[index]='0'+i;
            dfs(num,index+1);
        }
    }
public:
    void print_1_to_max_n_digit_seq(int n){
        vector<char> num(n,'0');
        dfs(num,0);
    }
};