剑指offer编程题Java实现——面试题12打印1到最大的n位数

题目:打印1到最大的n位数

输入数字n,按顺序打印输出从1到最大的n位十进制数,比如输入3,打印从1到999.

这道题考察的地方是如何表示大数问题。由于n是任意大的数组,如果n太大的话n位数就超过了long型能够表示的范围,在面试题11求数值的整数次方的时候题目中已经明确的提示了不考虑大数问题,在这道题中,用字符串或者数组表示大数是一种很简单有效的方法。用字符串表示大数也适用于大数加法、大数减法和大数的乘法问题。

下面代码是使用数组方式实现大数的产生和打印,在这道题中要特殊考虑的地方是如果实现整数+1,以及低位+1产生的进位问题的处理,还有要如何判断当前数字是否是最大的n位数。

 package Solution;

 /**
* 剑指offer面试题12:打印1到最大n位数
* 题目:输入数字n,按顺序打印从1到最大的n位十进制数。
* 比如:输入3,则打印1,2,3一直到999
* 解法一:使用数组表示大数
* @author GL
*
*/
public class No12PrintOneToMaxNthDigits { //使用数组实现对数进行+1操作
public static boolean increment(int[] number){
if(number.length<1)
throw new RuntimeException("invalid lenth of array");
//最高位产生进位标志,则数组中的数为最大的n位整数
boolean isOverFlow=false;
//进位位
int carry=0;
//没有产生进位的+1,循环只运行1次,产生一个进位,循环多运行一次
for(int i=number.length-1;i>=0;i--){
int sum=number[i]+carry;
if(i==number.length-1)
sum++;//最低位+1
if(sum>=10){
//最高位产生进位
if(i==0)
isOverFlow=true;
//普通位产生进位
else{
carry=1;
number[i]=0;
sum=0;
}
}else{
//普通位+1的结果保存到数组中,+1后程序退出循环
number[i]=sum;
break;
}
}
return isOverFlow;
}
//打印数组中表示的数,如果数组中表示的数字位数小于n,则不打印前面的0
public static void print(int[] number){
boolean isBeginning=true;
for(int i=0;i<number.length;i++){
if(isBeginning&&number[i]!=0)
isBeginning=false;
if(!isBeginning)
System.out.print(number[i]);
}
}
public static void main(String[] args) {
int[] number=new int[3];
while(!increment(number)){
print(number);
System.out.println();
}
}
}

数组实现大位数的表示

在实现+1的方法中,使用一个全局变量来表示是否是最大的n位数,也就是当数组的最低位array[0]产生进位的时候就已经达到了n位最大数。另外在实现+1操作时候,如果低位产生进位要将进位位加到高位上。

打印数字采用的是每生成一个数字,判断此数字是否是最大的n位数,如果不是则打印,然后数字+1,再判断打印的过程。

上一篇:2011 ACM 0和1思想


下一篇:JavaScript学习笔记(四)——jQuery插件开发与发布