189 8069 5689

java如何实现字典序排数

这篇文章主要为大家展示了java如何实现字典序排数,内容简而易懂,条理清晰,希望能够帮助大家解决疑惑,下面让小编带大家一起来研究并学习一下“java如何实现字典序排数”这篇文章吧。

创新互联主要从事做网站、网站设计、网页设计、企业做网站、公司建网站等业务。立足成都服务包河,十多年网站建设经验,价格优惠、服务专业,欢迎来电咨询建站服务:028-86922220

给定一个整数 n, 返回从 1 到 n 的字典顺序。

例如,

给定 n =13,返回 [1,10,11,12,13,2,3,4,5,6,7,8,9] 。

请尽可能的优化算法的时间复杂度和空间复杂度。输入的数据 n 小于等于 5,000,000。

答案:

 1public List lexicalOrder(int n) {
2    List res = new ArrayList<>();
3    for (int i = 1; i < 10; ++i) {
4        dfs(i, n, res);
5    }
6    return res;
7}
8
9public void dfs(int cur, int n, List res) {
10    if (cur > n)
11        return;
12    res.add(cur);
13    for (int i = 0; i < 10; ++i) {
14        dfs(10 * cur + i, n, res);
15    }
16}

解析:

解这题之前实现要明白什么是字典序,其实就是类似于字典一样,根据字母的顺序进行排列,我们先来看下面的图

java如何实现字典序排数

我们可以把它看成有9棵树,每棵树的根节点的值分别是从1到9,并且每棵树都有10个子节点,并且每个子节点又会有10个子节点……

1,代码3到5行分别遍历这9棵树。

2,方法dfs对每棵树执行dfs(深度优先搜索),关于树的深度优先搜索可以参考前面介绍过的304,完全二叉树的节点个数这道题第二种解法使用的就是深度优先搜索(dfs)

我们仔细观察上面的图,字典序排数有一个规律,比如当n等于300的时候,结果是下面这样的

java如何实现字典序排数

我们可以观察上面的数字,也可以查看最上面的图,就会发现这样一个规律。当数字curr小于n的时候,只要curr的个位数是9,那么他的下一个数就是(curr/10)+1(但要保证curr/10的个位数不能是9,如果是9就继续执行curr/10,直到curr/10的个位数不是9为止,比如199的下一个数是2),比如109的下一个是11,129的下一个是13一样。如果curr等于n,那么他的下一个数也是和上面同样的操作。理解了这点,代码就很容易写出来了

 1public List lexicalOrder(int n) {
2    List ans = new ArrayList<>(n);
3    int curr = 1;
4    for (int i = 1; i <= n; ++i) {
5        ans.add(curr);
6        if (curr * 10 <= n) {
7            curr *= 10;
8        } else {
9            while (curr % 10 == 9 || curr == n)
10                curr /= 10;
11            curr++;
12        }
13    }
14    return ans;
15}

重点是在第9到10行,如果curr的个位数是9或者curr等于n就要执行curr/10这步操作,直到curr的个位数不是9为止。

Java的优点是什么

1. 简单,只需理解基本的概念,就可以编写适合于各种情况的应用程序;2. 面向对象;3. 分布性,Java是面向网络的语言;4. 鲁棒性,java提供自动垃圾收集来进行内存管理,防止程序员在管理内存时容易产生的错误。;5. 安全性,用于网络、分布环境下的Java必须防止病毒的入侵。6. 体系结构中立,只要安装了Java运行时系统,就可在任意处理器上运行。7. 可移植性,Java可以方便地移植到网络上的不同机器。8.解释执行,Java解释器直接对Java字节码进行解释执行。

以上就是关于“java如何实现字典序排数”的内容,如果该文章对您有所帮助并觉得写得不错,劳请分享给您的好友一起学习新知识,若想了解更多相关知识内容,请多多关注创新互联行业资讯频道。


标题名称:java如何实现字典序排数
转载注明:http://cdxtjz.cn/article/gpjeho.html

其他资讯