Zwei Zeiger, keine Tabelle
Warum das wichtig ist "Finde zwei Dinge, die sich zu X addieren" hat eine berühmte versiegelte Antwort: packe alles in ein Set und suche den Partner. Es ist schnell und es braucht eine Kopie aller Daten. Wenn die Daten sortiert sind, brauchst du fast gar keinen Speicher.
A gift service verkauft Bundles von zwei verschiedenen Produkten für einen festen Bundle-Preis. Die Produktpreisliste ist sortiert, hat keine Wiederholungen und befindet sich auf einem eingebetteten Gerät mit sehr wenig freiem Speicher. Für einen Bundle-Preis benötigst du die Anzahl der Produktpaare, deren Preise genau diesen Preis ergeben.
prices = [1, 2, 3, 4, 5, 6] # sorted, no repeats
count_pairs(Tape(prices), 7) # 3: (1, 6), (2, 5), (3, 4)Schreibe count_pairs(tape, target). tape ist eine Tape von Ganzzahlpreisen, aufsteigend sortiert, ohne Wiederholungen. Gib zurück, wie viele Paare von zwei verschiedenen Artikeln genau target ergeben (jedes Paar wird einmal gezählt). Budgets: für 20.000 Artikel, lies höchstens 60.000 Werte und verwende höchstens 16.000 Bytes Arbeitsspeicher, während deine Funktion läuft (gemessen mit tracemalloc; eine Menge oder Liste der 20.000 Preise ist über 150.000 Bytes). len(tape) ist frei.
Ein Problem in dieser Lektion entdeckt? Melde es · Frage zu dieser Lektion
Diese Übung öffnet bald
Beende die vorherige Lektion, damit diese freigeschaltet wird. Der ganze Kurs ist kostenlos, kein Konto erforderlich, und du kannst diese Lektion jetzt direkt lesen.
Dieser Browser blockiert Cookies für learn.floati.life, daher können hier beendigte Lektionen nicht in der richtigen Reihenfolge geöffnet werden. Erlaube Cookies für diese Seite und lade sie neu.