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

Topic describes

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 the number 1 describing the previous term. Let's call it "21, "so this number right over here is 21 so it's" one 2 + one 1, "let's call it "1211," so it's "one 1 + one 2 + two ones," 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:

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

Thinking process

1. At the beginning, we split int into numbers to judge before and after, and then splice int again. Let’s loop through it.

It was later incorrectly reported that the length was not enough..

2. With array storage, the length is sufficient. Use arrays instead of storing ints, then loop through the array and evaluate it before and after.

3. In comments, you can use a string to directly store data, which further saves space

Answer key

1. Use array storage

Use the collection to store the results of the loop, carried into the loop again as an input parameter.

  • Initialize the array to 1, perform one operation, so the number of inputs is -1;
  • Adds one bit to the end of the array to prevent overflow when comparing with the next bit. And the loop ends after the last bit, so the logic fires if the comparison to the end is not the same
  • The inner loop completes, replacing the old array with the new one.
  • The loop completes, flips the array, and then converts it to a string
List<Integer> integers = new ArrayList<>(); // initialize the array to 1 integers. Add (1); For (int I = 0; int I = 0; i < n - 1; i++) { int tem = 0; Int count = 1; List<Integer> integers1 = new ArrayList<>(); int resultCount = integers.size(); // Add one bit to prevent overflow of array.add (0); for (int j = 0; j < resultCount; j++) { if (tem == 0) { tem = integers.get(j); } if (tem == integers.get(j+1)) { count ++; } else { integers1.add(tem); integers1.add(count); count = 1; tem = 0; } } integers = integers1; } Collections.reverse(integers); StringBuilder StringBuilder = new StringBuilder(); for (int ns : integers) { stringBuilder.append(ns); } return stringBuilder.toString();Copy the code

2. Use String

Improvement:

  • When temp is 0, the current element is stored. When temp is different, the current element is changed to 0. → The first element is stored. When temp is not used, a different variable is stored.
  • Add a 0 to the end of the array to prevent overflow, so when the last bit is reached it must be different and out of the loop → the end of the loop, and the final result is stored in the string
  • Use array storage, and finally convert to string. → Directly store data in string, convert to char array, and finally output directly
StringBuilder temp = new StringBuilder("1"); char[] chars = null; char c = ' '; for (int i = 0; i < n -1; i++) { int count = 1; chars = temp.toString().toCharArray(); // Store unused elements. When comparisons are not equal, different values are stored. C = chars[0]; temp = new StringBuilder(""); for (int j = 1; j < chars.length; j++) { if (c == chars[j]) { count ++; } // If not equal, write and reset else {temp.append(c); temp.append(count); count = 1; c = chars[j]; }} // Save the last data to temp.append(c); temp.append(count); } return temp.reverse().toString();Copy the code