Question

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

跳进面试官陷阱

这个题目看起来很简单。我们看到这个问题之后，最容易想到的办法是先求出最大的n位数，然后用一个循环从1开始逐个打印。于是我们很容易就能写出如下的代码：

初看之下好像没有问题，但如果仔细分析这个问题，我们就能注意到面试官没有规定n的范围。当输入的n很大的时候，我们求最大的n位数是不是用整型（int）或者长整型（long long）都会溢出？也就是说我们需要考虑大数问题。这是面试官在这道题里设置的一个大陷阱。

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

经过前面的分析，我们很自然地想到解决这个问题需要表达一个大数。最常用也是最容易的方法是用字符串或者数组表达大数。接下来我们用字符串来解决大数问题。

用字符串表示数字的时候，最直观的方法就是字符串里每个字符都是0到9之间的某一个字符，用来表示数字中的一位。因为数字最大是n位的，因此我们需要一个长度为n＋1的字符串（字符串中最后一个是结束符号\0）。当实际数字不够n位的时候，在字符串的前半部分补0。

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

基于上面的分析，我们可以写出如下代码：

在上面的代码中，函数Increment实现在表示数字的字符串number上增加1，而函数PrintNumber打印出number。这两个看似简单的函数都暗藏着小小的玄机。

我们需要知道什么时候停止在number上增加1，即什么时候到了最大的n位数999…99（n个9）。一个最简单的办法是每次递增之后，都调用库函数strcmp比较表示数字的字符串number和最大的n位数999…99，如果相等则表示已经到了最大的n位数并终止递增。虽然调用strcmp很简单，但对于长度为n的字符串，它的时间复杂度为O（n）。

我们注意到只有对999…99加1的时候，才会在第一个字符（下标为0）的基础上产生进位，而其他所有情况都不会在第一个字符上产生进位。因此当我们发现在加1时第一个字符产生了进位，则已经是最大的n位数，此时Increment返回true，因此函数Print1ToMaxOfNDigits中的while循环终止。如何在每一次增加1之后快速判断是不是到了最大的n位数是本题的一个小陷阱。下面是Increment函数的参考代码，它实现了用O（1）时间判断是不是已经到了最大的n位数：

接下来我们再考虑如何打印用字符串表示的数字。虽然库函数printf可以很方便就能打印一个字符串，但在本题中调用printf并不是最合适的解决方案。前面我们提到，当数字不够n位的时候，我们在数字的前面补0，打印的时候这些补位的0不应该打印出来。比如输入3的时候，数字98用字符串表示成098。如果直接打印出098，就不符合我们的习惯。为此我们定义了函数PrintNumber，在这个函数里，我们只有在碰到第一个非0的字符之后才开始打印，直至字符串的结尾。能不能按照我们的阅读习惯打印数字，是面试官设置的另外一个小陷阱。实现代码如下：

把问题转换成数字排列的解法，递归让代码更简洁

上述思路虽然比较直观，但由于模拟了整数的加法，代码有点长。要在面试短短几十分钟时间里完整正确地写出这么长的代码，对很多应聘者而言不是一件容易的事情。接下来我们换一种思路来考虑这个问题。如果我们在数字前面补0的话，就会发现n位所有十进制数其实就是n个从0到9的全排列。也就是说，我们把数字的每一位都从0到9排列一遍，就得到了所有的十进制数。只是我们在打印的时候，数字排在前面的0我们不打印出来罢了。

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

函数PrintNumber和前面第二种思路中的一样，这里就不再重复了。

源代码：

本题完整的源代码详见12_Print1ToMaxOfNDigits项目。

测试用例：

- 功能测试（输入1、2、3……）。

- 特殊输入测试（输入-1、0）。

本题考点：

- 考查解决大数问题的能力。面试官出这个题目的时候，他期望应聘者能意识到这是一个大数问题，同时还期待应聘者能定义合适的数据表示方式来解决大数问题。

- 如果应聘者采用第一种思路即在数上加1逐个打印的思路，面试官会关注他判断是否已经到了最大的n位数时采用的方法。应聘者要注意到不同方法的时间效率相差很大。

- 如果应聘者采用第二种思路，面试官还将考查他用递归方法解决问题的能力。

- 面试官还将关注应聘者打印数字时会不会打印出位于数字最前面的0。这里能体现出应聘者在设计开发软件时是不是会考虑用户的使用习惯。通常我们的软件设计和开发需要符合大部分用户的人机交互习惯。

本题扩展：

在前面的代码中，我们都是用一个char型字符表示十进制数字的一位。8个bit的char型字符最多能表示256个字符，而十进制数字只有0～9的10个数字。因此用char型字符串来表示十进制的数字并没有充分利用内存，有一些浪费。有没有更高效的方式来表示大数？

相关题目：

定义一个函数，在该函数中可以实现任意两个整数的加法。由于没有限定输入两个数的大小范围，我们也要把它当做大数问题来处理。在前面的代码的第一个思路中，实现了在字符串表示的数字上加1的功能，我们可以参考这个思路实现两个数字的相加功能。另外还有一个需要注意的问题：如果输入的数字中有负数，我们应该怎么去处理？

面试小提示：

如果面试题是关于n位的整数并且没有限定n的取值范围，或者是输入任意大小的整数，那么这个题目很有可能是需要考虑大数问题的。字符串是一个简单、有效的表示大数的方法。