Tutte le sfide
Facile 0 risolte 0% di accettazione

Serie di lanci di una moneta

In una sequenza di lanci di una moneta, trova la serie più lunga di teste, la serie più lunga di croci e il numero totale di serie.

Cosa imparerai

  • Suddividere una sequenza in serie massimali
  • Tenere la serie migliore per ciascun valore
  • Contare le serie

Problema

In un laboratorio di probabilità si lancia una moneta molte volte e si annotano i risultati come una stringa di H (testa) e T (croce). Una serie è un gruppo massimale di risultati uguali consecutivi; HHTHHH contiene le serie HH, T e HHH. Gli studenti si stupiscono spesso di quanto sia lunga la serie più lunga in una sequenza casuale, perciò il laboratorio la misura.

Implementa coin_toss_streaks(tosses).

Input

tosses: i risultati in ordine, usando solo H e T.

Output

Restituisci [longest_heads, longest_tails, streaks]: la lunghezza della serie di teste più lunga, la lunghezza della serie di croci più lunga (0 se quella faccia non esce mai) e il numero totale di serie.

Vincoli

0 ≤ lunghezza di tosses ≤ 100 000

Esempi

Esempio 1
Input:
tosses = "HHTHHH"

Output atteso:
expected = [3, 1, 3]
Input:
std::string tosses = "HHTHHH";

Output atteso:
std::vector<long long> expected = {3, 1, 3};
Input:
string tosses = "HHTHHH";

Output atteso:
long[] expected = new long[] {3, 1, 3};

Spiegazione

Le serie sono HH, T e HHH, quindi la serie di teste più lunga è 3, quella di croci più lunga è 1 e le serie sono 3.

Esempio 2
Input:
tosses = "TTTT"

Output atteso:
expected = [0, 4, 1]
Input:
std::string tosses = "TTTT";

Output atteso:
std::vector<long long> expected = {0, 4, 1};
Input:
string tosses = "TTTT";

Output atteso:
long[] expected = new long[] {0, 4, 1};

Spiegazione

Testa non esce mai, quindi la sua serie più lunga è 0; c'è una sola serie di croci, lunga 4: [0, 4, 1].

Come affrontarlo

Prova prima da solo, poi apri un suggerimento alla volta.

Suggerimento 1

Una nuova serie inizia all'indice 0 e in ogni punto in cui un lancio è diverso dal precedente.

Suggerimento 2

Tieni una lunghezza massima per le teste e una per le croci.

Suggerimento 3

Una stringa vuota non contiene nessuna serie.

Complessità attesa

tempo O(n), spazio aggiuntivo O(1)

Riferimenti

Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.

La migliore soluzione superata di ogni programmatore. Le più veloci, leggere e meglio valutate stanno in alto.

Ancora nessuna soluzione superata. Risolvila e prendi il primo posto.

Impara dagli altri

Soluzioni della community

Nessuna soluzione pubblicata. Risolvi questa sfida per condividere la prima.