Java教程

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

本文主要是介绍剑指 Offer 17. 打印从1到最大的n位数,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

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

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

示例 1:

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

说明:

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

做题思路:

首先看到这道题,会觉得很简单,因为觉得来一个for循环就可以了,其实如果简单来做是这样的,但就怕是按照大数来写代码,那么这个难度就不言而喻了。

一、简单的方法

class Solution {
    public int[] printNumbers(int n) {
        int[] res = new int[(int)Math.pow(10 , n) - 1];
        for (int i = 0; i < res.length; i++) {
            res[i] = i + 1;
        }
        return res;
    }
}

二、大数打印解法

做题思路:

首先要解决三个问题,参考了leetcodeK神:

  1. 表示大数的变量类型:
    无论是 short / int / long ... 任意变量类型,数字的取值范围都是有限的。因此,大数的表示应用字符串 String 类型。
  2. 生成数字的字符串集:
    使用 int 类型时,每轮可通过 +1+1 生成下个数字,而此方法无法应用至 String 类型。并且, String 类型的数字的进位操作效率较低,例如 "9999" 至 "10000" 需要从个位到千位循环判断,进位 4 次。

观察可知,生成的列表实际上是 nn 位 00 - 99 的 全排列 ,因此可避开进位操作,通过递归生成数字的 String 列表。

  1. 递归生成全排列:
    基于分治算法的思想,先固定高位,向低位递归,当个位已被固定时,添加数字的字符串。例如当 n = 2n=2 时(数字范围 1 - 991−99 ),固定十位为 00 - 99 ,按顺序依次开启递归,固定个位 00 - 99 ,终止递归并添加数字字符串。
class Solution {
        int[] res;
        int nine = 0, start, n,count = 0;
        char[] num,loops = {'0','1','2','3','4','5','6','7','8','9'};
        public int[] printNumbers(int n) {
            this.n = n;
            res = new int[(int)Math.pow(10, n) - 1];
            num = new char[n];//定义长度为n
            start = n - 1;
            dfs(0);//开启全排列递归
            return res;
        }

        void dfs(int x) {
            /*
            主要这倒题,要先了解一下递归生成全排列的思路。
            首先要先固定高位,再向低位递归。
            例如当n=3时(100-999),固定百位为0-9,按顺序依次开启递归,固定十位0-9,固定个位0-9,然后
            终止递归并添加到数字字符串
             */
            if (x == n) {//终止条件:已固定完所有位置
                String s = String.valueOf(num).substring(start);
                if (!s.equals("0"))
                    res[count++] = Integer.parseInt(s);
                if (n - start == nine) //当n=1时 start=0 当n=2时 start=1
                    start--;
                return;
            }
            for(char i : loops) {//遍历0-9
                if(i == '9') nine++; //等到9的时候,再递增到10
                num[x] = i;//固定x位为i
                dfs(x + 1);//并开启固定x+1位
            }
            nine--;//这里是为了在回溯前恢复nine
        }
    }

参考链接:https://leetcode-cn.com/problems/da-yin-cong-1dao-zui-da-de-nwei-shu-lcof/solution/mian-shi-ti-17-da-yin-cong-1-dao-zui-da-de-n-wei-2/(作者:jyd)

这篇关于剑指 Offer 17. 打印从1到最大的n位数的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!