Problem
Der Sitzplan eines riesigen Stadions ist größtenteils leer, daher wäre es Speicherverschwendung, jede Zelle abzulegen. Ein SparseGrid speichert nur die Zellen mit einem Wert ungleich null; jede andere Zelle ist 0. Das Gitter beginnt mit rows Zeilen, cols Spalten und ohne gespeicherte Zellen. Verarbeite diese Operationen der Reihe nach:
set r c v: Zelle (r, c) bekommt den Wertv. Wird 0 gesetzt, wird die Zelle aus dem Speicher entfernt.get r c: den Wert der Zelle (r, c) ausgeben.count: ausgeben, wie viele Zellen ungleich null sind.row_sum r: die Summe der Werte in Zeilerausgeben.width: die aktuelle Anzahl der Spalten ausgeben.remove_col c: Spalteclöschen. Ihre Zellen verschwinden, jede Zelle rechts davon rückt eine Spalte nach links, und das Gitter hat eine Spalte weniger.
Zeilen und Spalten werden ab 0 nummeriert, und jeder Index liegt zum Zeitpunkt der Operation innerhalb des Gitters.
Implementiere sparse_grid(rows, cols, operations).
Eingabe
rows: Die Anzahl der Zeilen.
cols: Die anfängliche Anzahl der Spalten.
operations: Die Operationen, die der Reihe nach verarbeitet werden.
Ausgabe
Gib die Ausgaben von get, count, row_sum und width in der Reihenfolge zurück, in der sie anfallen.
Einschränkungen
1 ≤ rows ≤ 1 000 000
1 ≤ cols ≤ 1 000 000
0 ≤ Anzahl der Operationen ≤ 1000
−1 000 000 ≤ v ≤ 1 000 000
Beispiele
Eingabe:
rows = 3
cols = 4
operations = ["set 0 1 5", "set 0 3 2", "set 2 2 7", "row_sum 0", "count", "get 1 1"]
Erwartete Ausgabe:
expected = [7, 3, 0]
Eingabe:
long long rows = 3;
long long cols = 4;
std::vector<std::string> operations = {"set 0 1 5", "set 0 3 2", "set 2 2 7", "row_sum 0", "count", "get 1 1"};
Erwartete Ausgabe:
std::vector<long long> expected = {7, 3, 0};
Eingabe:
long rows = 3;
long cols = 4;
string[] operations = new string[] {"set 0 1 5", "set 0 3 2", "set 2 2 7", "row_sum 0", "count", "get 1 1"};
Erwartete Ausgabe:
long[] expected = new long[] {7, 3, 0};
Erläuterung
Zeile 0 enthält 5 und 2, ihre Summe ist also 7; gespeichert sind drei Zellen; (1, 1) wurde nie gesetzt und ist daher 0.
Eingabe:
rows = 2
cols = 3
operations = ["set 1 0 4", "set 1 2 9", "remove_col 0", "get 1 1", "width", "count"]
Erwartete Ausgabe:
expected = [9, 2, 1]
Eingabe:
long long rows = 2;
long long cols = 3;
std::vector<std::string> operations = {"set 1 0 4", "set 1 2 9", "remove_col 0", "get 1 1", "width", "count"};
Erwartete Ausgabe:
std::vector<long long> expected = {9, 2, 1};
Eingabe:
long rows = 2;
long cols = 3;
string[] operations = new string[] {"set 1 0 4", "set 1 2 9", "remove_col 0", "get 1 1", "width", "count"};
Erwartete Ausgabe:
long[] expected = new long[] {9, 2, 1};
Erläuterung
Das Entfernen von Spalte 0 löscht die 4 und schiebt die 9 von Spalte 2 in Spalte 1, also liefert get 1 1 den Wert 9, die Breite ist 2 und es bleibt eine Zelle übrig.
So gehst du vor
Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.
Hinweis 1
Eine Map von (Zeile, Spalte) auf den Wert eignet sich gut; ein fehlender Schlüssel bedeutet 0.
Hinweis 2
Wird eine Zelle auf 0 gesetzt, sollte sie gelöscht werden, damit `count` stimmt.
Hinweis 3
Wird eine Spalte entfernt, bau die Map neu auf: Wirf diese Spalte heraus und verringere größere Spaltennummern um eins.
Erwartete Komplexität
Zeit O(q × s), zusätzlicher Speicher O(s), s = gespeicherte Zellen
Referenzen
Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.