Count a Character

+10

Bir s dizgesi ve tek bir c harfi verilir. c harfinin s içinde kaç kez geçtiğini döndürün. Eşleşme büyük-küçük harfe duyarlıdır: B ve b farklı karakterlerdir.

Fonksiyon

countChar(s: string, c: string) → integer

sstring: aranacak İngilizce harf dizisi
cstring: sayılacak tek harf
Döndürürinteger: s dizgesinin kaç karakteri c'ye eşittir

Kısıtlar

1 ≤ s.length ≤ 5 × 10⁴
s yalnızca İngilizce harfler (a ile z arası, A ile Z arası) içerir.
c tam olarak bir İngilizce harftir.

Örnekler

Girdi: s = "Mississippi"c = "s"
Çıktı: 4
Açıklama: Mississippi sözcüğünde 2, 3, 5 ve 6 indekslerinde s bulunur, bu yüzden cevap 4'tür.

Girdi: s = "Banana"c = "b"
Çıktı: 0
Açıklama: Banana büyük B harfiyle başlıyor ve sen küçük b harfini arıyorsun. Hiçbir eşleşme yok, bu yüzden yanıt 0.

Ek soru

c, ss gibi birkaç harften oluşan bir sözcük olsaydı ne olurdu? Örtüşen eşleşmeler sayılır mı ve döngünüz nasıl değişir?

İpuçları

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

3 ipucundan 0 açıldı

Çözüm

s'nin herhangi bir karakteri c olabilir, bu yüzden her birine bir kez bakıp eşleşmeleri sayarsın. Büyük-küçük harf duyarlılığına dikkat et: büyük harf farklı bir karakterdir.

Her c karakterini sil ve uzunlukları karşılaştır

Sezgi

Her c karakteri çıkararak s dizisinin bir kopyasını oluştur. Her çıkarma, kopyayı bir karakter kısaltır; dolayısıyla uzunluk farkı sayıdır. Mississippi için kopya Miiippi olur: 11 eksi 7, 4 eder.

Zaman karmaşıklığı O(n)'dir, ancak kopya, bir sayacın ihtiyaç duymadığı O(n) ek bellek kullanır.

Algoritma

c değerine eşit olan her karakteri dışarıda bırakan s kopyasını oluştur.
s uzunluğunu ve kopyanın uzunluğunu ölç.
s uzunluğundan kopyanın uzunluğunu çıkarıp sonucu döndür.

def countChar(s, c):
    # Every c that disappears makes the string one character shorter.
    without = s.replace(c, "")
    return len(s) - len(without)

Sayaçla tek geçiş

Sezgi

Kopyasını oluşturmak yerine okurken say. Bir sayaç 0'dan başlar ve c'ye eşit olan her karakter için 1 artar. Basit eşitlik, büyük harflerin küçük harflerle eşleşmesini önler.

Her karakter yalnızca bir kez karşılaştırılır ve yalnızca sayaç saklanır: O(n) zaman, O(1) alan. Hiçbir çözüm O(n) zamandan daha iyisini yapamaz; çünkü atladığın bir karakter bir c daha olabilir.

Algoritma

Hedef harfi c'den oku ve count = 0 olarak ayarla.
s üzerinde her seferinde bir karakter ilerle.
Karakter hedef harfe eşitse count'a 1 ekle.
count'u döndür.

def countChar(s, c):
    count = 0
    for ch in s:
        if ch == c:
            count += 1
    return count

Tuzaklar ve uç durumlar

Büyük/küçük harf duyarlılığını yok saymak. Her iki tarafı da küçük harfe çevirmek, Banana ile b için 1 döndürür; doğru yanıt 0'dır.
Bir karakteri bir dizgeyle karşılaştırmak. Java, C, C++, C# ve Go'da c bir dizge olarak gelirken s[i] veya s.charAt(i) tek bir karakterdir. Döngüden önce bir kez c[0] (veya c.charAt(0)) alın.
Java'da dizgeleri == ile karşılaştırmak. String.valueOf(s.charAt(i)) == c nesne kimliğini karşılaştırır ve neredeyse her zaman false sonucunu verir. char değerlerini karşılaştırın.
C'de döngü koşulunda strlen(s) çağırmak. Bu, dizgeyi her adımda yeniden tarar; dolayısıyla 5 × 10^4 karakter yaklaşık 2.5 × 10^9 adıma mal olur.

Sıkça sorulan sorular3

Bir dizgedeki bir karakterin kaç kez geçtiğini nasıl sayarsın?

Dizgeyi 0'dan başlayan bir sayaçla bir kez dolaşın ve geçerli karakter aradığınız karaktere her eşit olduğunda sayaca 1 ekleyin. Bu işlem O(n) zaman ve O(1) ek bellek gerektirir. Büyük/küçük harfe duyarsız bir sayım için önce hem dizgeyi hem de harfi küçük harfe dönüştürün.

Bir mülakatta yerleşik bir count fonksiyonunu kullanabilir miyim?

Genellikle evet, maliyetini açıklayabildiğin sürece. Python'ın str.count ve benzeri işlevleri yine de dizenin tamamını okur, bu yüzden O(n) karmaşıklığındadır. Görüşmeci isterse döngüyü yazmaya hazır ol.

Her karakteri bir kerede nasıl sayardın?

Tek bir geçiş yapın ve her karakterin sayısını bir hash map'te veya İngilizce harfler için 52 sayaçtan oluşan bir dizide tutun. Bu geçişten sonra herhangi bir harfin sayısını tek bir aramayla bulabilirsiniz. Aynı dizgedeki birçok harf hakkında soru sorulduğunda bunu kullanın.

def countChar(s, c):
    # Kodu buraya yazın

Test #1

Test #2

Argümanlar

s = "Mississippi"
c = "s"

Beklenen Çıktı