Müfredat 148 dersinden 55. · Önbelleksiz hız
Önbelleksiz hız

İki işaretçi, tablo yok

Neden önemli "Toplamı X eden iki şey bul" sorusunun ünlü bir cevabı vardır: her şeyi bir set içine koy ve eşini ara. Bu hızlıdır ve tüm verinin bir kopyasını gerektirir. Veri sıralı olduğunda ise neredeyse hiç belleğe ihtiyaç duymazsın.

A hediye servisi, iki farklı ürünün paketini sabit bir paket fiyatına satıyor. Ürün fiyat listesi sıralı, tekrar içermiyor ve çok az boş belleği olan gömülü bir cihazda duruyor. Bir paket fiyatı için, fiyatları tam olarak o fiyata eşit olan ürün çiftlerinin sayısına ihtiyacın var.

prices = [1, 2, 3, 4, 5, 6]   # sorted, no repeats
count_pairs(Tape(prices), 7)    # 3: (1, 6), (2, 5), (3, 4)
Senin sıran

count_pairs(tape, target) yaz. tape, tekrarsız ve küçükten büyüğe sıralanmış tam sayı fiyatlarından oluşan bir Tape. Toplamı tam olarak target eden iki farklı öğeden oluşan kaç çift olduğunu döndür (her çift bir kez sayılır). Bütçeler:, 20.000 öğe için en fazla 60.000 değer okunmalı ve fonksiyonun çalışırken en fazla 16.000 bayt çalışma belleği kullanılmalı (tracemalloc ile ölçülür; 20.000 fiyatın kümesi veya listesi 150.000 bayttan fazladır). len(tape) ücretsizdir.

Bu derste bir sorun mu fark ettin? Bildir · Bu ders hakkında soru sor

Bu alıştırma yakında açılacak

Bu dersi bitirince bu ders açılacak. Kursun tamamı ücretsiz, hesap gerekmiyor ve bu dersi hemen şimdi okuyabilirsin.