Due puntatori, nessuna tabella
Perché è importante "Trova due cose che sommate fanno X" ha una risposta famosa: metti tutto in un set e cerca il partner. È veloce, e richiede una copia di tutti i dati. Quando i dati sono ordinati, non ti serve quasi nessuna memoria.
Un servizio regali vende pacchetti di due prodotti diversi a un prezzo fisso del pacchetto. Il listino prezzi dei prodotti è ordinato, non ha ripetizioni, e sta su un dispositivo embedded con pochissima memoria libera. Per un prezzo del pacchetto, ti serve il numero di coppie di prodotti i cui prezzi sommati fanno esattamente quel prezzo.
prices = [1, 2, 3, 4, 5, 6] # sorted, no repeats
count_pairs(Tape(prices), 7) # 3: (1, 6), (2, 5), (3, 4)Scrivi count_pairs(tape, target). tape è un Tape di prezzi interi, in ordine crescente, senza ripetizioni. Restituisci quante coppie di due elementi diversi sommate fanno esattamente target (ogni coppia contata una volta). Budget: per 20,000 elementi leggi al massimo 60,000 valori, e usa al massimo 16,000 byte di memoria di lavoro mentre la tua funzione gira (misurati con tracemalloc; un set o una lista dei 20,000 prezzi supera i 150,000 byte). len(tape) è gratis.
Hai notato un problema in questa lezione? Segnalalo · Chiedi qualcosa su questa lezione
Questo esercizio si apre presto
Finisci la lezione precedente e questa si sblocca. L'intero corso è gratuito, senza account, e puoi leggere questa lezione subito.
Questo browser blocca i cookie per learn.floati.life, quindi le lezioni che hai finito qui non si possono aprire in ordine. Consenti i cookie per questo sito e ricarica.