《剑指offer》面试题17：打印从1到最大的n位数

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

思路：当输入n很大时，使用int或long都会溢出。需要考虑大数问题。
可以借用字符串或数组表示大数。首先把字符串中的每一个数字初始化为'0'，然后每一次为字符串表示的数加1，再打印出来。因此，我们只需要做两件事：一是在字符串表示的数字上模拟加法；二是把字符串表示的数字打印出来。
在模拟加法的过程中需要判断是否已经到了最大的n位数，如果使用库函数则时间复杂度为O(n)。在加法的过程中如果字符串的第一个字符产生了进位，则已经到达了最大的n位数。可以实现O（1）时间判断是否已经达到了最大的n位数。
打印字符串表示的数字时，字符串开始的0不必打印。例如'068'打印68

代码如下：

public static void print1ToMaxOfNDigits(int n) {
    if (n < 0) {
        return;
    }
    StringBuffer stringBuffer = new StringBuffer();
    for (int i = 0;i < n;i++) {
        stringBuffer.append('0');
    }
    // 如果未达到最大的n位数则打印
    while (!increment(stringBuffer)) {
        printNumber(stringBuffer);
    }
}

/**
 * 判断是否到达最大的n位数
 * 时间复杂度：O（1）
 * @param number
 * @return
 */
private static boolean increment(StringBuffer number) {
    boolean isOverFlow = false;
    int nTakeOver = 0;
    int nLength = number.length();
    for (int i = nLength - 1;i >= 0;i--) {
        int nSum = number.charAt(i) - '0' + nTakeOver;
        if (i == nLength - 1) {
            nSum++;
        }
        if (nSum >= 10) {
            if (i == 0) {
                isOverFlow = true;
            } else {
                nSum -= 10;
                nTakeOver = 1;
                number.setCharAt(i,(char)('0' + nSum));
            }
        } else {
            number.setCharAt(i,(char)('0' + nSum));
            break;
        }
    }
    return isOverFlow;
}

private static void printNumber(StringBuffer number) {
    boolean isBegining0 = true;
    for (int i = 0;i < number.length();i++) {
        if (isBegining0 && number.charAt[i] != '0') {
            isBegining0 = false;
        }
        if (!isBegining0) {
            System.out.print(number.charAt[i]);
        }
    }
    System.out.println();
}

如果在数字前面补0，则n位所有十进制数其实就是n个从0到9的全排列，把数字的每一位从0到9排列一遍，就得到了全部的十进制数。打印时排在前面的0不打印出来。使用递归实现全排列。
代码如下：

public static void print1ToMaxOfNDigits2(int n) {
    if (n < 0) {
        return;
    }
    StringBuffer stringBuffer = new StringBuffer();
    for (int i = 0;i < n;i++) {
        stringBuffer.append('0');
    }
    for (int i = 0;i < 10;i++) {
        stringBuffer.setCharAt(0,(char)(i + '0'));
        print1ToMaxOfNDigits2Core(stringBuffer,n,0);
    }
}

private static void print1ToMaxOfNDigits2Core(StringBuffer number,int n,int index) {
    if (index == n - 1) {
        printNumber(number);
        return;
    }
    for (int i = 0;i < 10;i++) {
        number.setCharAt(index + 1,(char)(i + '0'));
        print1ToMaxOfNDigitsCore(number,n,index + 1);
    }
}