Assign Cookies

Q: Assign Cookies algoritmasının zaman karmaşıklığı nedir?

İki diziyi sıralamak O(n log n + m log m) maliyetindedir ve ardından iki işaretçiyle yapılan tarama O(n + m) maliyetindedir; dolayısıyla baskın olan sıralamalardır. Yerinde sıralama, sıralamanın kendisinin kullandığı alan dışında ek alanı O(1) düzeyinde tutar.

Q: Kurabiye Dağıtımı için açgözlü seçim neden işe yarar?

k , en az açgözlü çocuğa uyan en küçük kurabiye olsun. En iyi eşleştirmenin bu çocuğa başka bir kurabiye verdiğini varsayalım. Yer değiştirin: Çocuk k kurabiyesini alır, k kurabiyesine sahip olan kişi de en az k kadar büyük olan diğer kurabiyeyi alır; böylece ikisi de doymuş olur. Sayı değişmez, dolayısıyla en iyi eşleştirme her zaman açgözlü seçimle başlayabilir ve aynı akıl yürütme kalan çocuklar ve kurabiyeler için de tekrarlanır.

KolayAçgözlü Sıralama

+10

Her i çocuğun bir açgözlülük faktörü g[i] vardır: onu mutlu eden en küçük kurabiye boyutu. Her j kurabiyesinin bir s[j] boyutu vardır. Bir çocuk, açgözlülük faktörüne eşit veya bundan büyük boyutta bir kurabiye aldığında mutlu olur. Her çocuk en fazla bir kurabiye alır ve her kurabiye en fazla bir çocuğa verilir. Mutlu edebileceğin en fazla çocuk sayısını döndür.

Fonksiyon

findContentChildren(g: integer-array, s: integer-array) → integer

ginteger-array: her çocuğun açgözlülük faktörü, kabul ettiği en küçük kurabiye boyutu
sinteger-array: her bir çerezin boyutu
Döndürürinteger: Açgözlülük faktörleri kadar büyük veya daha büyük birer kurabiye alabilen en fazla çocuk sayısı

Kısıtlar

1 ≤ g.length, s.length ≤ 5000
1 ≤ g[i], s[j] ≤ 10⁵
İki dizinin uzunlukları farklı olabilir ve hiçbiri sıralı değildir.

Örnekler

Girdi: g = [4, 2, 7]s = [3, 5, 1, 2]
Çıktı: 2
Açıklama: Sıralandığında, çocuklar 2, 4 ve 7 istiyor; kurabiyeler ise 1, 2, 3 ve 5. 2 numaralı kurabiye 2 isteyen çocuğu, 5 numaralı kurabiye ise 4 isteyen çocuğu doyurur. 7'ye ulaşabilecek hiçbir şey kalmadığından cevap 2'dir.

Gönderirken +16 gizli test

Ek soru

Ya her çocuğun kabul edeceği en büyük bir kurabiye de varsa ve bir kurabiye yalnızca belirli bir aralığa uyuyorsa? O zaman her kurabiye hangi bekleyen çocuğa verilmeli?

Çözüm

Soru, hangi çocuğa hangi kurabiyenin verileceğidir. Her eşleşmeyi denemek olasılıkları patlatır, ancak tek bir açgözlü kural sorunu çözer: önce en az açgözlü çocuğa hizmet et ve ona sığan en küçük kurabiyeyi ver. Her iki diziyi de sıraladıktan sonra bu kural, iki işaretçiyle yapılan tek bir gezinmeye dönüşür.

Her çocuk için sığan en küçük kurabiye

Doğru, ama en büyük testlerde bitmiyor

Sezgi

Çocukları en az açgözlüden en çok açgözlüye doğru ele al. Her çocuk için, henüz kullanılmamış tüm kurabiyelere bak ve yeterince büyük olanların en küçüğünü seç. Hiçbir kurabiye uygun değilse o çocuk aç kalır. İlk örnekte çocuklar 2, 4 ve 7 istiyor: 2 isteyen çocuk 2 numaralı kurabiyeyi alır, 4 isteyen çocuk 5 numaralı kurabiyeyi alır ve 7 isteyen için hiçbir şey kalmaz.

Neden uygun olan en küçük kurabiyeyi seçiyoruz? Daha büyük bir kurabiye, küçük olanın doyurabileceği her çocuğu doyurabilir, üstelik daha fazlasını da. İşe yarayan en küçük kurabiyeyi vermek, daha büyük kurabiyeleri daha sonra gelecek daha açgözlü çocuklara saklar; böylece doyurabileceğin bir çocuğu asla aç bırakmazsın.

Bedeli arama süresidir. n çocuğun her biri m kurabiyenin tümünü tarar; dolayısıyla n = m = 5000 olduğunda bu, 25 milyon kontrol demektir ve en büyük testler için fazla yavaştır.

Algoritma

Açgözlülük faktörlerini küçükten büyüğe sırala.
Kullanılıp kullanılmadığını belirten bir bayrağı her kurabiye için sakla.
Her çocuk için tüm kurabiyeleri tara ve boyutu çocuğun açgözlülük faktörüne en az eşit olan kullanılmamış en küçük kurabiyeyi aklında tut.
Bir tane bulduysan onu kullanılmış olarak işaretle ve çocuğu mutlu olarak say.
Sayıyı döndür.

def findContentChildren(g, s):
    used = [False] * len(s)
    fed = 0
    for need in sorted(g):  # least greedy child first
        best = -1
        for j in range(len(s)):
            if not used[j] and s[j] >= need and (best == -1 or s[j] < s[best]):
                best = j
        if best != -1:
            used[best] = True
            fed += 1
    return fed

İkisini de sıralayın ve iki işaretçi kullanın

Sezgi

Yukarıdaki tarama, tekrar tekrar uyan en küçük kurabiyeyi arar. Kurabiyeleri de sıralayın; böylece bu arama ortadan kalkar: Kurabiyeler boyutları artacak şekilde sıralanır, bu nedenle önce uyan en küçük kurabiyeyle karşılaşırsınız.

Kurabiyeleri en küçükten en büyüğe doğru ilerletin ve hâlâ bekleyen, en az açgözlü çocukta child işaretçisini tutun. Kurabiye en az g[child] boyutundaysa çocuk doyurulur ve işaretçi sonraki çocuğa ilerler. Daha küçükse, sıralı olduklarından hâlâ bekleyen tüm çocuklardan da küçüktür; dolayısıyla kurabiye işe yaramaz ve ilerlemeye devam edersiniz.

İlk örnekte sıralanmış kurabiyeler 1, 2, 3, 5; sıralanmış açgözlülük değerleri ise 2, 4, 7'dir. 1 numaralı kurabiye, 2 için çok küçüktür. 2 numaralı kurabiye, 2 isteyen çocuğu doyurur. 3 numaralı kurabiye, 4 için çok küçüktür. 5 numaralı kurabiye, 4 isteyen çocuğu doyurur. İşaretçi 2'de durur; cevap budur.

Her işaretçi yalnızca ileri hareket eder; bu nedenle taramanın karmaşıklığı O(n + m) olur ve süreyi esas olarak iki sıralama belirler. Yerinde sıralama için ek dizilere gerek yoktur.

Algoritma

g ve s dizilerini artan sırada sırala.
Hâlâ bekleyen en az açgözlü çocuk olan child = 0 değerini ata.
Her kurabiye için, en küçükten başlayarak: child hâlâ g dizisinin sınırları içindeyse ve kurabiye en az g[child] kadar büyükse child değerini 1 artır.
Beslenen çocuk sayısı olan child değerini döndür.

def findContentChildren(g, s):
    g.sort()
    s.sort()
    child = 0  # the least greedy child still waiting
    for size in s:  # smallest cookie first
        if child < len(g) and size >= g[child]:
            child += 1
    return child

Tuzaklar ve uç durumlar

Çoğu yanlış yanıt, eşleştirmeyi yanlış sırayla yapmaktan veya yanlış işaretçiyi ilerletmekten kaynaklanır.

Bir çocuğa ihtiyacından daha büyük bir kurabiye vermek. g = [1, 2] ve s = [1, 3] için, 1 isteyen çocuğa 3 numaralı kurabiyeyi vermek, 2 isteyen çocuğu aç bırakır; doğru eşleştirme ise ikisini de doyurur.
Kurabiye çok küçük olduğunda çocuk işaretçisini ilerletmek. Çocuğun hâlâ bir kurabiyeye ihtiyacı vardır; işe yaramayan kurabiyedir.
Çocuk işaretçisinin sınır kontrolünü unutmak. Her çocuk doyurulduktan sonra kalan kurabiyeler g dizisinin sonunu aşacak şekilde okunmamalıdır.
≥ yerine > ile karşılaştırmak. Açgözlülük katsayısıyla tam olarak aynı boyuttaki bir kurabiye yeterlidir.
Sayıları metin olarak sıralamak. JavaScript'te karşılaştırıcı olmadan kullanılan sort(), 10'u 9'dan önceye koyar.

Sıkça sorulan sorular4

Assign Cookies algoritmasının zaman karmaşıklığı nedir?

İki diziyi sıralamak O(n log n + m log m) maliyetindedir ve ardından iki işaretçiyle yapılan tarama O(n + m) maliyetindedir; dolayısıyla baskın olan sıralamalardır. Yerinde sıralama, sıralamanın kendisinin kullandığı alan dışında ek alanı O(1) düzeyinde tutar.

Kurabiye Dağıtımı için açgözlü seçim neden işe yarar?

k, en az açgözlü çocuğa uyan en küçük kurabiye olsun. En iyi eşleştirmenin bu çocuğa başka bir kurabiye verdiğini varsayalım. Yer değiştirin: Çocuk k kurabiyesini alır, k kurabiyesine sahip olan kişi de en az k kadar büyük olan diğer kurabiyeyi alır; böylece ikisi de doymuş olur. Sayı değişmez, dolayısıyla en iyi eşleştirme her zaman açgözlü seçimle başlayabilir ve aynı akıl yürütme kalan çocuklar ve kurabiyeler için de tekrarlanır.

En açgözlü çocuktan başlayabilir misin?

Evet. Her iki diziyi de sıralayın, ardından en büyük kurabiyeden ve en aç çocuktan başlayarak ilerleyin: kalan en büyük kurabiye kalan en aç çocuğa yetiyorsa ikisini de besleyin ve her iki işaretçiyi de ilerletin; yetmiyorsa o çocuk hiçbir kurabiyeyle doyurulamaz, bu yüzden çocuğu atlayın. Aynı sürede aynı sayıyı verir.

Assign Cookies dinamik programlama problemi midir?

Hayır. Bir yer değiştirme argümanı, açgözlü seçimin her zaman güvenli olduğunu gösterir; bu yüzden sıralama ve tek bir geçiş yeterlidir: O(n log n + m log m). En uzun ortak alt dizi tablosu gibi doldurulan, sıralanmış iki dizi üzerindeki bir tablo da yanıtı bulur; ancak aynı sonuç için O(n × m) zaman gerektirir.

Python

def findContentChildren(g, s):
    # Kodu buraya yazın

Test durumları

Durum 1

Durum 2

Girdi

g = [4, 2, 7]
s = [3, 5, 1, 2]

Beklenen