Problema
La mappa dei posti di uno stadio enorme è quasi tutta vuota, quindi memorizzare ogni cella spreca memoria. Una SparseGrid memorizza solo le celle che contengono un valore diverso da zero; tutte le altre valgono 0. La griglia parte con rows righe, cols colonne e nessuna cella memorizzata. Elabora queste operazioni in ordine:
set r c v: la cella (r, c) diventav. Assegnare 0 rimuove la cella dalla memoria.get r c: restituisce il valore della cella (r, c).count: restituisce quante celle sono diverse da zero.row_sum r: restituisce la somma dei valori della rigar.width: restituisce il numero attuale di colonne.remove_col c: elimina la colonnac. Le sue celle spariscono, ogni cella alla sua destra si sposta di una colonna a sinistra e la griglia ha una colonna in meno.
Righe e colonne sono numerate da 0, e ogni indice è dentro la griglia al momento dell'operazione.
Implementa sparse_grid(rows, cols, operations).
Input
rows: il numero di righe.
cols: il numero iniziale di colonne.
operations: le operazioni, da elaborare in ordine.
Output
Restituisci i risultati di get, count, row_sum e width nell'ordine in cui avvengono.
Vincoli
1 ≤ rows ≤ 1 000 000
1 ≤ cols ≤ 1 000 000
0 ≤ numero di operazioni ≤ 1 000
−1 000 000 ≤ v ≤ 1 000 000
Esempi
Input:
rows = 3
cols = 4
operations = ["set 0 1 5", "set 0 3 2", "set 2 2 7", "row_sum 0", "count", "get 1 1"]
Output atteso:
expected = [7, 3, 0]
Input:
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"};
Output atteso:
std::vector<long long> expected = {7, 3, 0};
Input:
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"};
Output atteso:
long[] expected = new long[] {7, 3, 0};
Spiegazione
La riga 0 contiene 5 e 2, quindi la sua somma è 7; le celle memorizzate sono tre; la (1, 1) non è mai stata impostata, quindi vale 0.
Input:
rows = 2
cols = 3
operations = ["set 1 0 4", "set 1 2 9", "remove_col 0", "get 1 1", "width", "count"]
Output atteso:
expected = [9, 2, 1]
Input:
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"};
Output atteso:
std::vector<long long> expected = {9, 2, 1};
Input:
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"};
Output atteso:
long[] expected = new long[] {9, 2, 1};
Spiegazione
Rimuovere la colonna 0 elimina il 4 e sposta il 9 dalla colonna 2 alla colonna 1, quindi get 1 1 vale 9, la larghezza è 2 e resta una sola cella.
Come affrontarlo
Prova prima da solo, poi apri un suggerimento alla volta.
Suggerimento 1
Una mappa da (riga, colonna) a valore funziona bene; una chiave assente significa 0.
Suggerimento 2
Impostare una cella a 0 deve eliminarla, così `count` resta corretto.
Suggerimento 3
Quando si rimuove una colonna, ricostruisci la mappa: elimina quella colonna e diminuisci di uno i numeri di colonna più grandi.
Complessità attesa
tempo O(q × s), spazio aggiuntivo O(s), s = celle memorizzate
Riferimenti
Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.