Problem
Ein Stochastik-Labor wirft eine Münze sehr oft und notiert die Ergebnisse als String aus H (heads, Kopf) und T (tails, Zahl). Eine Serie ist eine möglichst lange Gruppe aufeinanderfolgender gleicher Ergebnisse; HHTHHH besteht aus den Serien HH, T und HHH. Schüler sind oft überrascht, wie lang die längste Serie in einer zufälligen Folge ist, deshalb misst das Labor sie.
Implementiere coin_toss_streaks(tosses).
Eingabe
tosses: Die Ergebnisse der Reihe nach, nur aus H und T.
Ausgabe
Gib [longest_heads, longest_tails, streaks] zurück: die Länge der längsten Kopf-Serie, die Länge der längsten Zahl-Serie (0, wenn diese Seite nie fällt) und die Gesamtzahl der Serien.
Einschränkungen
0 ≤ Länge von tosses ≤ 100 000
Beispiele
Eingabe:
tosses = "HHTHHH"
Erwartete Ausgabe:
expected = [3, 1, 3]
Eingabe:
std::string tosses = "HHTHHH";
Erwartete Ausgabe:
std::vector<long long> expected = {3, 1, 3};
Eingabe:
string tosses = "HHTHHH";
Erwartete Ausgabe:
long[] expected = new long[] {3, 1, 3};
Erläuterung
Die Serien sind HH, T und HHH, also ist die längste Kopf-Serie 3, die längste Zahl-Serie 1, und es gibt 3 Serien.
Eingabe:
tosses = "TTTT"
Erwartete Ausgabe:
expected = [0, 4, 1]
Eingabe:
std::string tosses = "TTTT";
Erwartete Ausgabe:
std::vector<long long> expected = {0, 4, 1};
Eingabe:
string tosses = "TTTT";
Erwartete Ausgabe:
long[] expected = new long[] {0, 4, 1};
Erläuterung
Kopf fällt nie, also ist die längste Kopf-Serie 0; es gibt eine Zahl-Serie der Länge 4: [0, 4, 1].
So gehst du vor
Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.
Hinweis 1
Eine neue Serie beginnt bei Index 0 und überall dort, wo ein Wurf sich vom vorherigen unterscheidet.
Hinweis 2
Führe eine beste Länge für Kopf und eine für Zahl.
Hinweis 3
Ein leerer String hat überhaupt keine Serien.
Erwartete Komplexität
Zeit O(n), zusätzlicher Speicher O(1)
Referenzen
Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.