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

【打印从1到最大的n位数】《剑指offer》面试题17：打印从1到最大的n位数
题目：输入数字n，按顺序打印出从1到最大的n位十进制数。比如输入3，则打印出1、2、3一直到最大的3位数999。
思路：当输入n很大时，使用int或long都会溢出。需要考虑大数问题。
可以借用字符串或数组表示大数。首先把字符串中的每一个数字初始化为'0'，然后每一次为字符串表示的数加1，再打印出来。因此，我们只需要做两件事：一是在字符串表示的数字上模拟加法；二是把字符串表示的数字打印出来。
在模拟加法的过程中需要判断是否已经到了最大的n位数，如果使用库函数则时间复杂度为O(n)。在加法的过程中如果字符串的第一个字符产生了进位，则已经到达了最大的n位数。可以实现O（1）时间判断是否已经达到了最大的n位数。
打印字符串表示的数字时，字符串开始的0不必打印。例如'068'打印68
代码如下：

public static void print1ToMaxOfNDigits(int n) { if (n < 0) { return; } StringBuffer stringBuffer = new StringBuffer(); for (int i = 0; i < n; i++) { stringBuffer.append('0'); } // 如果未达到最大的n位数则打印 while (!increment(stringBuffer)) { printNumber(stringBuffer); } }/** * 判断是否到达最大的n位数 * 时间复杂度：O（1） * @param number * @return */ private static boolean increment(StringBuffer number) { boolean isOverFlow = false; int nTakeOver = 0; int nLength = number.length(); for (int i = nLength - 1; i >= 0; i--) { int nSum = number.charAt(i) - '0' + nTakeOver; if (i == nLength - 1) { nSum++; } if (nSum >= 10) { if (i == 0) { isOverFlow = true; } else { nSum -= 10; nTakeOver = 1; number.setCharAt(i,(char)('0' + nSum)); } } else { number.setCharAt(i,(char)('0' + nSum)); break; } } return isOverFlow; }private static void printNumber(StringBuffer number) { boolean isBegining0 = true; for (int i = 0; i < number.length(); i++) { if (isBegining0 && number.charAt[i] != '0') { isBegining0 = false; } if (!isBegining0) { System.out.print(number.charAt[i]); } } System.out.println(); }

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

public static void print1ToMaxOfNDigits2(int n) { if (n < 0) { return; } StringBuffer stringBuffer = new StringBuffer(); for (int i = 0; i < n; i++) { stringBuffer.append('0'); } for (int i = 0; i < 10; i++) { stringBuffer.setCharAt(0,(char)(i + '0')); print1ToMaxOfNDigits2Core(stringBuffer,n,0); } }private static void print1ToMaxOfNDigits2Core(StringBuffer number,int n,int index) { if (index == n - 1) { printNumber(number); return; } for (int i = 0; i < 10; i++) { number.setCharAt(index + 1,(char)(i + '0')); print1ToMaxOfNDigitsCore(number,n,index + 1); } }