打印从1到最大的n位数

题目：

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

分析：看到这道题很容易想到的办法是，先求出最大的n位数，然后用一个循环打印出所有数。

public static void printNumWithMax(int n) {

    long num = 1;
    // 利用循环计算出 (n+1) 位十进制数
    for (int i = 0; i < n; i++) {
        num *= 10;
    }

    // 循环打印（n+1）位十进制数的前一位，即是n位最大数
    for (int i = 1; i < num; i++) {
        System.out.println(i);
    }
}

上面的方法虽然打印出了所有数字，但是没有考虑边界问题，题目没有说明 n 的取值范围，所以不适合用 int保存，用long类型也可能会越界，所以要考虑使用字符串来保存数字。

在字符串表达数字上模拟加法，我们首先设置是否溢出标识，是否进位标识，以及取得字符数组长度，遍历这个字符数组，在末尾进行+1操作，如果末尾字符在+1后变为不小于10的数字，我们将末尾减去10加上‘0’字符赋值为末位，进位标识设置为1，在循环次位时+1，然后再判断是否为不小于10，是的话重复上面的步骤。直到判断高位是不是不小于10，是的话字符数组溢出；如果末尾字符在+1后是小于10的数字，直接加上‘0’赋值给末尾，跳出当前循环，返回没有溢出。

在字符串表达的数字打印出来方法时，没有什么特别，直接利用for循环遍历输出字符数组，但是要从高位第一个不是0的开始输出。

private static boolean incrementNumber(char[] number) {
    boolean isOverflow = false; //判断是否溢出
    int nTakeOver = 0; //判断是否进位
    int nLength = number.length;
    for (int i = nLength - 1; i >= 0; --i) {
        int nSum = number[i] - '0' + nTakeOver; //取到第i位的字符转换为数字 +进位符
        if (i == nLength - 1) { //末尾自加1
            ++nSum;
        }
        if (nSum >= 10) {
            if (i == 0) {
                isOverflow = true;
            } else {
                nSum -= 10;
                nTakeOver = 1;
                number[i] = (char) ('0' + nSum);
            }
        } else {
            number[i] = (char) (nSum + '0');
            break;
        }
    }
    return isOverflow;
}

private static 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();
}

把问题转化为数字排列的解法，使用递归可以使代码简洁明了。即：如果在所有的数字前面补0的话，就会发现n位所有的十进制数其实就是n个从0到9的全排列。也就是说，我们把数字的每一位都从0到9排列一遍，就得到了所有的十进制数。在打印时，数字排在前面的0不打印。

全排列递归实现最容易。数字的每一位都可能是0到9的一个数，然后设置下一位。递归结束的条件就是我们已经设置了数字的最后一位。

public static void printToMaxByCursive(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) {
        number[0] = (char) (i + '0');
        printToMaxOfNDigitsRecursively(number, n, 0);
    }
}


//利用递归实现1到最大的n位数的全排列
private static void printToMaxOfNDigitsRecursively(char[] number, int n, int index) {
    if(index == n - 1){
        printNumber(number);
        return;
    }
    for (int i = 0; i < 10; ++i) {
        number[index + 1] = (char) (i + '0');
        printToMaxOfNDigitsRecursively(number, n, index + 1);
    }
}