搜索
首页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删除
是否有任何威胁或增强Java平台独立性的新兴技术?是否有任何威胁或增强Java平台独立性的新兴技术?Apr 24, 2025 am 12:11 AM

新兴技术对Java的平台独立性既有威胁也有增强。1)云计算和容器化技术如Docker增强了Java的平台独立性,但需要优化以适应不同云环境。2)WebAssembly通过GraalVM编译Java代码,扩展了其平台独立性,但需与其他语言竞争性能。

JVM的实现是什么,它们都提供了相同的平台独立性?JVM的实现是什么,它们都提供了相同的平台独立性?Apr 24, 2025 am 12:10 AM

不同JVM实现都能提供平台独立性,但表现略有不同。1.OracleHotSpot和OpenJDKJVM在平台独立性上表现相似,但OpenJDK可能需额外配置。2.IBMJ9JVM在特定操作系统上表现优化。3.GraalVM支持多语言,需额外配置。4.AzulZingJVM需特定平台调整。

平台独立性如何降低发展成本和时间?平台独立性如何降低发展成本和时间?Apr 24, 2025 am 12:08 AM

平台独立性通过在多种操作系统上运行同一套代码,降低开发成本和缩短开发时间。具体表现为:1.减少开发时间,只需维护一套代码;2.降低维护成本,统一测试流程;3.快速迭代和团队协作,简化部署过程。

Java的平台独立性如何促进代码重用?Java的平台独立性如何促进代码重用?Apr 24, 2025 am 12:05 AM

Java'splatformindependencefacilitatescodereusebyallowingbytecodetorunonanyplatformwithaJVM.1)Developerscanwritecodeonceforconsistentbehavioracrossplatforms.2)Maintenanceisreducedascodedoesn'tneedrewriting.3)Librariesandframeworkscanbesharedacrossproj

您如何在Java应用程序中对平台特定问题进行故障排除?您如何在Java应用程序中对平台特定问题进行故障排除?Apr 24, 2025 am 12:04 AM

要解决Java应用程序中的平台特定问题,可以采取以下步骤:1.使用Java的System类查看系统属性以了解运行环境。2.利用File类或java.nio.file包处理文件路径。3.根据操作系统条件加载本地库。4.使用VisualVM或JProfiler优化跨平台性能。5.通过Docker容器化确保测试环境与生产环境一致。6.利用GitHubActions在多个平台上进行自动化测试。这些方法有助于有效地解决Java应用程序中的平台特定问题。

JVM中的类加载程序子系统如何促进平台独立性?JVM中的类加载程序子系统如何促进平台独立性?Apr 23, 2025 am 12:14 AM

类加载器通过统一的类文件格式、动态加载、双亲委派模型和平台无关的字节码,确保Java程序在不同平台上的一致性和兼容性,实现平台独立性。

Java编译器会产生特定于平台的代码吗?解释。Java编译器会产生特定于平台的代码吗?解释。Apr 23, 2025 am 12:09 AM

Java编译器生成的代码是平台无关的,但最终执行的代码是平台特定的。1.Java源代码编译成平台无关的字节码。2.JVM将字节码转换为特定平台的机器码,确保跨平台运行但性能可能不同。

JVM如何处理不同操作系统的多线程?JVM如何处理不同操作系统的多线程?Apr 23, 2025 am 12:07 AM

多线程在现代编程中重要,因为它能提高程序的响应性和资源利用率,并处理复杂的并发任务。JVM通过线程映射、调度机制和同步锁机制,在不同操作系统上确保多线程的一致性和高效性。

See all articles

热AI工具

Undresser.AI Undress

Undresser.AI Undress

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

AI Clothes Remover

AI Clothes Remover

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

Undress AI Tool

Undress AI Tool

免费脱衣服图片

Clothoff.io

Clothoff.io

AI脱衣机

Video Face Swap

Video Face Swap

使用我们完全免费的人工智能换脸工具轻松在任何视频中换脸!

热工具

螳螂BT

螳螂BT

Mantis是一个易于部署的基于Web的缺陷跟踪工具,用于帮助产品缺陷跟踪。它需要PHP、MySQL和一个Web服务器。请查看我们的演示和托管服务。

EditPlus 中文破解版

EditPlus 中文破解版

体积小,语法高亮,不支持代码提示功能

ZendStudio 13.5.1 Mac

ZendStudio 13.5.1 Mac

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

安全考试浏览器

安全考试浏览器

Safe Exam Browser是一个安全的浏览器环境,用于安全地进行在线考试。该软件将任何计算机变成一个安全的工作站。它控制对任何实用工具的访问,并防止学生使用未经授权的资源。

SublimeText3 Mac版

SublimeText3 Mac版

神级代码编辑软件(SublimeText3)