Table of Contents
Appearance sequence
Home Java javaTutorial How to implement the appearance sequence of Go Java algorithm

How to implement the appearance sequence of Go Java algorithm

Apr 18, 2023 pm 09:22 PM
java go

Appearance sequence

Given a positive integer n, output the nth item of the appearance sequence.

"Appearance sequence" is a sequence of integers, starting from the number 1, and each item in the sequence is a description of the previous item.

You can think of it as a sequence of numeric strings defined by a recursive formula:

countAndSay(1) = "1"

countAndSay(n) is a description of countAndSay(n-1), which is then converted into another numeric string.

The first five items are as follows:

  • 1, 1 —— The first item is the number 1

  • 2, 11 - Describe the previous item, this number is 1, that is, "a 1", recorded as "11"

  • 3, 21 - Describe the previous item item, this number is 11, which is "two 1s", recorded as "21"

  • 4, 1211 - describe the previous item, this number is 21, which is "one 2" One 1", recorded as "1211"

  • ##5, 111221 - Describe the previous item, this number is 1211, that is, "one 1, one 2, two 1", recorded as "111221"

Method 1: Traversal generation (Java)

The so-called "appearance sequence" is actually just counting the consecutive numbers of the same characters in the string. number.

The numerical string sequence defined by the recursive formula given in the question is as follows:

countAndSay(1) = "1";

countAndSay(n) is Description of countAndSay(n-1) and then converted to another numeric string.

We define the string S_{i} to represent countAndSay(i). If we require S_{n}, we need to find S_{n-1} first, and then follow the above description Method generation, that is, scanning the maximum number of consecutive identical characters in the string S_{n-1} from left to right, then converting the statistical number of characters into a numerical string and concatenating the corresponding characters.

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;
    }
}
Copy after login

N is a given positive integer, M is the maximum length of the generated string

Time complexity: O(N * M)

Space complexity :O(M)

Method 2: Recursive (Go)

The specific method analysis has been stated above

Since the data obtained each time comes from the above The result is one time, so we can assume that we have obtained the last result and then proceed with the operation. This uses recursion.

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
}
Copy after login

N is a given positive integer, M is the maximum length of the generated string

Time complexity: O(N * M)

Space complexity :O(M)

The above is the detailed content of How to implement the appearance sequence of Go Java algorithm. For more information, please follow other related articles on the PHP Chinese website!

Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn

Hot AI Tools

Undresser.AI Undress

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

AI Clothes Remover

Online AI tool for removing clothes from photos.

Undress AI Tool

Undress AI Tool

Undress images for free

Clothoff.io

Clothoff.io

AI clothes remover

AI Hentai Generator

AI Hentai Generator

Generate AI Hentai for free.

Hot Article

R.E.P.O. Energy Crystals Explained and What They Do (Yellow Crystal)
2 weeks ago By 尊渡假赌尊渡假赌尊渡假赌
Repo: How To Revive Teammates
4 weeks ago By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island Adventure: How To Get Giant Seeds
4 weeks ago By 尊渡假赌尊渡假赌尊渡假赌

Hot Tools

Notepad++7.3.1

Notepad++7.3.1

Easy-to-use and free code editor

SublimeText3 Chinese version

SublimeText3 Chinese version

Chinese version, very easy to use

Zend Studio 13.0.1

Zend Studio 13.0.1

Powerful PHP integrated development environment

Dreamweaver CS6

Dreamweaver CS6

Visual web development tools

SublimeText3 Mac version

SublimeText3 Mac version

God-level code editing software (SublimeText3)

Square Root in Java Square Root in Java Aug 30, 2024 pm 04:26 PM

Guide to Square Root in Java. Here we discuss how Square Root works in Java with example and its code implementation respectively.

Perfect Number in Java Perfect Number in Java Aug 30, 2024 pm 04:28 PM

Guide to Perfect Number in Java. Here we discuss the Definition, How to check Perfect number in Java?, examples with code implementation.

Random Number Generator in Java Random Number Generator in Java Aug 30, 2024 pm 04:27 PM

Guide to Random Number Generator in Java. Here we discuss Functions in Java with examples and two different Generators with ther examples.

Weka in Java Weka in Java Aug 30, 2024 pm 04:28 PM

Guide to Weka in Java. Here we discuss the Introduction, how to use weka java, the type of platform, and advantages with examples.

Armstrong Number in Java Armstrong Number in Java Aug 30, 2024 pm 04:26 PM

Guide to the Armstrong Number in Java. Here we discuss an introduction to Armstrong's number in java along with some of the code.

Smith Number in Java Smith Number in Java Aug 30, 2024 pm 04:28 PM

Guide to Smith Number in Java. Here we discuss the Definition, How to check smith number in Java? example with code implementation.

Java Spring Interview Questions Java Spring Interview Questions Aug 30, 2024 pm 04:29 PM

In this article, we have kept the most asked Java Spring Interview Questions with their detailed answers. So that you can crack the interview.

Break or return from Java 8 stream forEach? Break or return from Java 8 stream forEach? Feb 07, 2025 pm 12:09 PM

Java 8 introduces the Stream API, providing a powerful and expressive way to process data collections. However, a common question when using Stream is: How to break or return from a forEach operation? Traditional loops allow for early interruption or return, but Stream's forEach method does not directly support this method. This article will explain the reasons and explore alternative methods for implementing premature termination in Stream processing systems. Further reading: Java Stream API improvements Understand Stream forEach The forEach method is a terminal operation that performs one operation on each element in the Stream. Its design intention is

See all articles