算法學習之列印從1到最大的n位數

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

解法一：我們可能首先想到周遊接完事了，但是數字太大時就崩了，你懂得，是以使用字元串模拟數字加減法。

public void print1ToMaxOfNDigits(int n) {
        char[] number = new char[n];
        for (int i = 0; i < n; i++) {
            number[i] = '0';
        }

        while (!increment(number)) {
            printNumber(number);
        }
    }

    private boolean increment(char[] number) {

        int overTake = 0;

        int length = number.length;
        for (int i = length - 1; i >= 0; i--) {
            int sum = number[i] - '0' + overTake;
            if (i == length - 1) {
                ++sum;
            }

            if (sum >= 10) { // 如果大于10則進行進位
                if (i == 0) {// 如果是最大位數了，說明已經溢出，停止循環
                    return true;
                } else {// 模拟十進制加法進位
                    overTake = 1;
                    sum -= 10;
                    number[i] = (char) (sum + '0');
                }
            } else { // 小于10，列印
                number[i] = (char) ('0' + sum);
                break;
            }

        }


        return false;
    }

    private void printNumber(char[] numbers) {
        boolean isZ = true;
        for (char number : numbers) {

            if (isZ&&number!='0') { // 去除高位為0的情況
                isZ = false;
            }

            if(!isZ) {
                System.out.print(number);
            }
        }
        System.out.println(); // 拼接完整換行

    }
           

解法二：使用遞歸

因為每個位置都可能是0~9，是以我們做n位的0~9全排列就行了。

1、先是首位也就是最高位确定一個數字（0~9），後面的數字全排列

2、後一位數字确定一位數字（0~9），其後一位在進行全排列

3、以此類推，知道index到達末尾，隻剩一個數字時，結束

//列印1到最大的n位數的主方法
    public void printToMaxOfDigits(int n) {
        if (n <= 0) {
            System.out.println("輸入的n沒有意義");
            return;
        }
        char number[] = new char[n];
        for (int i = 0; i < number.length; i++) {
            number[i] = '0';
        }
        for (int i = 0; i < 10; ++i) { // 控制最大位數範圍從0~9 如：100~900
            number[0] = (char) (i + '0');
            printToMaxOfNDigitsRecursively(number, n, 0);
        }
    }

    //利用遞歸實作1到最大的n位數的全排列
    public void printToMaxOfNDigitsRecursively(char[] number, int n, int index) {

        if (index == n - 1) {
            printNumber(number);
            return;
        }

        for (int i = 0; i < 10; ++i) { // 指定位置(個位跟十位至最高位的前一位)的值可以為0~9
            number[index + 1] = (char) (i + '0');
            Log.e("testJ", "index==" + index + "-----" + "number[index + 1]==" + number[index + 1]);
            printToMaxOfNDigitsRecursively(number, n, index + 1);
        }

    }

    //輸出
    private void printNumber(char[] number) {
        boolean isBeginning0 = true;
        int nLength = number.length;
        for (int i = 0; i < nLength; ++i) {
            if (isBeginning0 && number[i] != '0') {
                isBeginning0 = false;
            }
            if (!isBeginning0) {
                System.out.print(number[i]);
            }
        }
        System.out.println();
    }