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
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].
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.