• Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.
  • This article has participated in the “Digitalstar Project” and won a creative gift package to challenge the creative incentive money.

Leetcode-38 – Appearance sequence

[Blog link]

The path to learning at 🐔

The nuggets home page

[答 案]

Topic link

[making address]

Making the address

[B].

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
    1. 11
    1. 21
    1. 1211
    1. 111221

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:

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

Idea 1: Clock

  • Because the data set is so small, only 30, we can easily tabulate it
class Solution {
    public String countAndSay(int n) {
        String[] arr = {
            ""."1"."11"."21"."1211"."111221"."312211"."13112221"."1113213211"."31131211131221"."13211311123113112211"."11131221133112132113212221"."3113112221232112111312211312113211"."1321132132111213122112311311222113111221131221"."11131221131211131231121113112221121321132132211331222113112211"."311311222113111231131112132112311321322112111312211312111322212311322113212221"."132113213221133112132113311211131221121321131211132221123113112221131112311332111213211322211312113211"."11131221131211132221232112111312212321123113112221121113122113111231133221121321132132211331121321231231121113122113322 113111221131221"."31131122211311123113321112131221123113112211121312211213211321322112311311222113311213212322211211131221131211132221232 112111312111213111213211231131122212322211331222113112211"."13211321322113311213212312311211131122211213211321223112111311222112111312211312111322211213211321322123211211131211121 33221123113112221131112311332111213122112311311123112111331121113122112132113213211121332212311322113212221"."11131221131211132221232112111312111213111213211231132132211211131221131211221321123113213221123113112221131112311332211 211131221131211132211121312211231131112311211232221121321132132211331121321231231121113112221121321133112132112312321123 113112221121113122113121113123112112322111213211322211312113211"."31131122211311123113321112131221123113111231121113311211131221121321131211132221123113112221131112212211131221121321131 211132221121321132132211331121321232221123113112221131112311322311211131122211213211331121321122112133221121113122113121 113222123211211131211121311121321123113213221121113122123211211131221121311121312211213211321322112311311222113111231131 1121321122112132231121113122113322113111221131221"."13211321322113311213212312311211131122211213211331121321123123211231131122211211131221131112311332211213211321322113312 211223113112221121113122113111231133221121113122113121113222123211211131211121332211213211321322113311213211322132112311 321322112111312212321121113122122211211232221123113112221131112311332111213122112311311123112111331121113122112132113121 113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132211331121321133112111312212 2211211132213211231131122212322211331222113112211"."11131221131211132221232112111312111213111213211231132132211211131221232112111312211213111213122112132113213221123113112 221133112132123222112111312211312111322212311222122132113213221123113112221133112132123222112311311222113111231133211121 312211231131112311211232221121113122113121113222123211211131221132211131221121321131211132221123113112211121312211231131 122113221122112133221121321132132211331121321231231121113112221121321133112132112312321123113112221121113122113111231133 221121321132122311211131122211213211321322112312321123113213221123113112221131112311332211211131221131211132221232112111 3122123211231131122113221123113221113122112132113213211121332212311322113212221"."31131122211311123113321112131221123113111231121113311211131221121321131211132221123113112211121312211231131122211211133 112111311222112111312211312111322211213211321322123211211131211121332211231131122211311123113321112132132112211131221131 211132221121321132132212321121113121112133221121321132132211331121321231231121113112221121321133112132112211213322112311 311222113111231133211121312211231131122211322311311222112111312211311123113322112132113212231121113112221121321132122211 322212221121123222112111312211312111322212321121113121112131112132112311321322112111312212321121113122112131112131221121 321132132211231131122211331121321232221121113122113121122132112311321322112111312211312111322211213111213122112132113121 113222112132113213221133112132123222112311311222113111231133211121312211231131122111213122112132113212221132221121321132 23113112221121113122113121113123112112322111213211322211312113211"."13211321322113311213212312311211131122211213211331121321123123211231131122211211131221131112311332211213211321223112111 311222112132113213221123123211231132132211231131122211311123113322112111312211312111322111213122112311311123112112322211 213211321322113311213212312311211131211131221223113112221131112311332211211131221131211132211121312211231131112311211232 221121113122113121113222123211211131211121311121321123113213221121113122123211211131221222112112322211213211321322113311 213212312311211131122211213211321322113221321132132211231131122211331121321232221121113122113121122132112311321322112111 312211312113221133211322112211213322112311311222113111231133211121312211231131112311211133112111312211213211312111322211 231131122111213122112311311222112111331121113112221121113122113121113222112132113213221232112111312111213322112311311222 113111221221113122112132113121113222112311311222113111231133221121113311211131122211211131221131112311332211211131221131 211132221232112111312111213322112132113213221133112132123123112111311222112132113212231121113112221121113122113121132211 3322112111312211322132113213221123113112221131112311311121321122112132231121113122113322113111221131221"."11131221131211132221232112111312111213111213211231132132211211131221232112111312211213111213122112132113213221123113112 221133112132123222112111312211312112213211231132132211211131221131211132221121311121312211213211312111322211213211321322 113311213212322211231131122211311123113223112111311222112132113311213211221121332211211131221131211132221232112111312111 213111213211231131112311311221122132113213221133112132123222112311311222113111231132231121113112221121321133112132112211 213322112311311222113111231133211121312211231131112311211133112111312211213211312111322211231131122111213122112311311221 132211221121332211211131221131211132221232112111312111213111213211231132132211211131221131211132221132211131221131211132 221121321132132212321121113121112133221123113112221131112212211131221121321131211132221123113112221131112211322212312211 322212221121123222112132113213221133112132123123112111311222112132113311213211231232112311311222112111312211311123113322 112132113212231121113112221121321132132211231232112311321322112311311222113111231133221121113122113121113221112131221123 113111231121123222112132113213221133122112231131122211211131221131112311332211213211321322113311213212322211231232112311 321322112311311222113311213212322211231131122211311123113321112131221123113111231121123222112111312211312111322212321121 113121112131112132112311321322112111312211312112213211231132132211231131122211311122113222123222112311311222113221113122 11312111322211213211321322113311213211331121113122122211211132213211231131122212322211331222113112211"."31131122211311123113321112131221123113111231121113311211131221121321131211132221123113112211121312211231131122211211133 112111311222112111312211312111322211213211321322123211211131211121332211231131122211311122122111312211213211312111322211 231131122211311123113322112111331121113112221121113122113111231133221121113122113121113222123211211131211121332211213211 321322113311213211322132112311321322112111312212321121113122122211211232221123113112221131112311332111213122112311311123 112111331121113122112132113311213211321222122111312211312111322212321121113121112133221121321132132211331121321132213211 231132132211211131221232112111312212221121123222112132113213221133112132123123112111311222112132113311213211231232112311 311222112111312211311123113322112132113212231121113112221121321132122211322212221121123222112311311222113111231133211121 312211231131112311211133112111312211213211312111322211231131122211311123113322113223113112221131112311332211211131221131 211132211121312211231131112311211232221121321132132211331221122311311222112111312211311123113322112132113213221133122211 332111213112221133211322112211213322112111312211312111322212321121113121112131112132112311321322112111312212321121113122 112131112131221121321132132211231131122211331121321232221121113122113121122132112311321322112111312211312111322211213111 213122112132113121113222112132113213221133112132123222112311311222113111231132231121113112221121321133112132112211213322 112111312211312111322212311222122132113213221123113112221133112132123222112111312211312111322212321121113121112133221121 311121312211213211312111322211213211321322123211211131211121332211213211321322113311213212312311211131122211213211331121 321122112133221123113112221131112311332111213122112311311123112111331121113122112132113121113222112311311222113111221221 113122112132113121113222112132113213221133122211332111213322112132113213221132231131122211311123113322112111312211312111 322212321121113122123211231131122113221123113221113122112132113213211121332212311322113212221"."13211321322113311213212312311211131122211213211331121321123123211231131122211211131221131112311332211213211321223112111 311222112132113213221123123211231132132211231131122211311123113322112111312211312111322111213122112311311123112112322211 213211321322113312211223113112221121113122113111231133221121321132132211331121321232221123123211231132132211231131122211 331121321232221123113112221131112311332111213122112311311123112112322211211131221131211132221232112111312211322111312211 213211312111322211231131122111213122112311311221132211221121332211213211321322113311213212312311211131122211213211331121 321123123211231131122211211131221232112111312211312113211223113112221131112311332111213122112311311123112112322211211131 221131211132221232112111312211322111312211213211312111322211231131122111213122112311311221132211221121332211211131221131 211132221232112111312111213111213211231132132211211131221232112111312211213111213122112132113213221123113112221133112132 123222112111312211312112213211231132132211211131221131211322113321132211221121332211213211321322113311213212312311211131 122211213211331121321123123211231131122211211131221131112311332211213211321322113311213212322211322132113213221133112132 123222112311311222113111231132231121113112221121321133112132112211213322112111312211312111322212311222122132113213221123 113112221133112132123222112111312211312111322212311322123123112111321322123122113222122211211232221123113112221131112311 332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131 221131211132221121321132132212321121113121112133221123113112221131112212211131221121321131211132221123113112221131112311 332211211133112111311222112111312211311123113322112111312211312111322212321121113121112133221121321132132211331121321132 213211231132132211211131221232112111312212221121123222112311311222113111231133211121321321122111312211312111322211213211 321322123211211131211121332211231131122211311123113321112131221123113111231121123222112111331121113112221121113122113111 231133221121113122113121113221112131221123113111231121123222112111312211312111322212321121113121112131112132112311321322 112111312212321121113122122211211232221121321132132211331121321231231121113112221121321133112132112312321123113112221121 113122113111231133221121321132132211331221122311311222112111312211311123113322112111312211312111322212311322123123112112 322211211131221131211132221132213211321322113311213212322211231131122211311123113321112131221123113112211121312211213211 321222113222112132113223113112221121113122113121113123112112322111213211322211312113211"."11131221131211132221232112111312111213111213211231132132211211131221232112111312211213111213122112132113213221123113112 221133112132123222112111312211312112213211231132132211211131221131211132221121311121312211213211312111322211213211321322 113311213212322211231131122211311123113223112111311222112132113311213211221121332211211131221131211132221231122212213211 321322112311311222113311213212322211211131221131211132221232112111312111213322112131112131221121321131211132221121321132 132212321121113121112133221121321132132211331121321231231121113112221121321133112132112211213322112311311222113111231133 211121312211231131122211322311311222112111312211311123113322112132113212231121113112221121321132122211322212221121123222 112111312211312111322212321121113121112131112132112311321322112111312212321121113122112131112131221121321132132211231131 122111213122112311311222113111221131221221321132132211331121321231231121113112221121321133112132112211213322112311311222 113111231133211121312211231131122211322311311222112111312211311123113322112132113212231121113112221121321132122211322212 221121123222112311311222113111231133211121312211231131112311211133112111312211213211312111322211231131122111213122112311 311222112111331121113112221121113122113121113222112132113213221232112111312111213322112311311222113111221221113122112132 113121113222112311311222113111221132221231221132221222112112322211211131221131211132221232112111312111213111213211231132 132211211131221232112111312211213111213122112132113213221123113112221133112132123222112111312211312111322212321121113121 112133221132211131221131211132221232112111312111213322112132113213221133112132113221321123113213221121113122123211211131 221222112112322211231131122211311123113321112132132112211131221131211132221121321132132212321121113121112133221123113112 221131112311332111213211322111213111213211231131211132211121311222113321132211221121332211213211321322113311213212312311 211131122211213211331121321123123211231131122211211131221131112311332211213211321223112111311222112132113213221123123211 231132132211231131122211311123113322112111312211312111322111213122112311311123112112322211213211321322113312211223113112 221121113122113111231133221121321132132211331121321232221123123211231132132211231131122211331121321232221123113112221131 112311332111213122112311311123112112322211211131221131211132221232112111312211322111312211213211312111322211231131122111 213122112311311221132211221121332211213211321322113311213212312311211131211131221223113112221131112311332211211131221131 211132211121312211231131112311211232221121321132132211331121321231231121113112221121321133112132112211213322112312321123 113213221123113112221133112132123222112311311222113111231132231121113112221121321133112132112211213322112311311222113111 231133211121312211231131112311211133112111312211213211312111322211231131122111213122112311311221132211221121332211211131 221131211132221232112111312111213111213211231132132211211131221232112111312211213111213122112132113213221123113112221133 112132123222112111312211312111322212311222122132113213221123113112221133112132123222112311311222113111231133211121321132 211121311121321122112133221123113112221131112311332211322111312211312111322212321121113121112133221121321132132211331121 321231231121113112221121321132122311211131122211211131221131211322113322112111312211322132113213221123113112221131112311 311121321122112132231121113122113322113111221131221"."31131122211311123113321112131221123113111231121113311211131221121321131211132221123113112211121312211231131122211211133 112111311222112111312211312111322211213211321322123211211131211121332211231131122211311122122111312211213211312111322211 231131122211311123113322112111331121113112221121113122113111231133221121113122113121113222123211211131211121332211213211 321322113311213211322132112311321322112111312212321121113122122211211232221123113112221131112311332111213213211221113122 113121113222112132113213221232112111312111213322112311311222113111231133211121312211231131112311211232221121113311211131 122211211131221131112311332211211131221131211132211121312211231131112311211232221121113122113121113222123211211131211121 311121321123113213221121113122123211211131221222112112322211213211321322113311213212312311211131122211213211321322113221 321132132211231131122211331121321232221121113122113121122132112311321322112111312211312113221133211322112211213322112311 311222113111231133211121312211231131112311211133112111312211213211312111322211231131122111213122112311311222112111331121 113112221121113122113121113222112132113212231121113112221121321132132211331222113112211221113122113121113222123211211131 211121311121321123113213221121113122123211211131221222112112322211213211321322113311213212312311211131122211213211321322 113221321132132211231131122211331121321232221121113122113121122132112311321322112111312211312113221133211322112211213322 112132113213221133112132123123112111311222112132113311213211231232112311311222112111312211311123113322112132113212231121 113112221121321132132211231232112311321322112311311222113111231133221121113122113121113221112131221123113111231121123222 112132113213221133122112231131122211211131221131112311332211213211321322113312221133211121311222113321132211221121332211 231131122211311123113321112131221123113111231121113311211131221121321131211132221123113112211121312211231131122211211133 112111311222112111312211312111322211213211321322123211211131211121332211231131122211311123113321112131221123113111231121 123222113223113112221131112311332111213122112311311123112112322211211131221131211132221232112111312211322111312211213211 312111322211231131122111213122112311311221132211221121332211213211321322113311213212312311211131211131221223113112221131 112311332211211131221131211132211121312211231131112311211232221121321132132211331121321231231121113122113223112111331121 113122112132113111231132231121113213221231221132221222112112322211211131221131211132221232112111312111213111213211231132 132211211131221232112111312211213111213122112132113213221123113112221133112132123222112111312211312112213211231132132211 211131221131211132221121311121312211213211312111322211213211321322113311213212322211231131122211311123113223112111311222 112132113311213211221121332211211131221131211132221231122212213211321322112311311222113311213212322211211131221131211132 221232112111312111213322112131112131221121321131211132221121321132132212321121113121112133221121321132132211331121321231 231121113112221121321133112132112211213322112311311222113111231133211121312211231131122211322311311222112111312211311123 113322112132113212231121113112221121321132122211322212221121123222112111312211312111322212321121113121112131112132112311 311123113112211221321132132211331121321232221123113112221131112311322311211131122211213211331121321122112133221121113122 113121113222123211211131211121311121321123113213221121113122123211211131221222112112322211213111213122112132113121113222 112132113213221232112111312111213322112132113213221133112132113221321123113213221121113122123211211131221222112112322211 213211321322113311213212312311211131122211213211331121321123123211231131122211211131221131112311332211213211321223112111 311222112132113212221132221222112112322211231131122211311123113321112131221123113111231121113311211131221121321131211132 221123113112211121312211231131122211211133112111311222112111312211312111322211213211321322123211211131211121332211231131 122211311123113321112132132112211131221131211132221121321132132212321121113121112133221121321132132211331121321231231121 113122113223112111331121113122122211211232221121321132132211331121321232221132231131122211311123113321112131221123113111 231121123222112111312211312111322212321121113121112131112132112311321322112111312211312112213211231132132211231131122211 311122113222123222112311311222113221113122113121113222112132113213221133112132113311211131221222112111322132112311311222 12322211331222113112211"
        };
        returnarr[n]; }}Copy the code
  • Time complexity O(1)
  • Space complexity O(1)

Idea 2: Recursion

  • This is definitely not the point that we’re looking at but it’s just a trick
  • Find the new state based on the previous state
  • It’s easy to think of a recursive solution
  • We’re just going to recursively go through the previous state
public String countAndSay(int n) {
    StringBuilder res = new StringBuilder();
    / / recursion
    if (n == 1) {
        return "1";
    }
    int pre = 0;
    int cur = 1;
    String str = countAndSay(n - 1);
    for (cur = 1; cur < str.length(); cur++) {
        if(str.charAt(pre) ! = str.charAt(cur)) {// Update the result if the current character is not equal to the previous character
            intcount = cur - pre; res.append(count).append(str.charAt(pre)); pre = cur; }}if(pre ! = cur) {int count = cur - pre;
        res.append(count).append(str.charAt(pre));
    }
    return res.toString();
}
Copy the code
  • Time complexity O(n)
  • Space complexity O(n)