面试题 12

1 题目描述

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

2 解法描述

1 乍看之下的解法

public static void  print12Max(int n){
    int result=1;
    int i;
    if(n<=0) return;
    for(i=0;i<n;i++){
        result*=10;
    }   
    for(i=1;i<result;i++){
        System.out.println(i);
    }
}

存在问题；当 n 值很大时会导致越界出现错误情况，没有考虑大数情况

2 在字符数组上模拟数字加法，解决大数溢出问题

public static void  print12Max_1(int n){
    //用长度为 n 的字符数组表示数字
    char[] number=new char[n];
    int i;
    if(n<=0) return;
    for(i=0;i<n;i++){
        number[i]='0';
    }
    while(increment(number)){
        printResult(number);
    }

}


private static boolean increment(char[] number){
    boolean overflow=true;
    int takeover=0;
    int i;
    int len=number.length-1;
    for(i=len;i>=0;i--){
        int sum=number[i]-'0'+takeover;
        if(i==len){
            sum++;
        }
        if(sum>=10){
            if(i==0){
                overflow=false;
                break;
            }else{
                number[i]='0';
                takeover=1;
            }
        }else{
            number[i]=(char) (sum+'0');
            break;
        }               
    }       
    return overflow;
}
private static void printResult(char[] number){
    boolean flag=true;
    for(int i=0;i<number.length;i++){
        if(number[i]=='0'&&flag){
        }else{
            flag=false;
            System.out.print(number[i]);
        }
    }
    System.out.println();
}

上述代码使用字符数组模拟整数的加法，代码有点长，接下来换一种思路来考虑这个问题，n 位所有的十进制数其实就是 n 个从 0 到 9 的全排列，也就谁说，我们把数字的每一位从 0 到 9 排列一遍，就得到了所有的十进制数，只是打印的时候，数字排在前面的 0 不打印出来。
比如 n=10 时
依次打印
0000000001
……
0000000009
0000000010
……
9999999999

public static void  print12Max_2(int n){
    if(n<=0) return;
    char[] number=new char[n];
    for(int i=0;i<n;i++){
        number[i]='0';
    }
    for(int i=0;i<10;i++){
        number[0]=(char) (i+'0');
        showRecursive(number,0);
    }
}

private static void showRecursive(char[] number,int index){
    if(index==number.length-1){
        printResult(number);
        return;
    }

    for(int i=0;i<10;i++){
        number[1+index]=(char) (i+'0');
        showRecursive(number,index+1);
    }
}