Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

The title

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 thecountAndSay(n-1)Is then converted to another numeric string.

The first five are as follows:

1. 1, 2. 11, 3. 21, 4. 1211, 5. 111221 The first term is the number 1 that describes the previous term, and this number is 1, "one 1", which is called "11", which describes the previous term, and this number is 11, which is called "21", which describes the previous term, So this number right here is 21 which is "one 2 + one 1", let's call it "1211" to describe the previous term, this number right here is 1211 which is" one 1 + one 2 + two 1s ", let's call it "111221".Copy the code

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:

The sample

Input: n = 1 Output: "1" Explanation: This is a basic example. Input: n = 4 Output: "1211" CountAndSay (1) = "1" countAndSay(2) = read "1" = one 1 = "11" countAndSay(3) = read "11" = two 1 = "21" countAndSay(4) = read "21" = 12 + 11 = "12" + "11" = "1211"Copy the code

prompt

  • 1 <= n <= 30

Their thinking

We can apply the recursive formula to the sequence of strings defined by the recursive formula, the termination conditions, and the recursive derivation.

Recursive template: in which the order of the second and third points can be exchanged, if there is no return value, you can not use the fourth point.

public String method(int n){
    // 1. Termination conditions
    
    // 2
    
    / / 3. Recursion
    
    // 4. Return the result
}
Copy the code

Code implementation

class Solution {
    public String countAndSay(int n) {
        CountAndSay (1) = "1"
        if(n == 1) {return "1";
        }

        // Recursion => countAndSay(n-1)
        String num = countAndSay(n - 1);

        // Process logic
        StringBuilder sb = new StringBuilder();
        The count variable is used to count how many elements are the same
        int count = 1;
        for(int i = 1; i < num.length(); ++i){
            // If it is the same, the sum is added
            if(num.charAt(i) == num.charAt(i - 1)){
                ++count;
            }else{
                // Concatenate the number and value of the preceding elements into a string
                sb.append(count).append(num.charAt(i - 1));
                // Reset statistics
                count = 1; }}// Only the penultimate element is counted, we need to add the last element
        sb.append(count).append(num.charAt(num.length() - 1));

        // Return the result
        returnsb.toString(); }}Copy the code

Complexity analysis

  • O(NM)O(NM)O(NM)
  • Space complexity: O(M)O(M)O(M)

The last

The article has written the bad place, asks the big guys to be generous to give advice, the mistake is the most can let the person grow up, wishes me and the big guy the distance to shorten gradually!

If you feel the article is helpful to you, please click like, favorites, follow, comment four consecutive support, your support is the biggest power of my creation!!

Title source: leetcode-cn.com/problems/co…