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算法外观数列的资料请关注我们其它相关文章！

赞 (0)

相关推荐

  • 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)  } 第

  • 三种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

  • 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 +

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

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

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

    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 Java算法之比较版本号方法详解

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

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

    目录 外观数列 方法一:遍历生成(Java) 方法二:递归(Go) 外观数列 给定一个正整数 n ,输出外观数列的第 n 项. 「外观数列」是一个整数序列,从数字 1 开始,序列中的每一项都是对前一项的描述. 你可以将其视作是由递归公式定义的数字字符串序列: countAndSay(1) = "1" countAndSay(n) 是对 countAndSay(n-1) 的描述,然后转换成另一个数字字符串. 前五项如下: 1.1 —— 第一项是数字 1 2.11 —— 描述前一项,这个数

  • Go Java算法之Excel表列名称示例详解

    目录 Excel表列名称 方法一:数学(Java) 方法一:数学(Go) Excel表列名称 给你一个整数 columnNumber ,返回它在 Excel 表中相对应的列名称. 例如: A -> 1 B -> 2 C -> 3 ... Z -> 26 AA -> 27 AB -> 28 ... 示例 1: 输入:columnNumber = 1 输出:"A" 示例 2: 输入:columnNumber = 28 输出:"AB"

  • Go Java算法之二叉树的所有路径示例详解

    目录 二叉树的所有路径 方法一:深度优先遍历搜索(Java) 方法二:广度优先遍历(Go) 二叉树的所有路径 给你一个二叉树的根节点 root ,按 任意顺序 ,返回所有从根节点到叶子节点的路径. 叶子节点 是指没有子节点的节点. 示例 1: 输入:root = [1,2,3,null,5] 输出:["1->2->5","1->3"] 示例 2: 输入:root = [1] 输出:["1"] 提示: 树中节点的数目在范围 [1,

  • Java中的vector类使用方法示例详解

     基本操作示例 VectorApp.java import java.util.Vector; import java.lang.*; import java.util.Enumeration; public class VectorApp { public static void main(String args[]) { Vector v1 = new Vector(); Integer integer1= new Integer(1); //加入为字符串对象 v1.addElement("

  • Java线程中的关键字和方法示例详解

    Java线程中的关键字和方法示例详解

    目录 一.volatile关键字 1,volatile能保证内存可见性 2,编译器优化问题 二.wait和notify 1,wait()方法 2,notify()方法 3,notifyAll()方法 一.volatile关键字 1,volatile 能保证内存可见性 代码在写入 volatile 修饰的变量的时候 改变线程工作内存中volatile变量副本的值 将改变后的副本的值从工作内存刷新到主内存 代码在读取 volatile 修饰的变量的时候 从主内存中读取volatile变量的最新值到线

  • Java读写文件创建文件夹多种方法示例详解

    出现乱码请修改为 BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream(path), "GBK")); 一.获得控制台用户输入的信息 复制代码 代码如下: public String getInputMessage() throws IOException...{    System.out.println("请输入您的命令∶");    byte buffe

  • Go Java算法之解码方法示例详解

    目录 解码方法 方法一:动态规划(Java) 方法二:动态规划——优化(go) 解码方法 一条包含字母 A-Z 的消息通过以下映射进行了 编码 : 'A' -> "1" 'B' -> "2" ... 'Z' -> "26" 要 解码 已编码的消息,所有数字必须基于上述映射的方法,反向映射回字母(可能有多种方法).例如,"11106" 可以映射为: "AAJF" ,将消息分组为 (1 1 1

  • java算法之二分查找法的实例详解

    java算法之二分查找法的实例详解 原理 假定查找范围为一个有序数组(如升序排列),要从中查找某一元素,如果该元素在此数组中,则返回其索引,否则返回-1.通过数组长度可取出中间位置元素的索引,将其值与目标值比较,如果中间位置元素值大于目标值,则在左部分进行查找,如果中间位置值小于目标值,则在右部分进行查找,如此循环,直到结束.二分查找算法之所以快是因为它没有遍历数组的每个元素,而仅仅是查找部分元素就能找到目标或确定其不存在,当然前提是查找范围为有序数组. Java的简单实现 package me

  • 浅谈使用Java Web获取客户端真实IP的方法示例详解

    Java-Web获取客户端真实IP: 发生的场景:服务器端接收客户端请求的时候,一般需要进行签名验证,客户端IP限定等情况,在进行客户端IP限定的时候,需要首先获取该真实的IP. 一般分为两种情况: 方式一.客户端未经过代理,直接访问服务器端(nginx,squid,haproxy): 方式二.客户端通过多级代理,最终到达服务器端(nginx,squid,haproxy): 客户端请求信息都包含在HttpServletRequest中,可以通过方法getRemoteAddr()获得该客户端IP.

  • Java子线程调用RequestContextHolder.getRequestAttributes()方法问题详解

    Java子线程调用RequestContextHolder.getRequestAttributes()方法问题详解

    相信很多开发过程中都用过RequestContextHolder.getRequestAttributes(),没错,我也经常用,但今天出现了问题,获取到的实例是空的 原因是因为我新开了一个子线程,在子线程调用了RequestContextHolder.getRequestAttributes().实际获取到的是空的 然后查看了源码 ThreadLocal获取.一个请求到达容器后,Spring会把该请求Request实例通过setRequestAttributes方法 把Request实例放入该

随机推荐