题目：输入数字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中的一个数，然后设置下一位。递归结束的条件是我们已经设置了数字的最后一位。
