Moyen 0 résolus 0 % de réussite

Grille creuse

Représentez une grille presque vide par la liste de ses cellules non nulles et répondez aux opérations de lecture, de comptage, de somme de ligne et de suppression de colonne.

Ce que vous allez apprendre

  • Ne stocker que les cellules non nulles
  • Mettre à jour les clés stockées quand les colonnes se décalent
  • Répondre aux requêtes sans construire la grille complète

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 valeur v. 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 ligne r.
  • width : affiche le nombre actuel de colonnes.
  • remove_col c : supprime la colonne c. 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

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

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

La meilleure solution validée de chaque codeur. Les plus rapides, les plus légères et les mieux notées passent devant.

Aucune solution validée pour l'instant. Résolvez-le et prenez la première place.

Apprenez des autres

Solutions de la communauté

Aucune solution publiée pour l'instant. Résolvez ce défi pour partager la première.