Go Java算法之外观数列实现方法示例详解

目录
  • 外观数列
  • 方法一:遍历生成(Java)
  • 方法二:递归(Go)

外观数列

给定一个正整数 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算法之外观数列实现方法示例详解的详细内容,更多关于Go Java算法外观数列的资料请关注我们其它相关文章!

时间: 2022-08-09

Go&nbsp;Java算法之从英文中重建数字示例详解

目录 从英文中重建数字 Java实现 Go实现 从英文中重建数字 给你一个字符串 s ,其中包含字母顺序打乱的用英文单词表示的若干数字(0-9).按 升序 返回原始的数字. 示例 1: 输入:s = "owoztneoer" 输出:"012" 示例 2: 输入:s = "fviefuro" 输出:"45" 提示: 1 <= s.length <= 105 s[i] 为 ["e","g&

Go语言实现Fibonacci数列的方法

本文实例讲述了Go语言实现Fibonacci数列的方法.分享给大家供大家参考.具体如下: Fibonacci数列:1,1,2,3,5,8,13,21,,, (即从第三项起,每一项的值都等于前两项之后) 第一种,使用递归: 复制代码 代码如下: func fibonacci(a int) int {      if a == 1 || a == 2 {          return 1      }      return fibonacci(a-1) + fibonacci(a-2)  } 第

Go Java算法之交错字符串示例详解

目录 交错字符串 方法一:动态规划(Java) 方法一:动态规划(GO) 交错字符串 给定三个字符串 s1.s2.s3,请你帮忙验证 s3 是否是由 s1 和 s2 交错 组成的. 两个字符串 s 和 t 交错 的定义与过程如下,其中每个字符串都会被分割成若干 非空 子字符串: s = s1 + s2 + ... + sn t = t1 + t2 + ... + tm |n - m| <= 1 交错 是 s1 + t1 + s2 + t2 + s3 + t3 + ... 或者 t1 + s1 +

三种java编程方法实现斐波那契数列

题目要求:编写程序在控制台输出斐波那契数列前20项,每输出5个数换行 //java编程:三种方法实现斐波那契数列 //其一方法: public class Demo2 { // 定义三个变量方法 public static void main(String[] args) { int a = 1, b = 1, c = 0; System.out.println("斐波那契数列前20项为:"); System.out.print(a + "\t" + b + &qu

Java实现全排列的三种算法详解

目录 算法一 算法二 算法三 算法一 基于递归与回溯实现.在排列1,2,3的时候,先由3向上回溯到2发现没有其他可能的情况,再回溯到1,排列为1,3,2再向上回溯到存在其他情况时,即根节点然后再排列以2为第一位的情况,重复上述过程将所有可能结果全部放入res中. 代码: import java.util.ArrayList; import java.util.List; public class h618_1 { static List<List<Integer>> res = n

Go&nbsp;Java算法之比较版本号方法详解

目录 比较版本号 方法一:字符串切割(Java) 方法二:双指针(Go) 比较版本号 给你两个版本号 version1 和 version2 ,请你比较它们. 版本号由一个或多个修订号组成,各修订号由一个 '.' 连接.每个修订号由 多位数字 组成,可能包含 前导零 .每个版本号至少包含一个字符. 修订号从左到右编号,下标从 0 开始,最左边的修订号下标为 0 ,下一个修订号下标为 1 ,以此类推.例如,2.5.33 和 0.1 都是有效的版本号. 比较版本号时,请按从左到右的顺序依次比较它们的

Java AtomicInteger类的使用方法详解

首先看两段代码,一段是Integer的,一段是AtomicInteger的,为以下: public class Sample1 { private static Integer count = 0; synchronized public static void increment() { count++; } } 以下是AtomicInteger的: public class Sample2 { private static AtomicInteger count = new AtomicIn

java 中enum的使用方法详解

java 中enum的使用方法详解 enum 的全称为 enumeration, 是 JDK 1.5 中引入的新特性,存放在 java.lang 包中. 下面是我在使用 enum 过程中的一些经验和总结. 原始的接口定义常量 public interface IConstants { String MON = "Mon"; String TUE = "Tue"; String WED = "Wed"; String THU = "Thu

Java 读取外部资源的方法详解及实例代码

Java 读取外部资源的方法详解 在Java代码中经常有读取外部资源的要求:如配置文件等等,通常会把配置文件放在classpath下或者在web项目中放在web-inf下. 1.从当前的工作目录中读取: try { BufferedReader in = new BufferedReader(new InputStreamReader(new FileInputStream("wkdir.txt"))); String str; while ((str = in.readLine())

Java this 关键字的使用方法详解

Java this 关键字的使用方法详解 构造方法中的this关键字 构造方法是一个类的对象在通过new关键字创建时自动调用的,在程序中不能向调用其他方法一样通过方法名(也就是类名)来调用.但如果一个类有多个构造方法,可以在一个构造方法中通过this(paras-)来调用其他的构造方法. 使用this来调用其他构造方法有如下几个约束. 1) 只能在构造方法中通过this来调用其他构造方法,普通方法中不能使用. 2) 不能通过this递归调用构造方法,即不能在一个构造方法中通过this直接或间接调

java 中迭代器的使用方法详解

java 中迭代器的使用方法详解 前言: 迭代器模式将一个集合给封装起来,主要是为用户提供了一种遍历其内部元素的方式.迭代器模式有两个优点:①提供给用户一个遍历的方式,而没有暴露其内部实现细节:②把元素之间游走的责任交给迭代器,而不是聚合对象,实现了用户与聚合对象之间的解耦. 迭代器模式主要是通过Iterator接口来管理一个聚合对象的,而用户使用的时候只需要拿到一个Iterator类型的对象即可完成对该聚合对象的遍历.这里的聚合对象一般是指ArrayList,LinkedList和底层实现为数

java编程abstract类和方法详解

抽象类和抽象方法常用知识点: (1)抽象类作为被继承类,子类必须实现抽象类中的所有抽象方法,除非子类也为抽象类. 也就是说,如果子类也为抽象类,可以不实现父类中的抽象方法.但是,如果有一个非抽象类 继承于抽象子类,需要实现抽象子类,抽象子类的抽象父类的所有抽象方法,新帐旧账一起算. (2)抽象类不能用final进行修饰. (3)抽象类不能被实例化,也就是说你用的时候不能通过new关键字创建. (4)抽象类中可以包含抽象方法和非抽象方法,抽象方法没有方法体,也就是没有具体实现, 只是定义了有什么功

Java线程三种命名方法详解

这篇文章主要介绍了Java线程三种命名方法详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 1.实例化一个线程对象 Thread t = new Thread(); t.setName("甲"); 2.实例化一个线程对象的同时,通过构造方法对线程进行命名 Thread(Runnable r, String name) Thread t = new Thread(() -> {}, "甲"); 3.使用自定义

Java贪心算法之Prime算法原理与实现方法详解

本文实例讲述了Java贪心算法之Prime算法原理与实现方法.分享给大家供大家参考,具体如下: Prime算法:是一种穷举查找算法来从一个连通图中构造一棵最小生成树.利用始终找到与当前树中节点权重最小的边,找到节点,加到最小生成树的节点集合中,直至所有节点都包括其中,这样就构成了一棵最小生成树.prime在算法中属于贪心算法的一种,贪心算法还有:Kruskal.Dijkstra以及哈夫曼树及编码算法. 下面具体讲一下prime算法: 1.首先需要构造一颗最小生成树,以及两个节点之间的权重数组,在

Java笛卡尔积算法原理与实现方法详解

本文实例讲述了Java笛卡尔积算法原理与实现方法.分享给大家供大家参考,具体如下: 笛卡尔积算法的Java实现: (1)循环内,每次只有一列向下移一个单元格,就是CounterIndex指向的那列. (2)如果该列到尾部了,则这列index重置为0,而CounterIndex则指向前一列,相当于进位,把前列的index加一. (3)最后,由生成的行数来控制退出循环. public class Test { private static String[] aa = { "aa1", &q

Java中ArrayList的removeAll方法详解

本文介绍的是关于Java中ArrayList的removeAll方法的相关内容,分享出来供大家参考学习,下面来一起看看详细的介绍: 在开发过程中,遇到一个情况,就是从所有骑手Id中过滤没有标签的骑手Id(直接查询没有标签的骑手不容易实现), List<Integer> allRiderIdList = new ArrayList(); // 所有的骑手,大致有23W数据 List<Integer> hasAnyTagRiderId = new ArrayList(); // 有标签