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

Plus longue série de lancers de dé

Trouvez où commence la plus longue série de lancers de dé consécutifs identiques et quelle est sa longueur.

Ce que vous allez apprendre

  • Détecter la fin d'une série de valeurs égales
  • Conserver le début et la longueur de la meilleure série
  • Départager les égalités en faveur de la première série

Problème

Un simulateur de dé enregistre chaque lancer d'un dé à six faces dans une liste. Une série est un groupe de lancers consécutifs de même valeur ; un lancer isolé forme une série de longueur 1. Trouvez la plus longue série. Si plusieurs séries ont la même longueur maximale, donnez celle qui commence en premier.

Implémentez longest_run_of_rolls(rolls).

Entrée

rolls : les lancers dans l'ordre où ils ont eu lieu, chacun entre 1 et 6.

Sortie

Renvoyez [start, length] : l'indice (à partir de 0) où commence la plus longue série, et sa longueur. Pour une liste vide, renvoyez [-1, 0].

Contraintes

0 ≤ nombre de lancers ≤ 10 000

1 ≤ lancer ≤ 6

Exemples

Exemple 1
Entrée :
rolls = [1, 4, 4, 2, 6, 6, 6, 3]

Sortie attendue :
expected = [4, 3]
Entrée :
std::vector<long long> rolls = {1, 4, 4, 2, 6, 6, 6, 3};

Sortie attendue :
std::vector<long long> expected = {4, 3};
Entrée :
long[] rolls = new long[] {1, 4, 4, 2, 6, 6, 6, 3};

Sortie attendue :
long[] expected = new long[] {4, 3};

Explication

Les trois 6 qui commencent à l'indice 4 battent les deux 4 : [4, 3].

Exemple 2
Entrée :
rolls = [5, 5, 2, 2, 3]

Sortie attendue :
expected = [0, 2]
Entrée :
std::vector<long long> rolls = {5, 5, 2, 2, 3};

Sortie attendue :
std::vector<long long> expected = {0, 2};
Entrée :
long[] rolls = new long[] {5, 5, 2, 2, 3};

Sortie attendue :
long[] expected = new long[] {0, 2};

Explication

Les deux paires ont une longueur de 2 ; les 5 commencent en premier, à l'indice 0 : [0, 2].

Comment l'aborder

Essayez d'abord seul, puis ouvrez les indices un par un.

Indice 1

Retenez où la série en cours a commencé.

Indice 2

Quand la valeur change (ou que la liste se termine), comparez la série qui vient de finir à la meilleure.

Indice 3

Ne remplacez la meilleure série que si la nouvelle est strictement plus longue.

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.