剑指Offer面试题：11.打印1到最大的n位数
一、题目：打印1到最大的n位数
题目：输入数字n，按顺序打印出从1最大的n位十进制数。比如输入3，则打印出1、2、3一直到最大的3位数即999。
二、不同的解法
2.1 不假思索的解法
最容易想到的办法是先求出最大的n位数，然后用一个循环从1开始逐个打印：
static void Print1ToMaxOfNDigitsSimple(int n) { int number = 1; int i = 0; while (i < n) { number = number * 10; i++; } for (i = 1; i < number; i++) { Console.Write("{0}\t", i); } }
初看之下好像没有问题，但是其并没有考虑大数问题，有可能即使用整型(int)或长整型(long)都会溢出。
2.2 字符串模拟运算的解法
解决这个问题需要表达一个大数。最常用也是最容易的方法是用字符串或者数组表达大数。该算法的步骤如下：
Step1.把字符串中的每一个数字都初始化为'0'；
Step2.每一次为字符串表示的数字加1，再打印出来；
static void Print1ToMaxOfNDigits(int n) { if (n <= 0) { return; } // memset(number,'0',n); char[] number = new char[n + 1]; for (int i = 0; i < n; i++) { number[i] = '0'; } number[n] = '\0'; // Increment实现在表示数字的字符串number上增加1 while (!Increment(number)) { // PrintNumber负责打印出number PrintNumber(number); } number = null; } static bool Increment(char[] number) { bool isOverflow = false; int takeOver = 0; int length = number.Length - 1; for (int i = length - 1; i >= 0; i--) { int sum = number[i] - '0' + takeOver; if (i == length - 1) { sum++; } if (sum >= 10) { if (i == 0) { // 标识已经溢出了 isOverflow = true; } else { sum -= 10; takeOver = 1; number[i] = (char)('0' + sum); } } else { number[i] = (char)('0' + sum); break; } } return isOverflow; } static void PrintNumber(char[] number) { bool isBeginning0 = true; for (int i = 0; i < number.Length; i++) { if (isBeginning0 && number[i] != '0') { isBeginning0 = false; } if (!isBeginning0) { Console.Write("{0}", number[i]); } } Console.Write("\t"); }
这里要注意的是：当数字不够n位的时候，我们在数字的前面补0，打印的时候这些补位的0不应该打印出来。
三、单元测试
3.1 封装测试入口
static void PrintTest(int n) { Console.WriteLine("Test for {0} begins:", n); Print1ToMaxOfNDigits(n); Console.WriteLine("Test for {0} ends.", n); }
3.2 测试用例
static void Main(string[] args) { PrintTest(1); PrintTest(2); PrintTest(3); PrintTest(0); PrintTest(-1); Console.ReadKey(); }
正文到此结束
