欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2024-03-15 19:59:18
...

题目

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

解题思路

             第一种思路是:先求出最大的n位数,然后用一个循环从1开始逐步打印。但是这个方法没有考虑到大数的问题。

             第二种思路是:

             在对字符串进行加1操作的函数中,对最低位进行加1操作:

             如果该位置超过10,当你的指针已经到0位置的时候,说明已经超出范围了;需要将进位标识置为1,同时减去10,得到目前该位置上的数,并将它转换为字符类型。

             而如果没有超过10,就无需进位,而是直接将该位置上的数转换为字符类型。并跳出循环。

             在负责打印的函数中,只有在碰到第一个非0字符之后才开始打印,一直到字符串结尾。

             第三种思路是:

             本题实际上可以类比为,求n位所有十进制数是n个从0到9的全排列,即将n位上数字的每一位都从0到9排列一遍,就可以得到所有的十进制数。注意,以0开头的数字,前面的0不用打印。

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

代码

package myNewSwordOffer;

public class printToMaxOfDigits {
	//没有考虑到输入的位数是大数的情况
	public static void printToMaxOfDigits1(int n) {
		int number = 1;
		int i = 0;
		while(i < n) {
			number *= 10;
			i++;
		}
		for(int j = 0; j < number; j++) {
			System.out.print(j + " ");
		}
	}
	
	//在字符串上模拟数字的加法
	public static void printToMaxOfDigits2(int n) {
		if(n < 0) {
			return;
		}
		
		//申请空间,并初始化
		char[] number = new char[n];
		for(int i = 0; i < number.length; i++) {
			number[i] = '0';
		}
		while(!increament(number)) {
			printCharNumber(number);
		}
	}
	
	public static boolean increament(char[] number) {
		int nTakeOver = 0;
		for(int i = number.length-1; i >= 0; i--) {
			int nSum = (number[i] - '0') + nTakeOver;
			
			if(i == number.length - 1) {
				nSum ++;
			}
			if(nSum >= 10) {
				if(i == 0) {
					return true;
				}
				nTakeOver = 1;
				nSum -= 10;
				number[i] = (char)(nSum + '0');
			}else {
				number[i] = (char)(nSum + '0');
				break;
			}
		}
		return false;
	}
	
	//采用递归的方法
	public static void printToMaxOfDigits3(int n) {
		if(n < 0) {
			return;
		}
		
		char[] number = new char[n];
		for(int i = 0; i < number.length; i++) {
			number[i] = '0';
		}
		for(int i = 0; i <= 9; i++) {
			printToMaxOfDigitRecursively(n, number, i, 0);
		}
	}
	
	private static void printToMaxOfDigitRecursively(int n, char[] number, int nNumber, int index) {
		if(index == number.length - 1) {
			number[index] = (char)(nNumber + '0');
			printCharNumber(number);
			return;
		}else{
			number[index] = (char)(nNumber + '0');
			for(int i = 0; i <= 9; i++) {
				printToMaxOfDigitRecursively(n, number, i ,index+1);
			}
		}
	}

	public static void printCharNumber(char[] number) {
		boolean isBeginning0 = true;
		for(int i = 0; i < number.length; i++) {
			if(isBeginning0 && number[i] - '0' != 0) {
				isBeginning0 = false;
			}
			if(!isBeginning0) {
				System.out.print(number[i]);
			}
		}
		System.out.println();
	}
	
	public static void main(String[] args) {
		printToMaxOfDigits1(2);
		System.out.println("--------------");
		printToMaxOfDigits2(2);
		System.out.println("--------------");
		printToMaxOfDigits3(2);
	}
}

总结

1、本题是大数问题,其中那种通过字符串来模拟数字加法的方式值得学习;

2、