Alle Herausforderungen
Einfach 0 gelöst 0% Erfolgsquote

Serien beim Münzwurf

Finde die längste Kopf-Serie, die längste Zahl-Serie und die Anzahl der Serien in einer Folge von Münzwürfen.

Das lernst du

  • Eine Folge in möglichst lange Serien zerlegen
  • Für jeden Wert die längste Serie mitführen
  • Serien zählen

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

Beispiel 1
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.

Beispiel 2
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.

Die beste bestandene Lösung jedes Coders. Schnellere, sparsamere und besser bewertete Lösungen stehen weiter oben.

Noch keine bestandene Lösung. Löse sie und hol dir Platz eins.

Von anderen lernen

Community-Lösungen

Noch keine veröffentlichten Lösungen. Löse die Aufgabe und teile als Erster eine Lösung.