17. 打印从 1 到最大的 n 位数

题目描述

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

解题思路

由于 n 可能会非常大，最大的 n 位数会超出 int 甚至 long 的范围，因此用长度为 n 的 char 数组表示数字。

n 位数的每一位都可以是 0～9，所有 n 位数就是这 n 位上数字的全排列。用回溯法从最高位开始逐位填入 0～9，填满 n 位就打印一次，例如 n = 2 时依次得到 00、01、……、99。打印时跳过前导 0，00 全是 0，不打印。

力扣上对应的 LCR 135 改为返回 int 数组，n 很小，直接从 1 循环到 10ⁿ - 1 即可。

public void print1ToMaxOfNDigits(int n) {
    if (n <= 0)
        return;
    char[] number = new char[n];
    print1ToMaxOfNDigits(number, 0);
}

private void print1ToMaxOfNDigits(char[] number, int digit) {
    if (digit == number.length) {
        printNumber(number);
        return;
    }
    for (int i = 0; i < 10; i++) {
        number[digit] = (char) (i + '0');
        print1ToMaxOfNDigits(number, digit + 1);
    }
}

private void printNumber(char[] number) {
    int index = 0;
    while (index < number.length && number[index] == '0')
        index++;
    if (index == number.length) // 全是 0，不是要打印的数
        return;
    while (index < number.length)
        System.out.print(number[index++]);
    System.out.println();
}