搜索
首页Javajava教程Go Java算法之外观数列如何实现

外观数列

给定一个正整数 n ,输出外观数列的第 n 项。

「外观数列」是一个整数序列,从数字 1 开始,序列中的每一项都是对前一项的描述。

你可以将其视作是由递归公式定义的数字字符串序列:

countAndSay(1) = "1"

countAndSay(n) 是对 countAndSay(n-1) 的描述,然后转换成另一个数字字符串。

前五项如下:

  • 1、1 —— 第一项是数字 1

  • 2、11 —— 描述前一项,这个数是 1 即 “ 一 个 1 ”,记作 "11"

  • 3、21 —— 描述前一项,这个数是 11 即 “ 二 个 1 ” ,记作 "21"

  • 4、1211 —— 描述前一项,这个数是 21 即 “ 一 个 2 一 个 1 ” ,记作 "1211"

  • 5、111221 —— 描述前一项,这个数是 1211 即 “ 一 个 1 一 个 2 二 个 1 ” ,记作 "111221"

方法一:遍历生成(Java)

所谓的「外观数列」,其实本质上只是依次统计字符串中连续相同字符的个数。

题目中给定的递归公式定义的数字字符串序列如下:

countAndSay(1) = "1";

countAndSay(n) 是对 countAndSay(n-1) 的描述,然后转换成另一个数字字符串。

我们定义字符串 S_{i}表示countAndSay(i),我们如果要求得 S_{n},则我们需先求出 S_{n-1},然后按照上述描述的方法生成,即从左到右依次扫描字符串 S_{n-1}中连续相同的字符的最大数目,然后将字符的统计数目转化为数字字符串再连接上对应的字符。

class Solution {
    public String countAndSay(int n) {
        String str = "1";
        for (int i = 2; i <= n; ++i) {
            StringBuilder sb = new StringBuilder();
            int start = 0;
            int pos = 0;
            while (pos < str.length()) {
                while (pos < str.length() && str.charAt(pos) == str.charAt(start)) {
                    pos++;
                }
                sb.append(Integer.toString(pos - start)).append(str.charAt(start));
                start = pos;
            }
            str = sb.toString();
        }
        return str;
    }
}

N 为给定的正整数,M 为生成的字符串中的最大长度

时间复杂度:O(N * M)

空间复杂度:O(M)

方法二:递归(Go)

具体的方法分析已经在上文中表述

由于每次得到的数据都是来源于上一次的结果,所以我们可以假设得到了上次的结果,继而往后运算。这就运用到了递归。

func countAndSay(n int) string {
    if n == 1 {
        return "1"
    }
    s := countAndSay(n - 1)
    i, res := 0, ""
    length := len(s)
    for j := 0; j < length; j++ {
        if s[j] != s[i] {
            res += strconv.Itoa(j-i) + string(s[i])
            i = j
        }
    }
    res += strconv.Itoa(length-i) + string(s[i])
    return res
}

N 为给定的正整数,M 为生成的字符串中的最大长度

时间复杂度:O(N * M)

空间复杂度:O(M)

以上是Go Java算法之外观数列如何实现的详细内容。更多信息请关注PHP中文网其他相关文章!

声明
本文转载于:亿速云。如有侵权,请联系admin@php.cn删除

热AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智能驱动的应用程序,用于创建逼真的裸体照片

AI Clothes Remover

AI Clothes Remover

用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool

Undress AI Tool

免费脱衣服图片

Clothoff.io

Clothoff.io

AI脱衣机

AI Hentai Generator

AI Hentai Generator

免费生成ai无尽的。

热门文章

R.E.P.O.能量晶体解释及其做什么(黄色晶体)
1 个月前By尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.最佳图形设置
1 个月前By尊渡假赌尊渡假赌尊渡假赌
威尔R.E.P.O.有交叉游戏吗?
1 个月前By尊渡假赌尊渡假赌尊渡假赌

热工具

DVWA

DVWA

Damn Vulnerable Web App (DVWA) 是一个PHP/MySQL的Web应用程序,非常容易受到攻击。它的主要目标是成为安全专业人员在合法环境中测试自己的技能和工具的辅助工具,帮助Web开发人员更好地理解保护Web应用程序的过程,并帮助教师/学生在课堂环境中教授/学习Web应用程序安全。DVWA的目标是通过简单直接的界面练习一些最常见的Web漏洞,难度各不相同。请注意,该软件中

PhpStorm Mac 版本

PhpStorm Mac 版本

最新(2018.2.1 )专业的PHP集成开发工具

SublimeText3 英文版

SublimeText3 英文版

推荐:为Win版本,支持代码提示!

SecLists

SecLists

SecLists是最终安全测试人员的伙伴。它是一个包含各种类型列表的集合,这些列表在安全评估过程中经常使用,都在一个地方。SecLists通过方便地提供安全测试人员可能需要的所有列表,帮助提高安全测试的效率和生产力。列表类型包括用户名、密码、URL、模糊测试有效载荷、敏感数据模式、Web shell等等。测试人员只需将此存储库拉到新的测试机上,他就可以访问到所需的每种类型的列表。

ZendStudio 13.5.1 Mac

ZendStudio 13.5.1 Mac

功能强大的PHP集成开发环境