剑指Offer面试题：11.打印1到最大的n位数

Edison Zhou

发布于 2018-08-20 16:15:32

3920

发布于 2018-08-20 16:15:32

文章被收录于专栏：EdisonTalkEdisonTalk

一、题目：打印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();
    }