（补充）【打印1到最大的n位数】剑指offer——面试题12：打印1到最大的n位数

剑指offer——面试题12：打印1到最大的n位数

此题在牛客网上没有OnlineJudge，在此补充两种做法。
参考网址：https://blog.csdn.net/yanxiaolx/article/details/52049810
题目：输入数字n，按顺序打印出1到最大的n位十进制数。比如输入3，则打印出1、2、3一直到最大的3位数即999。
陷阱：用整数会溢出。考虑大数问题，就是输入的数字非常大的情况，如100，怎么表示100位的数呢，可以用字符串保存。
细节问题：
1.字符串递增的溢出判断
2.打印时过滤0

Solution1：

用字符串模拟加法。
使用字符串数组表示大数，最直观的方法是字符串里每个字符都是’0’到’9’之间的某一个字符，用来表示数字中的一位。因为数字最大是n位的，因此我们需要一个长度为n+1的字符串（字符串中最后一个是结束号’\0’）。当实际数字不够n位的时候，在字符串的前半部分补0。
首先把字符串中的每一个数字都初始化为’0’，然后每一次为字符串表示的数字加1，再打印出来。因此只需要做两件事：一是在字符串表达的数字上模拟加法，二是把字符串表达的数字打印出来。
在这里定义了函数PrintNumber，在这个函数里，只有在碰到第一个非0的字符之后才开始打印，直至字符串的结尾。

Solution2：

思路：将n位数看做排列组合问题，以3位数为例，有3个位置，每个位上从0到9中选一个数字放进去，求所有的排列情况。三个位置是依次放进去数字的，这可以用递归。每个位置上0到9的十种情况可以用for循环来遍历。另外，记得函数最开始进入时要检查边界条件。

#include <iostream>
#include <vector>
#include <string>
using namespace std;

//打印1到最大N位数字
void PrintNumber(string &number);
//字符串number表示一个数字，在 number上增加1，如果做加法溢出，返回true；否则为false
bool Increment(string &number);
//数字全排列递归法
void Print1ToMaxOfNDigitsRecursively(string number, int length, int index);

// ====================方法一====================
void Print1ToMaxOfNDigits_1(int n) {
    if (n <= 0) {
        cout << "n必须为正整数，参数错误！" << endl;
        return;
    }
    string number(n, '0');
    while (!Increment(number)) //没有溢出则继续打印数字
        PrintNumber(number);
    return;
}

// 字符串number表示一个数字，在 number上增加1,如果做加法溢出，则返回true；否则为false
bool Increment(string &number) {
    bool isOverflow = false; //标记是否溢出
    int carry = 0;//进位
    int nLength = number.size();

    for (int i = nLength - 1; i >= 0; i--) { //从最低位一直加到最高位
        //将字符串number变为整数，后面才可以自++运算
        int nSum = number[i] - '0' + carry;
        if (i == nLength - 1)//最低位
            nSum++;//对应着加1操作
        if (nSum >= 10) { //判断是否需要进位
            if (i == 0)//当目前是最高位切需要进位时，则溢出
                isOverflow = true;
            else { //非最高位进位处理
                nSum -= 10;
                carry = 1;
                number[i] = '0' + nSum;//将整数number变为字符串，方便后面进行打印
            }
        } else { //不需要进位时，加1后跳出循环
            number[i] = '0' + nSum;
            break;
        }
    }
    return isOverflow;
}


// ====================方法二====================
void Print1ToMaxOfNDigits_2(int n) {
    if (n <= 0) {
        printf("n必须为正整数，参数错误！");
        return;
    }
    //数字全排列的写法需牢记！！！
    string number(n, '0');
    Print1ToMaxOfNDigitsRecursively(number, n, 0);
    return;
}

//数字全排列递归法
void Print1ToMaxOfNDigitsRecursively(string number, int length, int index) {
    //到了最后一位数字，递归结束
    if (index == length) {
        PrintNumber(number);
        return;
    }
    for (int i = 0; i < 10; i++) {
        //整数转为字符串
        number[index] = i + '0';
        Print1ToMaxOfNDigitsRecursively(number, length, index + 1);
    }
}

// ====================公共函数====================
// 字符串number表示一个数字，数字有若干个0开头， 打印出这个数字，并忽略前面的0
void PrintNumber(string &number) {
    bool isBeginning = true;
    int nLength = number.size();
    for (int i = 0; i < nLength; i++) {
        if (isBeginning&&number[i] != '0') { //找到起点
            isBeginning = false;
        }
        if (!isBeginning)
            cout << number[i];
    }
    cout << endl;
}

// ====================测试代码====================
void Test(int n) {
    cout << "Test for "<< n << " begins(方法一):" << endl;
    Print1ToMaxOfNDigits_1(n);
    cout << endl;

    cout << "Test for " << n << " begins(方法二):" << endl;
    Print1ToMaxOfNDigits_2(n);
    cout << endl;

    cout << "Test for " << n << " ends." << endl;
}

int main() {
    Test(1);
    Test(2);
    //Test(3);
    Test(0);
    Test(-1);
    return 0;
}

注意：重点学习数字全排列的写法！！！