Count a Character

Q: Bir karakteri saymak büyük/küçük harfe duyarlı mıdır?

Bu problemde evet: B ve b farklı karakterlerdir, bu nedenle Banana içinde b yoktur. Bunun yerine büyük/küçük harf duyarsız bir sayım gerekiyorsa, karşılaştırmadan önce hem dizeyi hem de harfi küçük harfe dönüştür.

BaşlangıçDiziler ve dizgiler

+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, bu nedenle yalnızca c ile tam olarak eşleşen karakterler sayılır.

Fonksiyon

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

sstring: aranacak İngilizce harf dizisi
cstring: saymak için tek harf
Döndürürinteger: s'nin kaç karakteri c'ye eşittir

Kısıtlar

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

Örnekler

Girdi: s = "Mississippi"c = "s"
Çıktı: 4
Açıklama: Mississippi sözcüğünde, 0'dan başlayarak sayıldığında 2, 3, 5 ve 6. konumlarda s bulunur, bu nedenle cevap 4'tür.

Girdi: s = "Banana"c = "b"
Çıktı: 0
Açıklama: Banana büyük B harfiyle başlar, arama ise küçük b harfini bulmaya yöneliktir. İkisi farklı olduğundan hiçbir eşleşme bulunmaz ve sonuç 0 olur.

Gönderirken +18 gizli test

Ek soru

Peki ya c, ss gibi birkaç harften oluşan bir sözcük olabilseydi? Ö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 içindeki her karaktere bir kez bakılmalıdır, çünkü bunlardan herhangi biri c olabilir. İşlem, sayaçla tek bir geçiştir. İnsanların kafasını karıştıran ayrıntılar büyük/küçük harf ayrımı (büyük harf farklı bir karakterdir) ve bazı dillerde bir karakteri tek harfli bir dizgeyle karşılaştırmaktır.

Her c'yi silin ve uzunlukları karşılaştırın

Sezgi

Her c karakteri kaldırarak s'nin bir kopyasını oluştur. Kaldırılan her karakter kopyayı bir karakter kısaltır; bu nedenle iki uzunluk arasındaki fark, c karakterinin kaç kez geçtiğine eşittir. Çoğu dilde bu kaldırma işlemini yapan bir replace veya delete fonksiyonu bulunur.

Mississippi ve s için kopya Miiippi olur. Bu, özgün 11 karaktere karşılık 7 karakterdir; dolayısıyla c 4 kez geçmiştir. Banana ve b için büyük B eşleşmediğinden hiçbir şey kaldırılmaz ve fark 0 olur.

İşlem, s üzerinde tek bir geçişten oluşur; dolayısıyla zaman karmaşıklığı O(n)'dir. Maliyet bellektir: kopya, s kadar uzun olabilir; bu da bir sayacın gerektirmediği O(n) ek alan demektir.

Algoritma

c karakterine eşit olan tüm karakterleri dışarıda bırakan bir s kopyası oluştur.
s'nin uzunluğunu ve kopyanın uzunluğunu ölç.
s'nin uzunluğundan kopyanın uzunluğunu çıkar ve 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)

Bir sayaçla tek geçiş

Sezgi

Kopyalamayı atla ve okurken say. s üzerinde soldan sağa ilerle; 0'dan başlayan bir sayaç tut ve geçerli karakter c'ye eşit olduğunda sayacı 1 artır. Eşleşme basit eşitlikle belirlenir, bu nedenle büyük bir harf küçük bir harfle asla eşleşmez.

Mississippi için sayaç 2, 3, 5 ve 6 indislerinde artar ve sonuçta 4 olur. Her karakter bir kez karşılaştırılır ve başka hiçbir şey saklanmaz.

Bu, O(n) zaman ve O(1) ek alan gerektirir: bir sayaç ve hedef harf. Zaman açısından daha iyisini yapamazsın, çünkü atladığın bir karakter bir c daha olabilir.

Algoritma

Hedef harfi c üzerinden oku ve count = 0 olarak ayarla.
s içinde her seferinde bir karakter ilerle.
Karakter hedefle eşleşiyorsa count değerine 1 ekle.
count değerini döndür.

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

Tuzaklar ve uç durumlar

Döngü kısa, hatalar ise iki değerin karşılaştırılma biçiminde gizli.

Büyük/küçük harf farkını yok saymak. Her iki tarafı da küçük harfe çevirmek, Banana ile b karşılaştırmasının 1 döndürmesini sağlar; ancak görev tam eşleşme istediğinden yanıt 0'dır.
Bir karakteri bir dizeyle karşılaştırmak. Java, C, C++, C# ve Go'da c bir dize olarak gelirken s.charAt(i) veya s[i] tek bir karakterdir. Döngüden önce bir kez c[0] (veya c.charAt(0)) alın.
Java'da dizeleri == 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 veya equals kullanın.
C'de döngü koşulunda strlen(s) çağırmak. Bu, her adımda dizenin tamamını dolaşır; dolayısıyla 5 × 10^4 karakter yaklaşık 2.5 × 10^9 adıma mal olur. Bunun yerine '\0' sonlandırıcısında durun.

Sıkça sorulan sorular4

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

0'dan başlayan bir sayaç oluşturun ve dizenin üzerinden bir kez geçin. Geçerli karakter, aradığınız karaktere her eşit olduğunda 1 ekleyin. Döngü sona erdiğinde sayaç cevaptır ve işlem O(n) zaman ve O(1) ek bellek gerektirir.

Bir karakteri saymak büyük/küçük harfe duyarlı mıdır?

Bu problemde evet: B ve b farklı karakterlerdir, bu nedenle Banana içinde b yoktur. Bunun yerine büyük/küçük harf duyarsız bir sayım gerekiyorsa, karşılaştırmadan önce hem dizeyi hem de harfi küçük harfe dönüştür.

Bir mülakatta yerleşik bir sayım işlevi kullanabilir miyim?

Genellikle evet, maliyetini açıklayabildiğin sürece. Python'daki str.count ve benzeri işlevler dizenin tamamını yine de okur, dolayısıyla O(n) karmaşıklığındadır. Birçok mülakatçı daha sonra döngüyü kendin yazmanı ister; bu yüzden bunu göstermeye hazır ol.

Her karakteri aynı anda nasıl sayarsın?

Bir geçiş yapın ve her karakterin sayısını bir karma eşlemede 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 bu daha iyi bir yaklaşımdır.

Python

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

Test durumları

Durum 1

Durum 2

Girdi

s = "Mississippi"
c = "s"

Beklenen