题目描述

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

题目解读

• 剑指Offer 114

代码

• 思路一、常规思路，用字符串存储，每次模拟数字+1操作

#include<iostream>
#include<string.h>
using namespace std;

bool Icreament_Digits(char *number, int length){
    bool isOverflow = false;
    int isTakeOver = 0;
    int sum = 0;

    for(int i=length; i >= 0; i--){
        
        sum = number[i] - '0' + isTakeOver;
        if(i == length){
            sum ++;
        }
        
        if(sum >= 10){
            if(i == 0){
                isOverflow = true;
            }
            else{
                number[i] = sum%10 + '0';
                isTakeOver = 1;
            }
        }
        else{
            number[i]  = sum + '0';
            break;
        }
    }
    return isOverflow;
}

void PrintNumber(char *number, int length){
    bool is_zero = true;

    for(int i = 0; i <= length; i++){
        if(number[i] != '0'){
            is_zero = false;
        }

        if(! is_zero){
            cout<<number[i];
        }
    }
    cout<<endl;
}

void PrintToMaxOfNDigits(int n){
    char *number = new char[n + 1];
    memset(number, '0', n);
    number[n] = '\0';

    while(! Icreament_Digits(number, n-1)){
        PrintNumber(number, n-1);
    }
    delete[] number;
}

int main(){
    PrintToMaxOfNDigits(6);
}

• 思路二、把问题转换为时间排列的解法，递归让代码更简洁

#include<iostream>
#include<string.h>
using namespace std;

void PrintNumber(char *number, int length){
    bool is_zero = true;

    for(int i = 0; i < length; i++){
        if(number[i] != '0'){
            is_zero = false;
        }

        if(! is_zero){
            cout<<number[i];
        }
    }
    cout<<endl;
}

void PrintToMaxOfNDigitsCore(char *number, int length, int index){
    if(index == length){
        PrintNumber(number, length);
    }
    else{
        for(int i=0; i < 10; i++){
            number[index] = i + '0';
            PrintToMaxOfNDigitsCore(number, length, index+1);
        }
    }
}

void PrintToMaxOfNDigits(int n){
    char *number = new char[n + 1];
    memset(number, '0', n);
    number[n] = '\0';

    PrintToMaxOfNDigitsCore(number, n, 0);
    delete[] number;
}

int main(){
    PrintToMaxOfNDigits(6);
}

总结展望

• 剑指 Offer 真是越做越顺心，每道题目都有收货，开心...

附

• 思路三，在整数范围内的递归(第二轮复习写的)

#include<iostream>
using namespace std;

void aa(int last, int n, int shi){
    if(n == 0){
        cout<<last<<endl;
    }
    else{
        for(int i=0; i <= 9; i++){
            aa(last + i*shi, n-1, shi/10);
        }
    }
}

int main(){
    int n = 3;
    int tt = 1;
    for(int i=2; i <=n; i++){
        tt *= 10;
    }
    aa(0, n, tt);
}