Deux pointeurs, pas de table
Pourquoi c'est important « Trouve deux choses dont la somme fait X » a une réponse célèbre : mets tout dans un set et cherche le partenaire. C'est rapide, et ça demande une copie de toutes les données. Quand les données sont triées, tu n'as besoin de presque aucune mémoire.
Un service de cadeaux vend des lots de deux produits différents à un prix de lot fixe. La liste des prix des produits est triée, n'a pas de répétitions, et se trouve sur un appareil embarqué avec très peu de mémoire libre. Pour un prix de lot, il te faut le nombre de paires de produits dont les prix font exactement ce prix.
prices = [1, 2, 3, 4, 5, 6] # sorted, no repeats
count_pairs(Tape(prices), 7) # 3: (1, 6), (2, 5), (3, 4)Écris count_pairs(tape, target). tape est une Tape de prix entiers, triés par ordre croissant, sans répétitions. Renvoie combien de paires de deux éléments différents font exactement target (chaque paire comptée une fois). Budgets : pour 20 000 éléments, lis au plus 60 000 valeurs, et utilise au plus 16 000 octets de mémoire de travail pendant l'exécution de ta fonction (mesurés avec tracemalloc ; un set ou une liste des 20 000 prix dépasse 150 000 octets). len(tape) est gratuit.
Tu as repéré un problème dans cette leçon ? Signale-le · Pose une question sur cette leçon
Cet exercice s'ouvre bientôt
Termine la leçon précédente pour débloquer celle-ci. Tout le cours est gratuit, aucun compte n'est requis, et tu peux lire cette leçon dès maintenant.
Ce navigateur bloque les cookies pour learn.floati.life, donc les leçons que tu as terminées ici ne peuvent pas s'ouvrir dans l'ordre. Autorise les cookies pour ce site et recharge la page.