Twee pointers, geen tabel
Waarom dit ertoe doet "Vind twee dingen die samen X vormen" heeft een bekend antwoord: zet alles in een set en zoek de partner op. Het is snel, en het heeft een kopie van alle data nodig. Als de data gesorteerd is, heb je bijna geen geheugen nodig.
A gift service verkoopt bundels van twee verschillende producten voor een vaste bundelprijs. De productprijslijst is gesorteerd, heeft geen herhalingen en staat op een ingebed apparaat met heel weinig vrij geheugen. Voor een bundelprijs heb je het aantal productparen nodig waarvan de prijzen precies optellen tot die prijs.
prices = [1, 2, 3, 4, 5, 6] # sorted, no repeats
count_pairs(Tape(prices), 7) # 3: (1, 6), (2, 5), (3, 4)Schrijf count_pairs(tape, target). tape is een Tape van gehele prijzen, gesorteerd in oplopende volgorde, zonder herhalingen. Geef terug hoeveel paren van twee verschillende items precies optellen tot target (elk paar één keer geteld). Budgets: voor 20.000 items gelezen met maximaal 60.000 waarden, en gebruik maximaal 16.000 bytes aan werkgeheugen terwijl je functie draait (gemeten met tracemalloc; een set of lijst van de 20.000 prijzen is meer dan 150.000 bytes). len(tape) is gratis.
Een probleem ontdekt in deze les? Meld het · Vraag naar deze les
Deze oefening opent binnenkort
Maak de les ervoor af voordat deze wordt ontgrendeld. De hele cursus is gratis, geen account nodig, en je kunt deze les nu lezen.
Deze browser blokkeert cookies voor learn.floati.life, dus lessen die je hier hebt afgerond kunnen niet in de juiste volgorde worden geopend. Sta cookies toe voor deze site en laad de pagina opnieuw.