Problème
Le plan des places d'un immense stade est presque vide, donc stocker chaque cellule gaspillerait de la mémoire. Une SparseGrid ne stocke que les cellules qui contiennent une valeur non nulle ; toutes les autres valent 0. La grille commence avec rows lignes, cols colonnes et aucune cellule stockée. Traitez ces opérations dans l'ordre :
set r c v: la cellule (r, c) prend la valeurv. Lui donner la valeur 0 la retire du stockage.get r c: affiche la valeur de la cellule (r, c).count: affiche le nombre de cellules non nulles.row_sum r: affiche la somme des valeurs de la ligner.width: affiche le nombre actuel de colonnes.remove_col c: supprime la colonnec. Ses cellules disparaissent, toutes les cellules situées à sa droite se décalent d'une colonne vers la gauche, et la grille a une colonne de moins.
Les lignes et les colonnes sont numérotées à partir de 0, et chaque indice est dans la grille au moment de l'opération.
Implémentez sparse_grid(rows, cols, operations).
Entrée
rows : le nombre de lignes.
cols : le nombre initial de colonnes.
operations : les opérations, traitées dans l'ordre.
Sortie
Renvoyez les résultats de get, count, row_sum et width dans l'ordre où ils se produisent.
Contraintes
1 ≤ rows ≤ 1 000 000
1 ≤ cols ≤ 1 000 000
0 ≤ nombre d'opérations ≤ 1 000
−1 000 000 ≤ v ≤ 1 000 000
Exemples
Entrée :
rows = 3
cols = 4
operations = ["set 0 1 5", "set 0 3 2", "set 2 2 7", "row_sum 0", "count", "get 1 1"]
Sortie attendue :
expected = [7, 3, 0]
Entrée :
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"};
Sortie attendue :
std::vector<long long> expected = {7, 3, 0};
Entrée :
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"};
Sortie attendue :
long[] expected = new long[] {7, 3, 0};
Explication
La ligne 0 contient 5 et 2, donc sa somme vaut 7 ; trois cellules sont stockées ; (1, 1) n'a jamais été définie, donc elle vaut 0.
Entrée :
rows = 2
cols = 3
operations = ["set 1 0 4", "set 1 2 9", "remove_col 0", "get 1 1", "width", "count"]
Sortie attendue :
expected = [9, 2, 1]
Entrée :
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"};
Sortie attendue :
std::vector<long long> expected = {9, 2, 1};
Entrée :
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"};
Sortie attendue :
long[] expected = new long[] {9, 2, 1};
Explication
Supprimer la colonne 0 efface le 4 et fait glisser le 9 de la colonne 2 vers la colonne 1, donc get 1 1 donne 9, la largeur est 2 et il reste une cellule.
Comment l'aborder
Essayez d'abord seul, puis ouvrez les indices un par un.
Indice 1
Un dictionnaire de (ligne, colonne) vers la valeur convient bien ; une clé absente signifie 0.
Indice 2
Mettre une cellule à 0 doit la supprimer, pour que `count` reste juste.
Indice 3
Quand une colonne est supprimée, reconstruisez le dictionnaire : retirez cette colonne et diminuez de un les numéros de colonne plus grands.
Complexité attendue
temps O(q × s), espace supplémentaire O(s), s = cellules stockées
Références
Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.