《劍指offer》面試題17：打印從1到最大的n位數(shù)

題目：輸入數(shù)字n，按順序打印出從1到最大的n位十進制數(shù)。比如輸入3，則打印出1、2、3一直到最大的3位數(shù)999。

思路：當(dāng)輸入n很大時，使用int或long都會溢出。需要考慮大數(shù)問題。
可以借用字符串或數(shù)組表示大數(shù)。首先把字符串中的每一個數(shù)字初始化為'0'，然后每一次為字符串表示的數(shù)加1，再打印出來。因此，我們只需要做兩件事：一是在字符串表示的數(shù)字上模擬加法；二是把字符串表示的數(shù)字打印出來。
在模擬加法的過程中需要判斷是否已經(jīng)到了最大的n位數(shù)，如果使用庫函數(shù)則時間復(fù)雜度為O(n)。在加法的過程中如果字符串的第一個字符產(chǎn)生了進位，則已經(jīng)到達了最大的n位數(shù)?？梢詫崿F(xiàn)O（1）時間判斷是否已經(jīng)達到了最大的n位數(shù)。
打印字符串表示的數(shù)字時，字符串開始的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位數(shù)則打印
    while (!increment(stringBuffer)) {
        printNumber(stringBuffer);
    }
}

/**
 * 判斷是否到達最大的n位數(shù)
 * 時間復(fù)雜度：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();
}

如果在數(shù)字前面補0，則n位所有十進制數(shù)其實就是n個從0到9的全排列，把數(shù)字的每一位從0到9排列一遍，就得到了全部的十進制數(shù)。打印時排在前面的0不打印出來。使用遞歸實現(xiàn)全排列。
代碼如下：

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);
    }
}