面试题17：打印从1到最大的n位数

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

错误方法：

先求出最大的n位数，再用一个循环从1逐个打印。但是当n很大时，我们求最大的n位数用int或long long可能都会溢出。所以我们需要考虑的是大数问题。

常规方法：

用字符串解决大数问题。本题中需要重点解决两大问题：1.字符串表示的大数模拟加法；2.把字符串表达的数打印出来。

字符串表示的大数模拟加法：

对于每一个字符串，计算加法都是从个位加1。从字符到int类型的计算方法：number[i] - '0'；
用局部变量nSum表示每一个上的字符，都等于本位+进位。由nSum是否等于10判断是否需要进位，若是，进位标志nTakeOver=1，nSum所在位变为0。下一次迭代时，下一个位会加上进位。
如何判断结束：若最大的数999……99加1，则最高位会变为10，而其他情况都不会在第一个字符上产生进位，所以当加1时发现第一个字符产生了进位，表明已经到了最大的n位数了。

bool Increment(char* number)
{
    //是否越界标志
    bool isOverflow = false;
    //进位符
    int nTakeOver = 0;
    //number中字符的数量
    int nLength = strlen(number);
    for (int i = nLength - 1; i >= 0; i--)
    {
        //nSum表示每一位的计算方法：本位+进位
        int nSum = number[i] - '0' + nTakeOver;

        //每个number都是从个位加1，直至进位
        if (i == nLength - 1)
        {
            nSum += 1;
        }

        if (nSum == 10)
        {
            //若是最高位number[0]为10，表示已经到达最大值了，越界标志置为true
            if (i == 0)
                isOverflow = true;
            //若某位加1后为10，则进位1，本位变0；
            else
            {
                nSum -= 10;
                nTakeOver = 1;
                number[i] = '0';
            }
        }

        //若nSum结果在0-9之间，正常加1即可
        else
        {
            number[i] = '0' + nSum;
            break;
        }
    }
    return isOverflow;
}

把字符串表达的数打印出来

前面字符串加法操作时，当数字不够n位时，我们会在数字前面补0，打印的字符串应该删除前面这些0。所以在这个函数里，只有在碰到第一个非零的字符之后才会开始打印。

//删除前缀的0
void PrintNumber(char* number)
{
    //number中字符的数量
    int nLength = strlen(number);
    int zero_end = 0;
    while (number[zero_end]=='0'&&zero_end<nLength)
    {
        zero_end++;
    }
    for (int i = zero_end; i < nLength; i++)
    {
        cout << number[i];
    }
    cout << endl;
}

高级方法：

n位所有十进制数其实就是n个从0到9的全排列，用递归表达。递归结束的条件是我们已经设置好了数字的最后一位。

void Print1ToMaxOfDigits(int n)
{
    if (n < 0)
        return;
    char* number = new char[n + 1];
    memset(number, '0', n);
    number[n] = '\0';
    //从最高位为0-9，剩下的位递归排列
    for (int i = 0; i < 10; i++)
    {
        number[0] = i + '0';
        Print1ToMaxOfDigitsRecursively(number, n, 0);
    }
    delete[] number;
}

void Print1ToMaxOfDigitsRecursively(char* number, int length, int index)
{
    //若排列到了最后一位，打印字符串，退出函数。
    if (index == length - 1)
    {
        PrintNumber(number);
        return;
    }
    //递归排列
    for (int j = 0; j < 10; j++)
    {
        number[index + 1] = j + '0';
        Print1ToMaxOfDigitsRecursively(number, length, index + 1);
    }
}

迭代方法（全代码）

//打印大数，忽略前端的0
void printNumberWithoutZero(vector<int>& number)
{
    int len = number.size();
    //这里注意：迭代时第一个大数为全0，不用打印出来，直接返回空即可。若不处理，会出现数组越界错误
    vector<int> allZero(number.size(), 0);
    if (number == allZero)
        return;
    int j = 0;
    while (number[j]==0)
    {
        ++j;
    }
    for(int i=j;i<len;++i)
        cout << number[i];
    cout << endl;
}

//递归打印
void Print1ToMaxOfDigit(int n)
{
    if (n <= 0)
        return;
    vector<int> number(n, 0);
    for (int i = 0; i <= 9; ++i)
    {
        number[0] = i;
        PrintRecrusively(number,n, 1);
    }
}
void PrintRecrusively(vector<int>& number,int n,int index)
{
    //若数组下标已经打印到了第n位，因最高位为n-1位，所以可返回
    if (index == n)
    {
        printNumberWithoutZero(number);
        return;
    }        
    for (int i = 0; i <= 9; ++i)
    {
        number[index] = i;
        PrintRecrusively(number, n,index + 1);
    }
}
int main()
{
    int n = 3;
    Print1ToMaxOfDigit(n);    
    return 0;
}