【剑指17】打印从 1 到最大的 n 位数

题目描述

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

解题思路

1.由于 n 可能会非常大，因此不能直接用 int 表示数字，而是用 char 数组进行存储。

public class Solution_17 {

    public static void main(String[] args) {
        print1ToMaxOfNDigits(3);
    }

    public static void print1ToMaxOfNDigits(int n) {
        if (n == 0) return;
        char[] chars = new char[n];
        for (int i = 0; i < n; i++) {
            chars[i] = '0';
        }
        while (!increment(chars)) {
            print(chars);
        }
    }

    public static boolean increment(char[] chars) {
        int carryOver = 0; //进位标志
        boolean overFlow = false; //溢出标志
        int sum = 0;
        for (int i = chars.length - 1; i >= 0; i--) {
            sum = chars[i] - '0' + carryOver;
            if (i == chars.length - 1) {
                sum++;
            }

            if (sum >= 10) {
                if (i == 0) {
                    overFlow = true;
                } else {
                    carryOver = 1;
                    sum -= 10;
                    chars[i] = (char) ('0' + sum);
                }
            } else {
                chars[i] = (char) ('0' + sum);
                break;
            }
        }
        return overFlow;
    }

    public static void print(char[] chars) {
        int index = -1;
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] != '0') {
                index = i;
                break;
            }
        }

        for (int i = index; i < chars.length; i++) {
            System.out.print(chars[i]);
        }
        System.out.println("");
    }
}

2.如果在数字前面补0，则n位所有十进制数其实就是n个从0到9的全排列，把数字的每一位从0到9排列一遍，就得到了全部的十进制数。打印时排在前面的0不打印出来。使用递归实现全排列。

/**
 * 打印从1到n位的最大数：使用递归实现全排列
 */
public class Solution_17_2 {

    public static void main(String[] args) {
        print1ToMaxOfNDigits(3);
    }

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

    public static void print1ToMaxOfNDigits_Recursely(char[] chars, int n, int index) {
        if (index == n) {
            printNumber(chars);
            return;
        }

        for (int i = 0; i < 10; i++) {
            chars[index] = (char) ('0' + i);
            print1ToMaxOfNDigits_Recursely(chars, n, index + 1);
        }
    }

    public static void printNumber(char[] chars) {
        int startNotZero = -1;
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] != '0') {
                startNotZero = i;
                break;
            }
        }
        if (startNotZero == -1) {
            return;
        }
        for (int i = startNotZero; i < chars.length; i++) {
            System.out.print(chars[i]);
        }
        System.out.println("");
    }

}