Appearance of the sequence

Subject address: leetcode-cn.com/problems/co…

Given a positive integer n, prints the NTH term of the appearance sequence.

An appearance sequence is a sequence of integers, starting with 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 to another numeric string.

// The first five items are as follows:
1
11
21
1211
111221
Copy the code

The first term is the number 1

I'm going to describe the previous term, and this number right here is 1 which is "one 1," which I'll call "11."

To describe the previous term, this number is 11 which is two ones, and I'll call it 21.

To describe the previous term, this number is 21 which is "one 2 + one 1," which is called "1211."

To describe the previous term, this number right here is 1211 which is "one 1 + one 2 + two 1's", which is called "111221".

To describe a numeric string, you first split the string into a minimum number of groups, each consisting of at most consecutive identical characters. Then for each group, the number of characters is described first, and then the characters are described, forming a description group. To convert the description to a numeric string, replace the number of characters in each group with a number, and then concatenate all the description groups.

For example, the numeric string “3322251” is described as follows:

Example 1:

Enter n =1Output:"1"Explanation: This is a basic example. * * sample2: ** ' 'Java input: n =4Output:"1211"Explanation: countAndSay (1) = "1"
countAndSay(2) = read"1"= a1 = "11"
countAndSay(3) = read"11"= 21 = "21"
countAndSay(4) = read"21"= a2+ a1 = "12" + "11" = "1211"
Copy the code

Tip:

1 <= n <= 30

Solution 1: violent solution

It’s intuitive to scan a string and count consecutively the same number of digits, then interrupt and re-count them. I end up with a new string and that’s an iteration. The above example takes n iterations, each using the string from the previous one.

public String countAndSay(int n){
    / / daddy
    String str = "1";
    // This iteration string
    StringBuilder result = new StringBuilder();
    // Iterate n times
    for(int c = 1; c < n; c++){
        //1. Clear the iteration string
        result.delete(0,result.length());
        //2. Dual-pointer scan
        int i = 0, j = 0;
        while(i < str.length() && j < str.length()){
            if(str.charAt(i) ! = str.charAt(j)){// Concatenate the same number and corresponding number
                result.append(j - i).append(str.charAt(i));
                i = j;
            }
            if(j == str.length() - 1){
                result.append(j - i + 1).append(str.charAt(i));
            }
            j++;    
        }
        str = result.toString();
    }
    return str;
}
Copy the code

Solution 2: Recursion (Solution 1)

If you want to do it a different way, you could do it n times recursively

public String countAndSay(int n) {
    // Recursive termination condition
    if (n == 1) {
        return "1";
    }
    // This iteration string
    StringBuilder result = new StringBuilder();
    / / daddy
    String str = countAndSay(n - 1);
    // Dual pointer scan
    int i = 0, j = 0;
    while(i < str.length() && j < str.length()){
        if(str.charAt(i) ! = str.charAt(j)){ result.append(j - i).append(str.charAt(i)); i = j; }if(j == str.length() - 1){
            result.append(j - i + 1).append(str.charAt(i));
        }
        j++;    
    }
    return res.toString();
}
Copy the code

Solution three: regular expression

With a little more effort, you can use regular expressions. To match the same number as a group, use Pattern and Matcher in java.util.regex.

"."Is for any character,"/ / 1"Refer to the preceding parentheses"*" 0One or more"(.). 1 \ \ *"The first character is arbitrary and the second character is either the preceding character or none, and the * is followed by the same string as the second character"aaabc"You filter out aaa, B, and CCopy the code

Code:

public String countAndSay(int n) {
    String str = "1";
    Pattern pattern = Pattern.compile("(.). 1 \ \ *");
    for (int i = 1; i < n; i++) {
        Matcher m = pattern.matcher(str);
        StringBuilder result = new StringBuilder();
        while (m.find()) {
            result.append(m.group().length() + String.valueOf(m.group().charAt(0)));
        }
        str = result.toString();
    }
    return str;
}
Copy the code

conclusion

This one is easier to do, because there are no extra steps in the direct solution that are inherently superior. The purpose of using solution three is just to get familiar with some operations and regular expressions in the Java class library. Many operations are redundant, so the efficiency is low. Solution 1 solution 2 in the case of the same time complexity, solution 2 using the system stack space consumption, not too much time difference will be a few operations.