题目描述

剑指 Offer 17. 打印从1到最大的n位数

难度简单93

输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。

示例 1:

输入: n = 1
输出: [1,2,3,4,5,6,7,8,9]

说明：

• 用返回一个整数列表来代替打印
• n 为正整数

测试用例

• 功能测试（输入1、2、3…）
• 特殊输入测试（输入-1、0）

题目考点

• 考察应聘者解决大数问题的能力。面试官出这道题的时候，他期望应聘者能意识到这是一个大数问题，同时还期待应聘者能定义合适的数据结构表示方式来解决大数问题。

解题思路

在字符串上模拟数字加法的解法

我们用字符串来表示 n ，首先把字符串的每一个数字都转化为‘0’，然后每次为字符串表示的数字加1，再打印出来。因此我们需要做两件事：一是在字符串表示的数字上模拟加法；而是把字符串表示的数字打印出来。

把问题转成数字排列的解法

如果我们在数字前面补零，就会发现 n 位十进制数其实就是 n 个从 0 到 9 的全排列。也就是说，我们把数字的每一个为都从 0 到 9 排列一遍，就得到了所有的十进制数。只是在打印的时候，排在前面的0不打印出来罢了。

普通解题

/**
 * 打印从1到最大的n位数
 *
 */
public class Solution {
    public void print1ToMaxOfNDigits(int n) {
        int number = (int) Math.pow(10, n);
        for (int i = 1; i < number; i++) {
            System.out.println(i);
        }
    }
}

考虑欠缺点：

• 没有考虑n是一个大数，没有意识到这是一个大数问题。
• 没有考虑非法输入，如负数。

参考解题

在字符串上模拟数字加法的解法

/** * 打印从1到最大的n位数 * * @Author rex * 2018/7/22 */
public class Solution1 {
   
    /** * 在字符串上模拟数字加法的解法 * * @param n */
    public void print1ToMaxOfNDigits(int n) {
   
        // 防止非法输入
        if (n <= 0) {
   
            return;
        }
        char[] number = new char[n];
        initCharArray(number);
        while (!increment(number)) {
   
            printNumber(number);
        }
    }

    /** * 字符串表示的数字上模拟加法 * @param number * @return */
    private boolean increment(char[] number) {
   
        // 是否超出999....
        boolean isOverflow = false;
        // 进位数
        int takeOver = 0;
        for (int i = number.length-1; i >= 0; i--) {
   
            int sum = number[i] - '0' + takeOver;
            if (i == number.length-1) {
   
                sum++;
            }
            if (sum >= 10) {
   
                if (i == 0) {
   
                    isOverflow = true;
                } else {
   
                    sum -= 10;
                    takeOver = 1;
                    number[i] = (char) ('0' + sum);
                }
            } else {
   
                number[i] = (char) ('0' + sum);
                break;
            }
        }
        return isOverflow;
    }

    /** * 根据字符串打印出数字 * 这个我一会也想出来 * @param number */
    private void printNumber(char[] number) {
   
        // 默认字符串不以0开始
        boolean isBegining0 = true;

        for (int i = 0; i < number.length; i++) {
   
            if (isBegining0 && number[i] != '0') {
   
                isBegining0 = false;
            }
            if (!isBegining0) {
   
                System.out.print(number[i]);
            }
        }
        System.out.println();
    }

    /** * 初始化字符数组 * * 使其每个字符初始为'0' * @param chars */
    public void initCharArray(char[] chars) {
   
        for (int i = 0; i < chars.length; i++) {
   
            chars[i] = '0';
        }
    }

}

把问题转成数字排列的解法

1.因为要考虑到大数，而int/long的取值范围都是有限的，所以应该用String字符串类型来表示大数，我们先把每个数当成一个size为n的字符数组，得到字符数组后，再字符数组->字符串->整数，转换为整数的过程可以自动把高位的0去掉 2.从第一位开始对每一位数字递归生成全排列，例如：n=2时，固定第一位为0，dfs(1,2),得到00,01,02,03,04，…09, 这些前面有0的字符数组，我们先用String.valueOf方法转换为字符串，再用Integer.valueOf方法转换为整数，然后添加到结果数组中（注意：要先跳过0）

class Solution {
   
    //先定义几个需要用到的全局变量
    //初始化结果数组res
    int[] res; //Math.pow返回的是double
    char[] nums;
    char[] loop = {
   '0','1','2','3','4','5','6','7','8','9'}; 
    int count=0;//数组计数索引
    int x = 0; //x表示递归到第几层
    public int[] printNumbers(int n) {
   
        nums = new char[n];
        res = new int[(int)Math.pow(10,n)-1]; //Math.pow返回的是double
        dfs(x,n);
        return res;
    }

    public void dfs(int x,int n){
     //x表示递归到第几层
        //递归终止条件，x==n,此时要要结果数组res中添加数字
        if(x==n){
   
            String str = String.valueOf(nums);//把字符数组转换为字符串
            int temp =  Integer.valueOf(str); //把字符串转换为整数
            if(temp!=0){
     //跳过0 
                res[count] = temp ;//把字符串转换为整数后添加到结果数组中
                count++; //计数索引加1
                return; 
            }
            return;
        }

        for(char ch:loop){
    //对第x层的数字进行固定，然后继续向下一层递归
            nums[x] = ch;
            dfs(x+1,n);
        }
    }
}

补充

如果面试题是关于 n 位的整数并且没有限定 n 的取值范围，或者输入任意大小的整数，那么这道题很有可能是需要考虑大数问题的。字符串是第一种简单、有效地表示大数的方法。