Problem
Betrachte jedes zusammenhängende Fenster aus span Ziffern und multipliziere dessen Ziffern. Gib das größte Produkt zurück. Führende Nullen sind gewöhnliche Ziffern; ein Fenster mit einer Null ergibt das Produkt Null. Die Ziffern dürfen weder umgeordnet noch übersprungen werden.
Implementiere largest_adjacent_digit_product(digits, span).
Eingabe
digits: Die Ziffernfolge, einschließlich etwaiger führender Nullen.
span: Die genaue Anzahl benachbarter Ziffern in einem Fenster.
Ausgabe
Gib das größte Produkt aller Fenster dieser Breite zurück.
Einschränkungen
1 ≤ Länge der Ziffernfolge ≤ 100.000. Zeichen sind 0…9. 1 ≤ span ≤ min(18, Länge). Alle Produkte passen in ein vorzeichenbehaftetes 64-Bit-Integer.
Beispiele
Eingabe:
span = 2
digits = "23405"
Erwartete Ausgabe:
expected = 12Eingabe:
long long span = 2;
std::string digits = "23405";
Erwartete Ausgabe:
long long expected = 12;Eingabe:
long span = 2;
string digits = "23405";
Erwartete Ausgabe:
long expected = 12;Erläuterung
Die Fenster 23, 34, 40 und 05 haben die Produkte 6, 12, 0 und 0. Das größte ist 12.
Eingabe:
span = 3
digits = "102"
Erwartete Ausgabe:
expected = 0Eingabe:
long long span = 3;
std::string digits = "102";
Erwartete Ausgabe:
long long expected = 0;Eingabe:
long span = 3;
string digits = "102";
Erwartete Ausgabe:
long expected = 0;Erläuterung
Es gibt nur ein Fenster der Breite drei. Es enthält eine Null, daher 1 × 0 × 2 = 0.
So gehst du vor
Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.
Hinweis 1
Eine Null in einem Fenster macht das Produkt zu null, also können nur zusammenhängende, nicht-nullige Abschnitte zum Maximum beitragen.
Hinweis 2
Nutze ein Sliding Window oder verfolge Produkte über Ziffernblöcke, um nicht jeden Bereich neu zu berechnen.
Hinweis 3
Achte auf die exakte Fensterlänge: führende Nullen zählen als Ziffern, und wenn die Länge einen nicht-nulligen Block überschreitet, ist das Produkt null.
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.