Médio 0 resolvidos 0% de aceitação

Grade esparsa

Guarde uma grade quase vazia como uma lista das suas células não nulas e responda operações de consulta, contagem, soma de linha e remoção de coluna.

O que você vai aprender

  • Guardar apenas as células não nulas
  • Atualizar as chaves guardadas quando as colunas se deslocam
  • Responder consultas sem montar a grade completa

Problema

Ver original (inglês)

O mapa de assentos de um estádio enorme fica quase todo vazio, então guardar cada célula desperdiça memória. Uma SparseGrid guarda apenas as células com valor diferente de zero; todas as outras valem 0. A grade começa com rows linhas, cols colunas e nenhuma célula guardada. Processe estas operações em ordem:

  • set r c v: a célula (r, c) passa a valer v. Atribuir 0 remove a célula do armazenamento.
  • get r c: informa o valor da célula (r, c).
  • count: informa quantas células são diferentes de zero.
  • row_sum r: informa a soma dos valores da linha r.
  • width: informa o número atual de colunas.
  • remove_col c: apaga a coluna c. As células dela desaparecem, todas as células à direita dela andam uma coluna para a esquerda, e a grade fica com uma coluna a menos.

Linhas e colunas são numeradas a partir de 0, e todo índice está dentro da grade no momento da operação.

Implemente sparse_grid(rows, cols, operations).

Entrada

rows: o número de linhas.

cols: o número inicial de colunas.

operations: as operações, processadas em ordem.

Saída

Retorne as respostas de get, count, row_sum e width na ordem em que acontecem.

Restrições

1 ≤ rows ≤ 1 000 000

1 ≤ cols ≤ 1 000 000

0 ≤ número de operações ≤ 1000

−1 000 000 ≤ v ≤ 1 000 000

Exemplos

Exemplo 1
Entrada:
rows = 3
cols = 4
operations = ["set 0 1 5", "set 0 3 2", "set 2 2 7", "row_sum 0", "count", "get 1 1"]

Saída esperada:
expected = [7, 3, 0]
Entrada:
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"};

Saída esperada:
std::vector<long long> expected = {7, 3, 0};
Entrada:
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"};

Saída esperada:
long[] expected = new long[] {7, 3, 0};

Explicação

A linha 0 tem 5 e 2, então a soma é 7; há três células guardadas; (1, 1) nunca recebeu valor, então vale 0.

Exemplo 2
Entrada:
rows = 2
cols = 3
operations = ["set 1 0 4", "set 1 2 9", "remove_col 0", "get 1 1", "width", "count"]

Saída esperada:
expected = [9, 2, 1]
Entrada:
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"};

Saída esperada:
std::vector<long long> expected = {9, 2, 1};
Entrada:
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"};

Saída esperada:
long[] expected = new long[] {9, 2, 1};

Explicação

Remover a coluna 0 apaga o 4 e desloca o 9 da coluna 2 para a coluna 1, então get 1 1 dá 9, a largura é 2 e sobra uma célula.

Como abordar

Tente sozinho primeiro e depois abra uma dica de cada vez.

Dica 1

Um mapa de (linha, coluna) para valor funciona bem; uma chave ausente significa 0.

Dica 2

Atribuir 0 a uma célula deve apagá-la, para que `count` continue correto.

Dica 3

Quando uma coluna for removida, reconstrua o mapa: descarte essa coluna e diminua em um os números das colunas maiores.

Complexidade esperada

tempo O(q × s), espaço extra O(s), s = células guardadas

Referências

Este desafio foi adaptado para o CodeUtility. Siga o enunciado e as restrições acima.

A melhor solução aprovada de cada programador. As mais rápidas, leves e mais bem avaliadas ficam no topo.

Ainda não há soluções aprovadas. Resolva e fique com o primeiro lugar.

Aprenda com outros

Soluções da comunidade

Ainda não há soluções publicadas. Resolva este desafio para compartilhar a primeira.