剑指offer-----打印1到最大的n位数

import java.util.Arrays;

/**
 * 剑指offer面试题12:打印1到最大的n位数
 * 
 * 题目:输入数字n,按顺序打印出从1最大的n位十进制数。比如输入3，则打印出1,2,3一直到最大的3位数即999.
 * 
 * 考查:解决大数处理问题---可以使用字符串或者数组来处理大数问题
 * 
 * 思路1:在字符串或者数组模拟数字加法的解法
 * 思路2:把问题转换成数字排列的解法
 *
 */
public class PrintOneToMaxOfNDigigits {
	
	//打印1到最大的n位数,使用数组解法
	public static void printOneToMaxOfNDigigits_1(int n) {
		if(n <= 0) {
			return;
		}
		char[] number = new char[n];
		//将字符数组填充为'0'
		Arrays.fill(number, '0');
		while(!increment(number)) {
			printNumber(number);
		}
	}
	
	//使用数组实现对数进行+1操作
	public static boolean increment(char[] number) {
		//是否溢出
		boolean isOverFlow = false;
		//进位
		int carry = 0;
		//数组长度
		int len = number.length;
		for (int i = len-1; i >=0 ; i--) {
			int sum = number[i]-'0' + carry;
			if(i == len-1) {
				sum++;
			}
			if(sum >= 10) {
				if(i == 0) {
					isOverFlow = true;
				}else {
					sum -= 10;
					number[i] = (char) ('0'+sum);
					carry = 1;
				}
			}else {
				//普通位+1的结果保存到数组中，+1后程序退出循环
				number[i] = (char) ('0'+sum);
				break;
			}
		}
		
		return isOverFlow;
	}
	
	//打印1到最大的n位数,使用全排列解法
	public static void printOneToMaxOfNDigigits_2(int n) {
		if(n <= 0) {
			return;
		}
		char[] number = new char[n];
		for (int i = 0; i < 10; i++) {
			number[0] = (char) (i + '0');
			printToMaxOfNDigigitsRecursively(number, n,0);
		}
	}
	
	//全排列递归
	public static void printToMaxOfNDigigitsRecursively(char[] number,int length,int index){
		if(index == length-1) {
			printNumber(number);
			return;
		}
		for (int i = 0; i < 10; i++) {
			number[index+1] = (char) (i +'0');
			printToMaxOfNDigigitsRecursively(number, length, index+1);
		}
	}
	
	//打印数组中表示的数，如果数组中表示的数字位数小于n，则不打印前面的0
	public static void printNumber(char[] number) {
		boolean isBegin = true;
		int len = number.length;
		for (int i = 0; i < len; i++) {
			//碰到第一个非'0'的字符后才开始打印
			if(isBegin && number[i] != '0') {
				isBegin = false;
			}
			if(!isBegin){
				System.out.print(number[i]);
			}
		}
		System.out.println();
	}
	
	public static void main(String[] args) {
//		printOneToMaxOfNDigigits_1(2);
		printOneToMaxOfNDigigits_2(3);
	}

}