欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

剑指Offer 12 打印1到最大的n位数

程序员文章站 2024-03-15 19:24:54
...

题目

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

分析

  1. 考虑大数问题;
  2. 在字符串上模拟数字加法的解法;
  3. 终止条件是第一个字符产生了进位,以此快速判断是否结束,而不是比较两个字符串;
  4. 输出时注意去掉补位用的0;
  5. 或者把问题转换成数字排列问题,采用递归。数字的每一位都可能是0-9中的一位数,然后设置下一位。

踩了个坑

Java中的for each不具备赋值作用,只能遍历,相当于赋值给了一个临时变量。

代码

public class PrintWithNumOfDigits {

    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        while (scanner.hasNext()){
            int n=scanner.nextInt();
            print2(n);
        }
    }

    /**
     * 方法一:在字符串上模拟数字加法的解法
     * @param n 几位数
     * @return
     */
    public static void print1(int n){
        if (n<0)
            return;

        char[] digits=new char[n];
        for (int i=0;i<digits.length;i++){
            digits[i]='0';
        }
        while (!increment(digits)){
            printDigits(digits);
        }
        return;
    }

    /**
     * 更新字符数组,并判断是否终止
     * @param digits 字符数组
     * @return
     */
    public static boolean increment(char[] digits){
        boolean isOverFlow=false;
        int nTakeOver=0;
        for (int i=digits.length-1;i>=0;i--){
            int nSum=digits[i]-'0'+nTakeOver;
            if (i==digits.length-1)
                nSum++;
//          进位发生了
            if (nSum>=10){
//              第一位进位了
                if (i==0){
                    isOverFlow=true;
                }
                nTakeOver=1;
                digits[i]='0';
            }
//            不进位时直接退出循环了,所以不需要将nTakeOver置0
            else {
                digits[i]=(char)(digits[i]+1);
                break;
            }
        }
        return isOverFlow;
    }

    /**
     * 打印字符数组,并去除前面的无意义的0
     * @param digits 字符数组
     */
    public static void printDigits(char[] digits){
        boolean start=false;
        for (int i=0;i<=digits.length-1;i++){
            if(!(digits[i]=='0'&&!start)){
                start=true;
            }
            if (start){
                System.out.print(digits[i]);
            }

        }
            System.out.print("\n");
    }

    /**
     * 方法二:全排列方法
     * @param n 几位数
     */
    public static void print2(int n){
        if (n<=0)
            return;
        char[] digits=new char[n];
        for (int i=0;i<10;i++){
            digits[0]=(char)(i+'0');
            recursiveprint(digits,0);
        }

    }

    /**
     * 递归的打印字符数组
     * @param digits 字符数组
     * @param index 发生变化位置的索引
     */
    public static void recursiveprint(char[] digits,int index){
        if (index==digits.length-1){
            printDigits(digits);
            return;
        }
        for (int i=0;i<10;i++){
            digits[index+1]=(char)(i+'0');
            recursiveprint(digits,index+1);
        }
    }
}