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

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

1.跳进面试官的陷阱

public int[] PrintNumbers(int n)
{
    var number = 1;
    var i = 0;
    while (i++<n)
    {
        number *= 10;
    }
    var reArray=new int[number-1];
    for (i = 1; i < number; i++)
    {
        reArray[i - 1] = i;
    }
    return reArray;
}

最容易想到的办法是先求出最大的n 位数，然后用一个循环从1 开始逐个打印。当输入的n很大的时候，我们求最大的n位数是不是用整型（int）或者长整型（long long）都会溢出？也就是说我们需要考虑大数问题。这是面试官在这道题里设置的一个大陷阱。

2.在字符串上模拟数字加法的解法，绕过陷阱才能拿到offer

public List<string> PrintNumbers(int n)
{
    if (n <= 0) return null;
    var number=new string[n+1];
    for (var i = 0; i < number.Length; i++)
        number[i] = "0";
    var reData = new List<int>();
    var list = new List<string>();
    while (!Increment(number))
    {
        //打印number
        list.Add(GetNumber(number));
    }
    return list;
}

/// <summary>
/// 数组模拟数字加一
/// </summary>
/// <param name="number"></param>
/// <returns></returns>
public bool Increment(string[] number)
{
    var isOverflow = false;
    var nTakeOver = 0;
    var nLength = number.Length;
    for(var i=nLength-1;i>=0;i--)
    {
        var nSum = int.Parse(number[i]) + nTakeOver;
        if (i == nLength - 1)
            nSum++;
        if (nSum >= 10)
        {
            if (i == 1)
                isOverflow = true;
            else
            {
                nSum -= 10;
                nTakeOver = 1;
                number[i] = nSum.ToString();
            }
        }
        else
        {
            number[i] = nSum.ToString();
            nTakeOver = 0;
        }
    }
    return isOverflow;
}

/// <summary>
/// 打印数字，去掉前面的0
/// </summary>
/// <param name="number"></param>
/// <returns></returns>
public string GetNumber(string[] number)
{
    var isBeginning0 = true;
    var nLength = number.Length;
    var str = new StringBuilder();
    for (var i = 0; i < nLength; i++)
    {
        if (isBeginning0 && number[i] != "0")
            isBeginning0 = false;
        if (!isBeginning0)
        {
            str.Append(number[i]);
        }
    }
    return str.ToString();
}

首先我们把字符串中的每一个数字都初始化为’0’，然后每一次为字符串表示的数字加1，再打印出来。因此我们只需要做两件事：一是在字符串表达的数字上模拟加法，二是把字符串表达的数字打印出来。

3.把问题转化成数字排列的解法，递归让代码更简介

public List<string> PrintNumbers(int n)
{
    if (n <= 0) return null;
    var number=new string[n];
    for (var i = 0; i < number.Length; i++)
        number[i] = "0";
    var list = new List<string>();
    for (var i = 0; i < 10; ++i)
    {
        number[0] = i.ToString();
        Print1ToMaxOfNDigitsRecursively(number, n, 0, list);
    }
    return list;
}

public void Print1ToMaxOfNDigitsRecursively(string[] number, int length, int index,List<string> list)
{
    if (index == length - 1)
    {
        list.Add(GetNumber(number));
        return;
    }
    for (var i = 0; i < 10; i++)
    {
        number[index + 1] = i.ToString();
        Print1ToMaxOfNDigitsRecursively(number, length, index + 1,list);
    }
}

/// <summary>
/// 打印数字，去掉前面的0
/// </summary>
/// <param name="number"></param>
/// <returns></returns>
public string GetNumber(string[] number)
{
    var isBeginning0 = true;
    var nLength = number.Length;
    var str = new StringBuilder();
    for (var i = 0; i < nLength; i++)
    {
        if (isBeginning0 && number[i] != "0")
            isBeginning0 = false;
        if (!isBeginning0)
        {
            str.Append(number[i]);
        }
    }
    return str.ToString();
}

全排列用递归很容易表达，数字的每一位都可能是0～9中的一个数，然后设置下一位。递归结束的条件是我们已经设置了数字的最后一位。