剑指Offer：面试题17——打印从1到最大的n位数（java）

打印从1到最大的n位数

问题描述

问题分析

• 首先这道题肯定是不会让你用最简单的循环去做的，但是为什么不能用循环呢？因为这道题并没有说不考虑大数的限制，也就是说使用int或者long可能会导致溢出
• 所以对于大数的情况，我们一般都是用字符数组去模拟数字的加法，这就是算法思路一
• 其次就是可以把问题转化为数字的全排列问题，无非就是对定长的字符数组，每一位都可能取0-9，进行全排列，这样的思路是最优的，但是我没怎么看懂代码实现！

算法思路一：字符数组模拟

• 输入n，使用n+1位的字符数组模拟存储，并且同时进行加1的实现

• 有几个问题是需要注意的：

  • 字符数组必须初始化为‘0’，默认初始化的值看起来为0，实际上在计算的时候会不一样
  • 字符与数字做运算转化的时候必须要 加上或者减 ‘0’ （因为ascll的原因）
  • 每次输出的时候要注意要去掉前面的0
  • 如何判断结束？只需要判断字符数组的第一位是否为1即可，因为我们多用了一位进行存储

 public static void printMaxNum1(int n){
        char[] nums = new char[n+1];
        //初始化
        for(int i = 0; i < n+1; i++) nums[i] = '0';

        while (nums[0] != '1'){ //判断是否结束

            //每次从最后一位开始加1
            for(int i = n; i >= 0; i--){
                int result = nums[i] - '0' + 1;
                //判断进位
                if(result > 9){
                    nums[i] = '0';
                }else {
                    nums[i] = (char) (result + '0');
                    break;
                }

            }

            //输出 将前面的0去掉
            int index = 0;
            for( ; index < n + 1; index++){
                if(nums[index] != '0') break;
            }
           
            if(nums[0] != '1'){ //因为该算法最后一位会打印10000  所以加一个判断
                String str = new String(nums);
                System.out.println(str.substring(index,n+1));
            }

            }



        }

算法思路二（全排列）

• 实际上这个全排列的思想我是清楚地，但是代码实现我是看了挺久都没看懂，这里使用了递归的写法，我就把别人的代码放过来了

 //打印1到最大的n位数的主方法
    public static void printToMaxOfDigits(int n){
        if(n <= 0){
            System.out.println("输入的n没有意义");
            return;
        }
        char number[] = new char[n];
        for (int i = 0; i < number.length; i++) {
            number[i] = '0';
        }
        for (int i = 0; i < 10; ++i) {
            number[0] = (char) (i + '0');
            printToMaxOfNDigitsRecursively(number, n, 0);
        }
    }
    //利用递归实现1到最大的n位数的全排列
    public static void printToMaxOfNDigitsRecursively(char[] number, int n, int index) {
        if(index == n - 1){
            printNumber(number);
            return;
        }
        for (int i = 0; i < 10; ++i) {
            number[index + 1] = (char) (i + '0');
            printToMaxOfNDigitsRecursively(number, n, index + 1);
        }
    }

    //输出
    private static void printNumber(char[] number) {
        boolean isBeginning0 = true;
        int nLength = number.length;
        for (int i = 0; i < nLength; ++i) {
            if(isBeginning0 && number[i]!='0'){
                isBeginning0 = false;
            }
            if(!isBeginning0){
                System.out.print(number[i]);
            }
        }
        System.out.println();
    }

总结

• 写第一种算法的时候遇见了之前没有遇见过的问题，对于不初始化的字符数组，debug的时候发现默认存储的的确是‘0’，但是实际使用 （- ‘0’ + 1 ）方式进行计算的时候会是不一样的结果，我也不知道原因。所以最后还是初始化了
• 字符与数字进行计算的时候，要减去‘0’ ，这个好久没写了，有点忘记了