“This is the 9th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

describe

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 are as follows:

  1. 1
  2. 11
  3. 21
  4. 1211
  5. 111221 the first term is going to be the number 1 that describes the previous term, and this number is going to be 1, so this is going to be 1, so this is going to be 11, so this is going to be 2 1s, so this is going to be 21, so this is going to be 12 + 1, Let’s call it “1211. “To describe the previous term, this number is 1211 so it’s” one 1 + one 2 + two 1’s. “Let’s call it “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:
Input: n = 1 Output: "1" Explanation: This is a basic example.Copy the code
  • Example 2:
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
  • Tip:
  • 1 <= n <= 30

parsing

The second person tells the first number: 1, 1, 11; the third person tells the second number: 2, 21, and so on.

Solution idea: for this kind, according to the above situation to solve, there are repeated operation problems, using recursion to solve the problem, can also be used recursion can also be used to solve the cycle.

Recursive end condition, n == 1 operation: Records the number of occurrences of each digit in the previous number. Returns record data.

Complexity:

  • Time complexity: O(n), where n is the length of the string. The string needs to be traversed backwards at most once.
  • Space complexity: O(1).

The sample

class Solution { public String countAndSay(int n) { if (n == 1) { return "1"; } StringBuilder before =new StringBuilder(countAndSay(n - 1)) ; StringBuilder result = new StringBuilder(""); int count = 1; char target = before.charAt(0); for (int i = 1; i < before.length(); i++) { if (before.charAt(i) ! = target) { result .append(count +""+ target); target = before.charAt(i); count = 1; } else { count++; } } result .append(count +""+ target); return result.toString(); }}Copy the code

Running results:

Result: Yes

Execution time: 52 ms, beating 785% of all Java commits

Memory consumption: 13.1 MB, beating 15.8% of all Java commits