So implementieren Sie die Erscheinungssequenz des Go Java-Algorithmus

Erscheinungssequenz

Geben Sie bei einer positiven Ganzzahl n das n-te Element der Erscheinungssequenz aus.

„Erscheinungssequenz“ ist eine Folge von ganzen Zahlen, beginnend mit der Nummer 1, und jedes Element in der Sequenz ist eine Beschreibung des vorherigen Elements.

Sie können es sich als eine Folge numerischer Zeichenfolgen vorstellen, die durch eine rekursive Formel definiert sind:

countAndSay(1) = „1“

countAndSay(n) ist eine Beschreibung von countAndSay(n-1), was dann ist in eine andere numerische Zeichenfolge konvertiert.

Die ersten fünf Elemente sind wie folgt:

• 1, 1 –— Das erste Element ist die Nummer 1

• 2, 11 –– das ist „a 1“, aufgezeichnet als „11“

• 3, 21 – Beschreiben Sie den vorherigen Artikel, diese Zahl ist 11, das ist „zwei 1“, aufgezeichnet als „21“

• 4, 1211 – beschrieben Das vorherige Element, die Nummer ist 21, was „a 2 + a 1“ ist, aufgezeichnet als „1211“

• 5, 111221 – Beschreiben Sie das vorherige Element, die Nummer ist 1211, was „a 1 + a“ ist 2 + Zwei 1“, aufgezeichnet als „111221“

Methode 1: Traversal-Generierung (Java)

Die sogenannte „Erscheinungssequenz“ zählt eigentlich nur die Anzahl aufeinanderfolgender identischer Zeichen in einer Zeichenfolge.

Die durch die in der Frage angegebene rekursive Formel definierte numerische Zeichenfolgenfolge lautet wie folgt:

countAndSay(1) = „1“;

countAndSay(n) ist eine Beschreibung von countAndSay(n-1) und dann in eine andere numerische Zeichenfolge umgewandelt.

Wir definieren die Zeichenfolge S_{i} zur Darstellung von countAndSay(i). Wenn wir S_{n} benötigen, müssen wir zuerst S_{n-1} finden und es dann gemäß der oben beschriebenen Methode generieren ist, von links nach rechts die maximale Anzahl aufeinanderfolgender identischer Zeichen in der Zeichenfolge S_{n-1} zu scannen, dann die statistische Anzahl von Zeichen in eine numerische Zeichenfolge umzuwandeln und die entsprechenden Zeichen zu verbinden.

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 ist eine gegebene positive ganze Zahl, M ist die maximale Länge in der generierten Zeichenfolge

Zeitkomplexität: O(N * M)

Raumkomplexität: O(M)

Methode 2: Rekursion (Go)

Die spezifische Methodenanalyse wurde oben beschrieben

Da die jedes Mal erhaltenen Daten aus dem vorherigen Ergebnis abgeleitet werden, können wir davon ausgehen, dass wir das letzte Ergebnis erhalten haben, und dann mit der Berechnung fortfahren. Dies verwendet Rekursion.

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 ist eine gegebene positive ganze Zahl, M ist die maximale Länge in der generierten Zeichenfolge

Zeitkomplexität: O(N*M)

Raumkomplexität: O(M)

Das obige ist der detaillierte Inhalt vonSo implementieren Sie die Erscheinungssequenz des Go Java-Algorithmus. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!