Tous les défis
Facile 0 résolus 0 % de réussite

Séries à pile ou face

Trouvez la plus longue série de faces, la plus longue série de piles et le nombre total de séries dans une suite de lancers de pièce.

Ce que vous allez apprendre

  • Découper une suite en séries maximales
  • Suivre la meilleure série pour chaque valeur
  • Compter les séries

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

Exemple 1
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.

Exemple 2
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.

La meilleure solution validée de chaque codeur. Les plus rapides, les plus légères et les mieux notées passent devant.

Aucune solution validée pour l'instant. Résolvez-le et prenez la première place.

Apprenez des autres

Solutions de la communauté

Aucune solution publiée pour l'instant. Résolvez ce défi pour partager la première.