剑指offer面试题17:打印1到最大的n位数(Java 实现)
程序员文章站
2024-03-15 19:16:18
...
题目:输入数字n,按顺序打印出从1到最大的n位十进制数,比如输入3,则打印出1,2,3一直到最大的3位数即999。
测试用例:
- 功能测试:输入1、2、3…
- 特殊测试:输入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));
}
}
}