Problema
Un simulatore registra in una lista ogni lancio di un dado a sei facce. Una serie è un gruppo di lanci consecutivi con lo stesso valore; un singolo lancio è una serie di lunghezza 1. Trova la serie più lunga. Se più serie hanno la stessa lunghezza massima, indica quella che inizia per prima.
Implementa longest_run_of_rolls(rolls).
Input
rolls: i lanci nell'ordine in cui sono avvenuti, ciascuno da 1 a 6.
Output
Restituisci [start, length]: l'indice (a partire da 0) in cui inizia la serie più lunga e la sua lunghezza. Per una lista vuota restituisci [-1, 0].
Vincoli
0 ≤ numero di lanci ≤ 10 000
1 ≤ lancio ≤ 6
Esempi
Input:
rolls = [1, 4, 4, 2, 6, 6, 6, 3]
Output atteso:
expected = [4, 3]
Input:
std::vector<long long> rolls = {1, 4, 4, 2, 6, 6, 6, 3};
Output atteso:
std::vector<long long> expected = {4, 3};
Input:
long[] rolls = new long[] {1, 4, 4, 2, 6, 6, 6, 3};
Output atteso:
long[] expected = new long[] {4, 3};
Spiegazione
I tre 6 a partire dall'indice 4 battono i due 4: [4, 3].
Input:
rolls = [5, 5, 2, 2, 3]
Output atteso:
expected = [0, 2]
Input:
std::vector<long long> rolls = {5, 5, 2, 2, 3};
Output atteso:
std::vector<long long> expected = {0, 2};
Input:
long[] rolls = new long[] {5, 5, 2, 2, 3};
Output atteso:
long[] expected = new long[] {0, 2};
Spiegazione
Entrambe le coppie hanno lunghezza 2; i 5 iniziano per primi, all'indice 0: [0, 2].
Come affrontarlo
Prova prima da solo, poi apri un suggerimento alla volta.
Suggerimento 1
Ricorda dove è iniziata la serie corrente.
Suggerimento 2
Quando il valore cambia (o la lista finisce), confronta la serie appena conclusa con la migliore.
Suggerimento 3
Sostituisci la migliore solo se la nuova serie è strettamente più lunga.
Complessità attesa
tempo O(n), spazio aggiuntivo O(1)
Riferimenti
Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.