Todos os desafios
Médio 0 resolvidos 0% de aceitação

Maior sequência de lançamentos iguais

Descubra onde começa a maior sequência de lançamentos de dado iguais e consecutivos e qual é o tamanho dela.

O que você vai aprender

  • Detectar onde termina uma sequência de valores iguais
  • Guardar o início e o tamanho da melhor sequência
  • Desempatar a favor da primeira sequência

Problema

Ver original (inglês)

Um simulador de dados registra em uma lista cada lançamento de um dado de seis faces. Uma sequência é um grupo de lançamentos consecutivos com o mesmo valor; um lançamento sozinho é uma sequência de tamanho 1. Encontre a maior sequência. Se várias sequências empatarem no maior tamanho, informe a que começa primeiro.

Implemente longest_run_of_rolls(rolls).

Entrada

rolls: os lançamentos na ordem em que aconteceram, cada um de 1 a 6.

Saída

Retorne [start, length]: o índice (a partir de 0) em que a maior sequência começa e o tamanho dela. Para uma lista vazia, retorne [-1, 0].

Restrições

0 ≤ número de lançamentos ≤ 10 000

1 ≤ lançamento ≤ 6

Exemplos

Exemplo 1
Entrada:
rolls = [1, 4, 4, 2, 6, 6, 6, 3]

Saída esperada:
expected = [4, 3]
Entrada:
std::vector<long long> rolls = {1, 4, 4, 2, 6, 6, 6, 3};

Saída esperada:
std::vector<long long> expected = {4, 3};
Entrada:
long[] rolls = new long[] {1, 4, 4, 2, 6, 6, 6, 3};

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

Explicação

Os três 6 que começam no índice 4 superam os dois 4: [4, 3].

Exemplo 2
Entrada:
rolls = [5, 5, 2, 2, 3]

Saída esperada:
expected = [0, 2]
Entrada:
std::vector<long long> rolls = {5, 5, 2, 2, 3};

Saída esperada:
std::vector<long long> expected = {0, 2};
Entrada:
long[] rolls = new long[] {5, 5, 2, 2, 3};

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

Explicação

Os dois pares têm tamanho 2; os 5 começam primeiro, no índice 0: [0, 2].

Como abordar

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

Dica 1

Guarde onde a sequência atual começou.

Dica 2

Quando o valor mudar (ou a lista acabar), compare a sequência que terminou com a melhor até agora.

Dica 3

Só substitua a melhor quando a nova sequência for estritamente maior.

Complexidade esperada

tempo O(n), espaço extra O(1)

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.