Go Analyse de code d'exemple de méthode de décodage d'algorithme Java

Méthode de décodage

Un message contenant les lettres A-Z est codé avec le mappage suivant :

• 'A' -> "1"

• 'B' -> .

• 'Z' -> "26"

• Pour décoder le message codé, tous les chiffres doivent être mappés sur des lettres en fonction de la méthode mappée ci-dessus (il peut y avoir plusieurs méthodes). Par exemple, "11106" peut être mappé sur :

"AAJF" , regroupez le message comme (1 1 10 6)

"KJF" , regroupez le message comme (11 10 6)

Notez que le message ne peut pas être regroupés comme (1 11 06) car "06" ne peut pas être mappé sur "F" car "6" et "06" ne sont pas équivalents dans le mappage.

Étant donné une chaîne non vide s contenant uniquement des nombres, veuillez calculer et renvoyer le nombre total de méthodes de décodage.

Les données de la question garantissent que la réponse doit être un entier de 32 bits.

Exemple 1 :

• Entrée : s = "12"

Sortie : 2

Explication : Il peut être décodé comme "AB" (1 2) ou "L" (12).

Exemple 2 :

• Entrée : s = "226"

Sortie : 3

Explication : Il peut être décodé comme "BZ" (2 26), "VF" (22 6), ou "BBF" (2 2 6).

Exemple 3 :

• Entrée : s = "0"

Sortie : 0

Explication : Aucun caractère ne correspond aux nombres commençant par 0.

Les mappages valides contenant 0 sont 'J' -> "10" et 'T'->

Comme il n'y a pas de caractères, il n'existe aucun moyen efficace de décoder cela car tous les nombres doivent être mappés.

Conseil :

1 <= s.length <= 100

s ne contiennent que des chiffres et peuvent contenir des zéros non significatifs.

Méthode 1 : Programmation dynamique (Java)

Pour une chaîne donnée s, laissez sa longueur être n et les caractères qu'elle contient de gauche à droite sont s[1], s[2],..., s[ n]. Nous pouvons utiliser la programmation dynamique pour calculer le nombre de méthodes de décodage d'une chaîne.

Plus précisément, soit fi représente le nombre de méthodes de décodage pour les i premiers caractères s[1..i] de la chaîne s. Lors du transfert d'état, nous pouvons considérer quels caractères dans s ont été utilisés pour le dernier décodage

class Solution {
    public int numDecodings(String s) {
        int n = s.length();
        int[] f = new int[n + 1];
        f[0] = 1;
        for (int i = 1; i <= n; ++i) {
            if (s.charAt(i - 1) != &#39;0&#39;) {
                f[i] += f[i - 1];
            }
            if (i > 1 && s.charAt(i - 2) != &#39;0&#39; && ((s.charAt(i - 2) - &#39;0&#39;) * 10 + (s.charAt(i - 1) - &#39;0&#39;) <= 26)) {
                f[i] += f[i - 2];
            }
        }
        return f[n];
    }
}

Complexité temporelle : o(n)

Complexité spatiale : o(n)

Méthode 2 : Programmation dynamique—&mdash ;Optimisation (aller )

Veuillez consulter la description ci-dessus pour des idées de méthodes spécifiques. Cette méthode optimise la complexité de l'espace. En utilisant des variables temporaires, la complexité de l'espace est réduite de o(n) à o(1)

func numDecodings(s string) int {
    n := len(s)
    // a = f[i-2], b = f[i-1], c = f[i]
    a, b, c := 0, 1, 0
    for i := 1; i <= n; i++ {
        c = 0
        if s[i-1] != &#39;0&#39; {
            c += b
        }
        if i > 1 && s[i-2] != &#39;0&#39; && ((s[i-2]-&#39;0&#39;)*10+(s[i-1]-&#39;0&#39;) <= 26) {
            c += a
        }
        a, b = b, c
    }
    return c
}

Complexité temporelle : o(n)

Complexité spatiale : o(1)

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!