Comment implémenter la séquence d'apparition de l'algorithme Go Java

Séquence d'apparition

Étant donné un entier positif n, affichez le nième élément de la séquence d'apparition.

« Séquence d'apparence » est une séquence d'entiers, commençant par le chiffre 1, et chaque élément de la séquence est une description de l'élément précédent.

Vous pouvez le considérer comme une séquence de chaînes numériques définies par une formule récursive :

countAndSay(1) = "1"

countAndSay(n) est une description de countAndSay(n-1), qui est alors converti en une autre chaîne numérique.

Les cinq premiers éléments sont les suivants :

• 1, 1 —— Le premier élément est le numéro 1

• 2, 11 —— qui est "un 1", enregistré comme "11"

• 3, 21 - décrivez l'élément précédent, ce nombre est 11, qui est "deux 1", enregistré comme "21"

• 4, 1211 - décrit L'élément précédent, le nombre est 21, qui est "a 2 + a 1", enregistré comme "1211"

• 5, 111221 - Décrivez l'élément précédent, le nombre est 1211, qui est "a 1 + a 2 + Deux 1", enregistré comme "111221"

Méthode 1 : Génération traversante (Java)

La soi-disant "séquence d'apparition" consiste en fait à compter simplement le nombre de caractères identiques consécutifs dans une chaîne.

La séquence de chaînes numériques définie par la formule récursive donnée dans la question est la suivante :

countAndSay(1) = "1" ;

countAndSay(n) est une description de countAndSay(n-1), puis converti en une autre chaîne numérique A.

Nous définissons la chaîne S_{i} pour représenter countAndSay(i). Si nous avons besoin de S_{n}, nous devons d'abord trouver S_{n-1}, puis le générer selon la méthode décrite ci-dessus, c'est-à-dire est, de la gauche Scannez le nombre maximum de caractères identiques consécutifs dans la chaîne S_{n-1} vers la droite, puis convertissez le nombre statistique de caractères en une chaîne numérique et connectez les caractères correspondants.

class Solution {
    public String countAndSay(int n) {
        String str = "1";
        for (int i = 2; i <= n; ++i) {
            StringBuilder sb = new StringBuilder();
            int start = 0;
            int pos = 0;
            while (pos < str.length()) {
                while (pos < str.length() && str.charAt(pos) == str.charAt(start)) {
                    pos++;
                }
                sb.append(Integer.toString(pos - start)).append(str.charAt(start));
                start = pos;
            }
            str = sb.toString();
        }
        return str;
    }
}

N est un entier positif donné, M est la longueur maximale de la chaîne générée

Complexité temporelle : O(N * M)

Complexité spatiale : O(M)

Méthode 2 : Récursion (Go)

La méthode d'analyse spécifique a été décrite ci-dessus

Étant donné que les données obtenues à chaque fois proviennent du résultat précédent, nous pouvons supposer que nous avons obtenu le dernier résultat et ensuite procéder au calcul. Cela utilise la récursivité.

func countAndSay(n int) string {
    if n == 1 {
        return "1"
    }
    s := countAndSay(n - 1)
    i, res := 0, ""
    length := len(s)
    for j := 0; j < length; j++ {
        if s[j] != s[i] {
            res += strconv.Itoa(j-i) + string(s[i])
            i = j
        }
    }
    res += strconv.Itoa(length-i) + string(s[i])
    return res
}

N est un entier positif donné, M est la longueur maximale de la chaîne générée

Complexité temporelle : O(N*M)

Complexité spatiale : O(M)

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!