面試題12：列印1到最大的N位數

解題思路：

方法一：

利用數組來存儲每一位的數值（0~9）。

總共有N位，每一位的數值可能為0~9中的一個數，其實就是全排列問題，進而可以利用遞歸的方式求解。遞歸的結束條件就是已經設定了數字的最後一位的值。

package jianzhi;


public class Test12 {

    /**
     * 輸入數字n，按順序列印出從1最大的n位十進制數。比如輸入3，則列印出1、2、3 一直到最大的3位數即999。
     *
     * @param n 數字的最大位數
     */
    public static void printOneToNthDigits(int n) {
        // 輸入的數字不能為小于1
        if (n < ) {
            throw new RuntimeException("The input number must larger than 0");
        }
        // 建立一個數組用于打存放值
        int[] arr = new int[n];
        printOneToNthDigits(, arr);
    }

    /**
     * 輸入數字n，按順序列印出從1最大的n位十進制數。
     *
     * @param n   目前處理的是第個元素，從0開始計數
     * @param arr 存放結果的數組
     */
    public static void printOneToNthDigits(int n, int[] arr) {

        // 說明所有的資料排列選擇已經處理完了
        if (n >= arr.length) {
            // 可以輸入數組的值
            printArray(arr);
        } else {
            // 對
            for (int i = ; i <= ; i++) {
                arr[n] = i;
                printOneToNthDigits(n + , arr);
            }
        }
    }

    /**
     * 輸入數組的元素，從左到右，從第一個非0值到開始輸出到最後的元素。
     *
     * @param arr 要輸出的數組
     */
    public static void printArray(int[] arr) {
        // 找第一個非0的元素
        int index = ;
        while (index < arr.length && arr[index] == ) {
            index++;
        }

        // 從第一個非0值到開始輸出到最後的元素。
        for (int i = index; i < arr.length; i++) {
            System.out.print(arr[i]);
        }
        // 條件成立說明數組中有非零元素，是以需要換行
        if (index < arr.length) {
            System.out.println();
        }
    }

    /**
     * 輸入數字n，按順序列印出從1最大的n位十進制數。比如輸入3，則列印出1、2、3 一直到最大的3位數即999。
     * 【第二種方法，比上一種少用記憶體空間】
     *
     * @param n 數字的最大位數
     */
    public static void printOneToNthDigits2(int n) {
        // 輸入值必須大于0
        if (n < ) {
            throw new RuntimeException("The input number must larger than 0");
        }

        // 建立一個長度為n的數組
        int[] arr = new int[n];
        // 為數組元素賦初始值
        for (int i = ; i < arr.length; i++) {
            arr[i] = ;
        }

        // 求結果，如果最高位沒有進位就一直進行處理
        while (addOne(arr) == ) {
            printArray(arr);
        }
    }

    /**
     * 對arr表示的數組的最低位加1 arr中的每個數都不能超過9不能小于0，每個位置模拟一個數位
     *
     * @param arr 待加數組
     * @return 判斷最高位是否有進位，如果有進位就傳回1，否則傳回0
     */
    public static int addOne(int[] arr) {
        // 儲存進位值，因為每次最低位加1
        int carry = ;
        // 最低位的位置的後一位
        int index = arr.length;

        do {
            // 指向上一個處理位置
            index--;
            // 處理位置的值加上進位的值
            arr[index] += carry;
            // 求處理位置的進位
            carry = arr[index] / ;
            // 求處理位置的值
            arr[index] %= ;
        } while (carry !=  && index > );

        // 如果index=0說明已經處理了最高位，carry>0說明最高位有進位，傳回1
        if (carry >  && index == ) {
            return ;
        }

        // 無進位傳回0
        return ;
    }


    public static void main(String[] args) {
        printOneToNthDigits();
        System.out.println();
        printOneToNthDigits2();
    }

}