Alle Herausforderungen
Mittel 0 gelöst 0% Erfolgsquote

Dünnbesetztes Gitter

Speichere ein größtenteils leeres Gitter als Liste seiner Zellen ungleich null und beantworte Operationen zum Lesen, Zählen, zu Zeilensummen und zum Entfernen von Spalten.

Das lernst du

  • Nur Zellen ungleich null speichern
  • Gespeicherte Schlüssel anpassen, wenn sich Spalten verschieben
  • Abfragen beantworten, ohne das vollständige Gitter aufzubauen

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 Wert v. 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 Zeile r ausgeben.
  • width: die aktuelle Anzahl der Spalten ausgeben.
  • remove_col c: Spalte c lö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

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

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

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.