Jewels and Stones

Q: Jewels and Stones'un zaman karmaşıklığı nedir?

Bir küme kullanıldığında karmaşıklık O(j + s) olur: jewels 'tan kümeyi oluşturmak için j adım ve s taşın her biri için sabit zamanlı bir arama. Her taş için jewels 'ı taramak O(j × s) karmaşıklığındadır.

BaşlangıçHashing

+10

Sana harflerden oluşan iki dize verilir. jewels içindeki her harf bir mücevher türünü belirtir ve hiçbir harf tekrarlanmaz. stones içindeki her harf, sahip olduğun bir taşı temsil eder. Taşlarından kaçının mücevher olduğunu döndür. Harfler büyük/küçük harfe duyarlıdır: "a" ve "A" farklı türlerdir.

Fonksiyon

numJewelsInStones(jewels: string, stones: string) → integer

jewelsstring: mücevher sayılan taş türleri, her biri bir harf
stonesstring: sahip olduğun taşlar, her biri bir harf
Döndürürinteger: harfi mücevherlerde bulunan taşların sayısı

Kısıtlar

1 ≤ jewels.length ≤ 52
1 ≤ stones.length ≤ 10⁴
Her iki dizge de yalnızca İngilizce harfler içerir; küçük ve büyük harfler.
jewels harflerinin tümü birbirinden farklıdır.

Örnekler

Girdi: jewels = "rR"stones = "rubyRRr"
Çıktı: 4
Açıklama: Mücevher türleri r ve R'dir. rubyRRr içinde r, R, R ve r taşları eşleşirken u, b ve y eşleşmez; bu nedenle cevap 4'tür.

Girdi: jewels = "z"stones = "ZZZ"
Çıktı: 0
Açıklama: Tek mücevher türü küçük harfli z’dir. Her taş büyük harfli Z’dir ve farklı bir türdür; bu yüzden hiçbiri sayılmaz.

Gönderirken +12 gizli test

İpuçları

Tek tek açın. Her biri biraz daha fazlasını gösterir.

3 ipucundan 0 açıldı

Çözüm

Her taş için bir yanıt gerekir: bu harf bir mücevher mi? Her taş için jewels dizgesinde arama yapmak aynı taramayı tekrar tekrar yapar. Mücevher harflerini bir kümeye bir kez ekle; böylece her taş için tek bir arama yeterli olur.

Her taş için mücevherleri tara

Sezgi

Taşları teker teker ele al. Her taş için jewels dizisini tara ve ona eşit olan ilk harfte dur. Eşleşme, sayaca 1 ekler. İlk örnekte u taşı r ve R ile karşılaştırılır, eşleşme bulunamaz ve sayaç artmaz.

İlk eşleşmede durabilirsin; çünkü mücevher harflerinin hepsi farklıdır, dolayısıyla bir taş en fazla biriyle eşleşebilir. Mücevher olmayan bir taşı ise bunu anlayana kadar tüm mücevher harfleriyle karşılaştırman gerekir.

j mücevher türü ve s taş için en fazla j × s karşılaştırma yapılır. Burada j ≤ 52, dolayısıyla 10^4 taş bile yaklaşık 5 × 10^5 karşılaştırmaya mal olur ve tarama zamanında tamamlanır. Tür listesinin büyümesiyle verimsizlik ortaya çıkar: aynı arama her taş için yeniden yapılır.

Algoritma

count değerini 0 olarak ayarla.
Her taş için, onu jewels dizgesindeki her harfle karşılaştır.
İlk eşleşen harfte, count değerine 1 ekle ve sonraki taşa geç.
count değerini döndür.

def numJewelsInStones(jewels, stones):
    count = 0
    for stone in stones:
        for jewel in jewels:
            if stone == jewel:
                count += 1
                break  # the kinds are distinct: no second match is possible
    return count

Mücevherleri bir kümeye koy

Sezgi

"Bu harf bir mücevher mi?" sorusunun yanıtı, aynı harf için her sorduğunda aynıdır. Bu yüzden her tür için bir kez yanıtla: jewels harflerinden bir küme oluştur. Küme, üyelik sorgularını sabit zamanda yanıtlar; böylece her taş için tarama yapmak yerine tek bir arama gerekir.

İlk örnekte küme {r, R} olur. rubyRRr üzerinde ilerlerken aramalar sırasıyla evet, hayır, hayır, hayır, evet, evet, evet yanıtını verir: dört mücevher. Kümeyi oluşturmak j adım, dizi boyunca ilerlemek s adım sürer; dolayısıyla toplam süre O(j + s) olur.

Küme en fazla 52 harf tutar. Yerleşik küme desteği olmayan bir dilde, karakter koduna göre indekslenmiş bir bayrak dizisi aynı işi görür.

Algoritma

jewels içindeki her harfi içeren bir küme oluştur.
count değerini 0 olarak ayarla.
Her taş için, küme taşı içeriyorsa count değerine 1 ekle.
count değerini döndür.

def numJewelsInStones(jewels, stones):
    kinds = set(jewels)
    count = 0
    for stone in stones:
        if stone in kinds:
            count += 1
    return count

Tuzaklar ve uç durumlar

Algoritma tek bir döngüden oluşur. Yanlış yanıtlar, harflerin nasıl karşılaştırılıp sayıldığından kaynaklanır.

Büyük-küçük harf farkını göz ardı etmek. Her iki dizenin de harflerini küçültmek, z ile Z karakterlerinin eşleşmesini sağlar ve ikinci örnek 0 yerine 3 döndürür.
Taşlar yerine farklı mücevher türlerini saymak. rubyRRr iki tür mücevher ama dört mücevher taşı içerir; tekrarlar da dahil olmak üzere her taş sayılır.
Kümeyi taş döngüsünün içinde oluşturmak. Her taş için yeniden oluşturmak, her seferinde j adım gerektirir ve taramanın O(j × s) maliyetini geri getirir. Kümeyi döngüden önce, bir kez oluşturun.
Argümanların sırasını değiştirmek. Küme jewels değerini içermeli ve döngü stones üzerinde ilerlemelidir. Roller ters çevrildiğinde ikinci örnek, z türündeki tek mücevheri taşlarla karşılaştırıp yine 0 sonucunu verir; ancak ("a", "aaa"), 3 yerine 1 döndürür.

Sıkça sorulan sorular3

Jewels and Stones'un zaman karmaşıklığı nedir?

Bir küme kullanıldığında karmaşıklık O(j + s) olur: jewels'tan kümeyi oluşturmak için j adım ve s taşın her biri için sabit zamanlı bir arama. Her taş için jewels'ı taramak O(j × s) karmaşıklığındadır.

Jewels and Stones için neden bir hash set kullanılır?

Her taş, harfinin bir mücevher olup olmadığını sorar. Bir hash kümesi bu soruyu sabit zamanda yanıtlar; jewels dizgesinde arama yapmaksa dizgenin uzunluğuyla orantılı zaman alır. Kümeyi oluşturmak için bir kez zaman harcarsın ve sonrasında her taşta zamandan tasarruf edersin.

Bunu bir küme kullanmadan çözebilir misin?

Evet. Harfler İngilizce harfleri olduğundan, karakter koduna göre indekslenen 128 veya 256 bayraklı bir dizi, hiç karma işlemi gerektirmeyen bir küme olarak çalışır. Her mücevher harfini işaretleyin, ardından bayrağı ayarlı olan taşları sayın. Ruby'deki stones.count(jewels) tüm işi tek bir çağrıda yapar, ancak bayrak dizisi arka planda neler olduğunu gösterir.

Python

def numJewelsInStones(jewels, stones):
    # Kodu buraya yazın

Test durumları

Durum 1

Durum 2

Girdi

jewels = "rR"
stones = "rubyRRr"

Beklenen