Problem
Ein Würfelsimulator speichert jeden Wurf eines sechsseitigen Würfels in einer Liste. Eine Serie ist eine Gruppe aufeinanderfolgender Würfe mit demselben Wert; ein einzelner Wurf ist eine Serie der Länge 1. Finde die längste Serie. Haben mehrere Serien dieselbe größte Länge, nimm die, die zuerst beginnt.
Implementiere longest_run_of_rolls(rolls).
Eingabe
rolls: Die Würfe in der Reihenfolge, in der sie gefallen sind, jeweils von 1 bis 6.
Ausgabe
Gib [start, length] zurück: den Index (ab 0 gezählt), an dem die längste Serie beginnt, und ihre Länge. Für eine leere Liste gib [-1, 0] zurück.
Einschränkungen
0 ≤ Anzahl der Würfe ≤ 10 000
1 ≤ Wurf ≤ 6
Beispiele
Eingabe:
rolls = [1, 4, 4, 2, 6, 6, 6, 3]
Erwartete Ausgabe:
expected = [4, 3]
Eingabe:
std::vector<long long> rolls = {1, 4, 4, 2, 6, 6, 6, 3};
Erwartete Ausgabe:
std::vector<long long> expected = {4, 3};
Eingabe:
long[] rolls = new long[] {1, 4, 4, 2, 6, 6, 6, 3};
Erwartete Ausgabe:
long[] expected = new long[] {4, 3};
Erläuterung
Die drei Sechsen ab Index 4 schlagen die zwei Vieren: [4, 3].
Eingabe:
rolls = [5, 5, 2, 2, 3]
Erwartete Ausgabe:
expected = [0, 2]
Eingabe:
std::vector<long long> rolls = {5, 5, 2, 2, 3};
Erwartete Ausgabe:
std::vector<long long> expected = {0, 2};
Eingabe:
long[] rolls = new long[] {5, 5, 2, 2, 3};
Erwartete Ausgabe:
long[] expected = new long[] {0, 2};
Erläuterung
Beide Paare haben die Länge 2; die Fünfen beginnen zuerst, bei Index 0: [0, 2].
So gehst du vor
Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.
Hinweis 1
Merk dir, wo die aktuelle Serie begonnen hat.
Hinweis 2
Wenn sich der Wert ändert (oder die Liste endet), vergleiche die abgeschlossene Serie mit der bisher besten.
Hinweis 3
Ersetze die beste nur, wenn die neue Serie echt länger ist.
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.