题目:输入数字n,按顺序打印出从1最大的n位十进制数。比如输入3,则打印出1、2、3一直到最大的3位数即999
错误代码
//error
void PrintToMaxOfNDigits_1(int n){
int number=1;
int i=0;
while (i++<n)
number*=10;
for (i=1;i<number;++i)
System.out.println(i);
}
如果输入n很大,求最大位的n位数是会溢出的,应该考虑大数问题
解决方法:
在字符串中模拟数字加法来‘,几个注意点,如何判断最大,不要调用比较的方式去处理,因为每次比较字符串如果长度为n的字符串他的时间复杂度位O(n),只要对加一进位的时候做逻辑判断就可以了,打印的时候去除开头的0就可以了
//正确写法
public static void printToMaxOfDigst(int n){
if (n<=0){
return;
}
char[] num = new char[n];
for(int i = 0;i<n;i++){
num[i] = '0';
}
while (!increment(num)){
System.out.println(num);
}
}
private static boolean increment(char[] num){
boolean isOverflow = false;
int size = num.length;
int carry = 0;
for(int i = size - 1; i >= 0; i--){
int temp = num[i] - '0' + carry;
if(i == size - 1)
temp++;
if(temp >= 10){
if(i == 0) //最高位溢出
isOverflow = true;
else{
temp -= 10;
carry = 1;
num[i] = (char) ('0' + temp);
}
}else{
num[i] = (char)('0' + temp);
break;
}
}
return isOverflow;
}
public void printNumber(char[] num){
int size = num.length;
int i = 0;
while(i < size && num[i] == '0') //i < size在前,否则越界
i++;
if(i == size)//不打印全0
return;
char[] printNum = Arrays.copyOfRange(num, i, size);//复制数组
System.out.println(printNum);
}
思路2
递归方式去处理,用字符串去模拟整数的加法,思路比较直观,但是代码较长。面试过程不容易完整写出怎么长的代码。如果我们在数字前面补0,就会发现n位所有十进制其实就是n个从0到9的全排列,也就是我们把数字每一位都从0到9进行一次排列,就可以得到所有的十进制数字
public void printToMax2(int n){
if(n <= 0) return;
char[] number = new char[n];
Arrays.fill(number, '0');
printOrder(number,n,0);
}
public void printOrder(char[] number, int n, int loc){
if(loc == n) return;
for(int i = 0; i <= 9; i++){
number[loc] = (char)('0' + i);
if(loc == n - 1){
printNumber(number);
}
printOrder(number,n,loc + 1);
}
}
原文链接:http://blog.csdn.net/qq_22329521/article/details/53164557