Problème
Un laboratoire de probabilités lance une pièce de nombreuses fois et note les résultats sous forme d'une chaîne de H (face, heads) et de T (pile, tails). Une série est un groupe maximal de résultats identiques consécutifs ; HHTHHH contient les séries HH, T et HHH. Les élèves sont souvent surpris par la longueur de la plus longue série dans une suite aléatoire, alors le laboratoire la mesure.
Implémentez coin_toss_streaks(tosses).
Entrée
tosses : les résultats dans l'ordre, uniquement avec H et T.
Sortie
Renvoyez [longest_heads, longest_tails, streaks] : la longueur de la plus longue série de faces, la longueur de la plus longue série de piles (0 si ce côté ne sort jamais) et le nombre total de séries.
Contraintes
0 ≤ longueur de tosses ≤ 100 000
Exemples
Entrée :
tosses = "HHTHHH"
Sortie attendue :
expected = [3, 1, 3]
Entrée :
std::string tosses = "HHTHHH";
Sortie attendue :
std::vector<long long> expected = {3, 1, 3};
Entrée :
string tosses = "HHTHHH";
Sortie attendue :
long[] expected = new long[] {3, 1, 3};
Explication
Les séries sont HH, T et HHH, donc la plus longue série de faces mesure 3, la plus longue série de piles 1, et il y a 3 séries.
Entrée :
tosses = "TTTT"
Sortie attendue :
expected = [0, 4, 1]
Entrée :
std::string tosses = "TTTT";
Sortie attendue :
std::vector<long long> expected = {0, 4, 1};
Entrée :
string tosses = "TTTT";
Sortie attendue :
long[] expected = new long[] {0, 4, 1};
Explication
Face ne sort jamais, donc sa plus longue série vaut 0 ; il y a une seule série de piles, de longueur 4 : [0, 4, 1].
Comment l'aborder
Essayez d'abord seul, puis ouvrez les indices un par un.
Indice 1
Une nouvelle série commence à l'indice 0 et partout où un lancer diffère du précédent.
Indice 2
Gardez une meilleure longueur pour face et une pour pile.
Indice 3
Une chaîne vide ne contient aucune série.
Complexité attendue
temps O(n), espace supplémentaire O(1)
Références
Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.