算法学习之打印从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();
    }