【☆面试题12】打印1到最大的n位数

【题目描述】

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

【解决方案】

1. 最无脑的做法

怎么可能会出这么简单的问题，必然要考虑的大数问题！

我的代码实现，仅供参考：

 1         public static void Print0neToMax(int n)
 2         {
 3             int max = 1;
 4 
 5             for (int i = 0; i < n; i++)
 6             {
 7                 max *= 10;
 8             }
 9 
10             for (int i = 1; i < max; i++)
11             {
12                 Console.WriteLine(i);
13             }
14         }

2. 考虑大数问题

我的代码实现，仅供参考：

 1         public static void PrintOneToMax(int n)
 2         {
 3             if (n <= 0)
 4                 return;
 5 
 6             int[] num = new int[n];
 7 
 8             while (!Increment(num))
 9             {
10                 PrintNum(num);
11             }
12         }
13 
14         public static bool Increment(int[] num)
15         {
16             int length = num.Length;
17             int flag = 0;
18             int temp = 0;
19             bool isOverFlow = false;
20 
21             for (int i = length - 1; i >= 0; i--)
22             {
23                 temp = num[i] + flag;
24 
25                 if (i == length - 1)
26                 {
27                     temp++;
28                 }
29 
30                 if (temp >= 10)
31                 {
32                     if (i == 0)
33                     {
34                         isOverFlow = true;
35                         break;
36                     }
37                     else
38                     {
39                         flag = 1;
40                         temp = temp - 10;
41                         num[i] = temp;
42                     }
43                 }
44                 else
45                 {
46                     num[i] = temp;
47                     break;
48                 }
49             }
50 
51             return isOverFlow;
52         }
53 
54         public static void PrintNum(int[] num)
55         {
56             bool isBegining = true;
57 
58             for (int i = 0; i < num.Length; i++)
59             {
60                 if (isBegining && num[i] != 0)
61                 {
62                     isBegining = false;
63                 }
64 
65                 if (!isBegining)
66                 {
67                     Console.Write(num[i]);
68                 }
69             }
70 
71             Console.WriteLine();
72         }

3. 把问题转换成0到9个数字的排列的解法，递归让代码更简洁

我的代码实现，仅供参考：

 1         public static void PrintOneToMax(int n)
 2         {
 3             if (n <= 0)
 4                 return;
 5 
 6             int[] num = new int[n];
 7             
 8             GetOneToNineArrange(num, 0);
 9         }
10 
11         public static void GetOneToNineArrange(int[] num,int index)
12         {
13             if (index == num.Length)
14             {
15                 PrintNum(num);
16                 return;
17             }
18 
19             for (int i = 0; i < 10; i++)
20             {
21                 num[index] = i;
22                 GetOneToNineArrange(num, index + 1);
23             }
24         }
25 
26         public static void PrintNum(int[] num)
27         {
28             bool isBegining = true;
29 
30             for (int i = 0; i < num.Length; i++)
31             {
32                 if (isBegining && num[i] != 0)
33                 {
34                     isBegining = false;
35                 }
36 
37                 if (!isBegining)
38                 {
39                     Console.Write(num[i]);
40                 }
41             }
42 
43             Console.WriteLine();
44         }

【本题扩展】

在前面的代码中，我们都是用一个int型来表示十进制数字的以为，而32bit的int型字符最多能存2^32方的字符，而十进制数字只有10个数字。

因此用int型字符来表示十进制的数字并没有充分利用内存，浪费空间。有没有高效的方式来表示大数？

我的想法：

可以使用char，byte数组来存放，但是C#中最小的byte也得8位，能存256个字符，还是一定程度上浪费了空间。应该有其他更巧妙的方法，暂时先不管这块了。

【相关题目】

大数相加，考虑与负数相加的情况，其实也隐式包含了大数相减。

暂时先不做，放下。