剑指Offer-题17（Java版）：打印1到最大的n位数

参考自：《剑指Offer——名企面试官精讲典型编程题》

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

主要思路：1到最大的n位数其实就是n个从0到9的全排列，把数字的每一位从0到9排列一遍就得到所有的数，总数目为$10^n$。可以使用递归实现全排列。

关键点：递归

时间复杂度：O($10^n$)

public class PrintOneToMaxOfNDigits { public static void main(String[] args) { int n = 3; print1ToMaxOfnDigits(n); } private static void print1ToMaxOfnDigits(int n) { if (n <= 0) { return; } char[] numbers = new char[n]; for (int i = 0; i < 10; ++i) { numbers[0] = (char) (i + '0'); printByRecursively(numbers, 0); } } private static void printByRecursively(char[] numbers, int index) { if (index == numbers.length - 1) { // 递归到数字长度为n，则打印结果 printNumber(numbers); return; } for (int i = 0; i < 10; ++i) { numbers[index + 1] = (char) (i + '0'); printByRecursively(numbers, index + 1); } } private static void printNumber(char[] numbers) { boolean isBeginWithZero = true; for (char number : numbers) { // 忽略开头的0 if (isBeginWithZero && number != '0') { isBeginWithZero = false; } if (!isBeginWithZero) { System.out.print(number); } } System.out.println(); } }