How to implement the appearance sequence of Go Java algorithm

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;
    }
}

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
}

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!