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

剑指offer面试题17:打印1到最大的n位数(Java 实现)

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

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

测试用例:

  1. 功能测试:输入1、2、3…
  2. 特殊测试:输入0、-1…

方法一:

找出最大的 n 位数,直接打印。

//找出最大的n位数,直接打印
	public void print1ToMaxOfNDigits_1(int n){
		int number = 1;
		int i = 0;
		
		while(i++ < n){                //有多少位数就乘多少个10
			number = number*10;             
		}
		
		for(int j=0; j<number; j++){       //此时nubmer-1为最大的数字
			System.out.println(j);
		}
	}

如果上述程序在n很大时,显然会有溢出,int 的范围不够。那么我们会想到用long来存储,但是如果n的值还是很大,以至于long也无法满足要求。

此时就要意识到这道题目是一个大数问题,需要利用字符串来存储数字。

方法二:

//利用字符串来存储数字
	public void print1ToMaxNdigits_2(int n){
		if(n<=0)return;
		
		StringBuffer str = new StringBuffer();
		
		//将字符串的每一个字符初始化为0
		for(int i=0; i<n; i++){
			str.append('0');
		}
		
		
		while(!Increment(str)){
			printNumber(str);
		}
	}

	public boolean Increment(StringBuffer str){
		boolean isOverFlow = false;
		int takeOver = 0;                  //初始进位为0  
		int length = str.length();
		
		for(int i=length-1; i>=0; i--){     //从字符串的尾部开始操作
			int num = str.charAt(i) - '0' +takeOver;     //字符串每一个字符上面的数字:原本的字符 - 初始化的字符‘0’ + 前面的进位
			
			if(i == length-1){              //如果是刚开始的尾部,直接自加,因为初始的数字为0
				num++;
			}
			
			if(num>=10){                   //如果字符上的数字到达10的时候,分为两种情况
				if(i==0){
					isOverFlow = true;      //到达最高位,数字溢出
				}else{
					num = num-10;           //没到最高位,把数字减掉10变成0,然后向前进一位
					takeOver = 1;
					str.setCharAt(i,(char) ('0'+num));   //把字符上的数字重新转换成字符类型
				}
			}else{                                   //字符上的数字没到达10,直接把数字转换成字符
				str.setCharAt(i, (char) ('0'+num));
				break;
			}
		}
		return isOverFlow;
	}
	
	//打印数字,从第一个非0的字符开始打印
	public void printNumber(StringBuffer str){
		boolean isBeginning0 = true;
		for(int i=0; i<str.length(); i++){
			if(isBeginning0 && str.charAt(i)!='0')
				isBeginning0 = false;
			if(!isBeginning0){
				System.out.println(str.charAt(i));
			}
		}

方法三:

如果我们在数字前面补0的话,就会发现n位所有十进制数其实就是n个从0到9的全排列。也就是说,我们把数字的每一位都从0到9排列一遍,就得到了所有的十进制数。

利用递归的方式把所有可能的数字组合全部排列出来,最后打印的时候不打印前面的0即可。

//递归排列所有数列的可能
	public void print1ToMaxNDigits_3(int n){
		if(n<=0)return;
		
		StringBuffer str = new StringBuffer(n);
		for(int i=0; i<n; i++){
			str.append('0');
		}
		
		for(int i=0; i<10;i++){
			str.setCharAt(0, (char) (i+'0'));
			print1ToMaxNDigits_Recursely(str,n,0);
		}
		
	}
	
	//构造一个递归函数
	public void print1ToMaxNDigits_Recursely(StringBuffer str, int n, int index) {
		if(index == n-1){
			printNumber1(str);
		}
		
		for(int i=0; i<10; i++){
			str.setCharAt(index, (char) (i+'0'));
		}
		print1ToMaxNDigits_Recursely(str, n, index+1);
	}
	
		//打印数字,从第一个非0的字符开始打印
		public void printNumber(StringBuffer str){
			boolean isBeginning0 = true;
			for(int i=0; i<str.length(); i++){
				if(isBeginning0 && str.charAt(i)!='0')
					isBeginning0 = false;
				if(!isBeginning0){
					System.out.println(str.charAt(i));
				}
			}
		}