This is the fifth day of my participation in the August More text Challenge. For details, see:August is more challenging

preface

The appearance sequence of problem 38 is as follows:

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

An appearance sequence is a sequence of integers, starting with the number 1. Each item in the sequence is a description of the preceding 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.

Example 1:

Input: n = 1 Output: "1" Description: This is a basic example.Copy the code

Example 2:

Input: n = 4 Output: "1211" CountAndSay (1) = "1" countAndSay(2) = "1" = "11" countAndSay(3) = "11" = "21" = "21" countAndSay(4) = "read "21" = a 2 + a 1 = "12" + "11" = "1211"Copy the code

A, thinking

This question is so long that you need to read it twice to understand what it means. There is an important message in this passage:

  • Definition of appearance sequence: a sequence of numeric strings defined by a recursive formula

Since the sequence corresponding to n is a description of the sequence corresponding to the appearance of n-1, it is obvious that we can recursively generate the sequence corresponding to n.

But how to get throughn-1The corresponding appearance sequence is generatednWhat about the appearance sequence?

For example

We can visualize the following example: given that n=4 corresponds to the appearance list of 1211, what is the appearance list of n=5?

Tips: We know that the appearance sequence corresponding to n=5 is a description of n=4, and that the same values need to be linked in the description. For example, there are two consecutive ones in 1211 that need to be read as two ones

The general idea is divided into the following steps:

I =0: I is the traversal index

  1. Walk from left to rightn=4The appearance of the sequence1211.As long as two adjacent values are not equal, the result is recorded
  2. i = 0When, get the string1
  3. i = 1When, get the string2. In this case, the two adjacent values are differentA 1
  4. i = 2When, get the string1. This eat adjacent two values are not the same record resultA 2
  5. i = 3When, get the string1. This eats adjacent values that are the same, but for the last string, perhaps recording the resultTwo 1
  6. The final result isOne 1, one 2, two 1's, i.e.,111221

The above traversal procedure uses double Pointers to effectively reduce the space to store a string, so it is implemented using double Pointers + recursion. .

Second, the implementation

The implementation code

The implementation code is consistent with the idea

public String countAndSay(int n) {
    if (n == 1)
        return "1";
    else {
        String val = countAndSay(n -1);
        returnexplain(val); }}/** * Double pointer: describes a value */
public String explain(String val) {
    StringBuilder sb = new StringBuilder();
    char[] arr = val.toCharArray();
    int left = 0;
    int right = 0;
    while (right < arr.length) {
        / / not equal
        if(arr[left] ! = arr[right]) { sb.append(right - left).append(arr[left]);// Move the left pointer
            left = right;
        }
        // Whether it is the last element
        if (right == arr.length -1) {
            sb.append(right - left + 1).append(arr[left]);
        }
        right ++;
    }
    return sb.toString();
}
Copy the code

The test code

public static void main(String[] args) {
    String ret = new Number38().countAndSay(5);
    System.out.println(ret);
}
Copy the code

The results of

Third, summary

Thank you for seeing the end, it is my great honor to help you ~♥