Todos os desafios
Fácil 0 resolvidos 0% de aceitação

Sequências no cara ou coroa

Encontre a maior sequência de caras, a maior sequência de coroas e o número de sequências em um registro de lançamentos de moeda.

O que você vai aprender

  • Dividir uma sequência em blocos máximos de valores iguais
  • Acompanhar a melhor sequência de cada valor
  • Contar as sequências

Problema

Ver original (inglês)

Um laboratório de probabilidade lança uma moeda muitas vezes e anota os resultados como uma string de H (cara) e T (coroa). Uma sequência é um grupo máximo de resultados iguais consecutivos; HHTHHH tem as sequências HH, T e HHH. Os alunos costumam se surpreender com o tamanho da maior sequência em um registro aleatório, então o laboratório mede isso.

Implemente coin_toss_streaks(tosses).

Entrada

tosses: os resultados em ordem, usando apenas H e T.

Saída

Retorne [longest_heads, longest_tails, streaks]: o tamanho da maior sequência de caras, o tamanho da maior sequência de coroas (0 se esse lado nunca sair) e o número total de sequências.

Restrições

0 ≤ tamanho de tosses ≤ 100 000

Exemplos

Exemplo 1
Entrada:
tosses = "HHTHHH"

Saída esperada:
expected = [3, 1, 3]
Entrada:
std::string tosses = "HHTHHH";

Saída esperada:
std::vector<long long> expected = {3, 1, 3};
Entrada:
string tosses = "HHTHHH";

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

Explicação

As sequências são HH, T e HHH, então a maior sequência de caras tem 3, a maior de coroas tem 1, e há 3 sequências.

Exemplo 2
Entrada:
tosses = "TTTT"

Saída esperada:
expected = [0, 4, 1]
Entrada:
std::string tosses = "TTTT";

Saída esperada:
std::vector<long long> expected = {0, 4, 1};
Entrada:
string tosses = "TTTT";

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

Explicação

Cara nunca sai, então a maior sequência de caras é 0; há uma sequência de coroas de tamanho 4: [0, 4, 1].

Como abordar

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

Dica 1

Uma nova sequência começa no índice 0 e em todo ponto em que um lançamento é diferente do anterior.

Dica 2

Guarde um melhor tamanho para as caras e outro para as coroas.

Dica 3

Uma string vazia não tem nenhuma sequência.

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.