(剑指Offer)面试题12:打印1到最大的n位数

时间:2022-08-13 14:52:23

题目:

输入数字n,按顺序打印出从1到最大的n位十进制数。

比如输入3,打印1,2,3一直到最大的3位数即999。

思路:

1、不考虑n的范围,直接打印。

void Print1ToMaxOfNDigits_1(int n){
int number=1;
for(int i=0;i<n)
number=10*number;
for(int i=1;i<number;i++)
cout<<i<<"\t";
cout<<endl;
}

2、如果n很大,能表示范围超出了int 或者long long的范围,那么就需要考虑大数问题。

最常用也是最容易的方法就是用字符串或者数组来表示大数。

数字最大为n位,因此我们需要一个n+1长度的字符串来存储,最后一位为结束符号'\0',实际位数不够n位时,在字符串前部分补‘0’.(打印的时候将前面的'0'去掉)

步骤:

1、字符串每一位都初始化为‘0’;

2、每一次为字符串表示的数字+1,如果没有超出范围,则打印出来;

如何判断有没有溢出?+

当字符串表示的第一位数即最高位,(最高位+进位)大于或等于10,即判断溢出。

如何打印字符串?

打印字符串时,需要将前部分的'0'省略掉。

递归实现:

n位所有十进制数其实就是n个从0到9的全排列。即把数字的每一位都从0到9排列一遍,就得到了所有的十进制数。

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

代码:

#include <iostream>
#include <string.h> using namespace std; bool Increment(char* number){
bool isOverflow=false;
int nTakeOver=0;
int nLength=strlen(number);
int nSum; for(int i=nLength-1;i>=0;i--){
nSum=number[i]-'0'+nTakeOver;
if(i==nLength-1)
nSum++;
if(nSum>=10){
if(i==0)
isOverflow=true;
else{
nSum=nSum-10;
nTakeOver=1;
number[i]='0'+nSum;
}
}
else{
number[i]='0'+nSum;
break;
}
}
return isOverflow;
} void PrintNumber(char* number){
int i=0;
int length=strlen(number);
while(number[i]=='0')
i++;
for(int j=i;j<length;j++)
cout<<number[j];
cout<<"\t";
} void Print1ToMaxOfNDigits(int n){
if(n<=0)
return;
char* number=new char[n+1];
memset(number,'0',n);
number[n]='\0'; while(!Increment(number))
PrintNumber(number); delete number;
} void Print1ToMaxOfNDigits_1(int n){
int number=1;
for(int i=0;i<n)
number=10*number;
for(int i=1;i<number;i++)
cout<<i<<"\t";
cout<<endl;
} int main()
{
Print1ToMaxOfNDigits(3);
return 0;
}
#include <iostream>
#include <string.h> using namespace std; void PrintNumber(char* number){
int i=0;
int length=strlen(number);
while(number[i]=='0')
i++;
for(int j=i;j<length;j++)
cout<<number[j];
cout<<"\t";
} void Print1ToMaxOfNDigits_recursively(char* number,int length,int index){
if(index==length){
PrintNumber(number);
return;
}
for(int i=0;i<10;i++){
number[index]='0'+i;
Print1ToMaxOfNDigits_recursively(number,length,index+1);
}
} void Print1ToMaxOfNDigits_2(int n){
if(n<=0)
return;
char* number=new char[n+1];
number[n]='\0';
Print1ToMaxOfNDigits_recursively(number,n,0);
delete number;
} int main()
{
Print1ToMaxOfNDigits_2(3);
return 0;
}