Tutte le sfide
Media 0 risolte 0% di accettazione

Griglia sparsa

Rappresenta una griglia quasi vuota come elenco delle sue celle diverse da zero e gestisci le operazioni di lettura, conteggio, somma di riga e rimozione di colonna.

Cosa imparerai

  • Memorizzare solo le celle diverse da zero
  • Aggiornare le chiavi memorizzate quando le colonne si spostano
  • Rispondere alle richieste senza costruire la griglia completa

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) diventa v. 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 riga r.
  • width: restituisce il numero attuale di colonne.
  • remove_col c: elimina la colonna c. 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

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

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

La migliore soluzione superata di ogni programmatore. Le più veloci, leggere e meglio valutate stanno in alto.

Ancora nessuna soluzione superata. Risolvila e prendi il primo posto.

Impara dagli altri

Soluzioni della community

Nessuna soluzione pubblicata. Risolvi questa sfida per condividere la prima.