Count Vowels

Q: Sesli harfleri saymanın zaman karmaşıklığı nedir?

O(n) 'dir; burada n dizenin uzunluğudur, çünkü her karakter bir kez kontrol edilir ve her kontrol en fazla beş harfle karşılaştırma yapar. Ek alan O(1) 'dir: bir sayaç ve sabit sesli harf kümesi.

Q: Bu problemde y bir sesli harf mi?

Hayır. İngilizce yazımında y bazen rhythm sözcüğünde olduğu gibi bir ünlü görevi görür, ancak programlama problemleri ünlüleri neredeyse her zaman a , e , i , o ve u olarak tanımlar; bu problem de öyle yapıyor. Bir problem y harfini içeriyorsa, kontrol ettiğin harflere onu da ekle.

BaşlangıçDiziler ve dizgiler

+10

İngilizce harflerden oluşan bir s dizeniz var. Karakterlerinden kaçının ünlü olduğunu sayın ve bu sayıyı döndürün. Ünlüler, küçük veya büyük harfli a, e, i, o ve u harfleridir. y harfi sayılmaz.

Fonksiyon

countVowels(s: string) → integer

sstring: taranacak İngilizce harf dizisi
Döndürürinteger: s içindeki sesli harflerin sayısı; büyük ve küçük harfler birlikte

Kısıtlar

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

Örnekler

Girdi: s = "Interview"
Çıktı: 4
Açıklama: Sesli harfler I, e, i ve e harfleridir. Büyük I, küçük harfle aynı şekilde sayılır; bu nedenle cevap 4'tür.

Girdi: s = "rhythm"
Çıktı: 0
Açıklama: rhythm içinde a, e, i, o veya u yoktur. İçindeki y harfi sesli harf gibi okunur, ancak listede yer almadığı için cevap 0'dır.

Gönderirken +18 gizli test

Ek soru

Stringi yalnızca bir kez okuyarak beş sesli harfin her birinin kaç kez geçtiğini döndürebilir misin?

İpuçları

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

3 ipucundan 0 açıldı

Çözüm

Sayma, bir sayaçla dizenin üzerinden tek geçişte yapılır. Verilecek tek kararlar, bir karakterin sesli harf olup olmadığını nasıl test edeceğin ve büyük harflerle ne yapacağındır. Her karakteri küçük harfe dönüştür ve beş sesli harfle karşılaştır; böylece her karakter sabit miktarda işlem gerektirir.

Her ünlüyü kendi geçişinde say

Sezgi

Soruyu on daha küçük soruya böl: kaç tane a var, kaç tane e var ve böylece U'ya kadar devam et. Bunların her biri basit bir sayımdır. Dizgeyi dolaş ve aradığın harfe eşit olan her karakter için 1 ekle, ardından bu on sayımı topla.

s içindeki her sesli harf, aeiouAEIOU içindeki on harften tam olarak birine eşittir; bu nedenle tam olarak bir kez sayılır ve hiçbir ünsüz bunlardan herhangi birine eşit değildir. Interview için e taraması 2, i taraması 1, I taraması 1 bulur ve diğer yedi tarama hiçbir şey bulmaz: toplam 4.

Dizge on kez okunur; yaklaşık 10n karşılaştırma yapılır. Bu hâlâ O(n) karmaşıklığındadır, çünkü on sabit bir sayıdır; ancak 5 × 10^4 karakter için, her karakteri bir kez okuyacak tek bir geçişe kıyasla 5 × 10^5 karşılaştırma anlamına gelir.

Algoritma

total = 0 olarak ayarla.
aeiouAEIOU içindeki on harfi teker teker al.
Her harf için dizenin tamamını tara ve bir karakter ona eşit olduğunda total değerini 1 artır.
On geçişten sonra total değerini döndür.

def countVowels(s):
    total = 0
    for vowel in "aeiouAEIOU":
        total += s.count(vowel)  # one pass over s for this letter
    return total

Bir küçük harf kontrolüyle tek geçiş

Sezgi

Döngülerin yönünü değiştir. Dizeyi bir kez oku ve her karakter için şu soruyu sor: Bu bir sesli harf mi? Tek bir denetimle hem büyük hem küçük harfleri kapsamak için önce karakteri küçük harfe dönüştür. I, i olur ve E, e olur; ünsüzler ünsüz olarak kalır, böylece yalnızca a, e, i, o ve u harfleriyle karşılaştırma yaparsın.

Denetim sabit zaman alır: beş harf üzerinde bir switch, bir kümede arama veya beş harfli aeiou dizesinde arama. Interview üzerinde ilerlerken sayaç I, e, i ve e harflerinde artar ve 4'te biter.

Her karakter bir kez okunduğundan, zaman karmaşıklığı O(n)'dir. Bellek, sayaç ve beş sesli harften oluşur; alan karmaşıklığı O(1)'dir.

Algoritma

count = 0 olarak ayarla.
Dizgede her seferinde bir karakter ilerle.
Karakteri küçük harfe dönüştür.
Karakter a, e, i, o veya u ise count değerini 1 artır.
count değerini döndür.

def countVowels(s):
    vowels = set("aeiou")
    count = 0
    for ch in s:
        if ch.lower() in vowels:
            count += 1
    return count

Tuzaklar ve uç durumlar

Görev birkaç satıra sığar ve hatalar, ilk kontrolün gözden kaçırdığı durumlardan kaynaklanır.

Yalnızca küçük harfleri kontrol etmek. Yalnızca aeiou ile karşılaştırmak, Interview içindeki büyük I harfini gözden kaçırır ve 3 döndürür. Karakteri küçük harfe dönüştürün ya da on harfin tümünü listeleyin.
y harfini saymak. Bu problemde y hiçbir zaman bir sesli harf değildir; bu yüzden rhythm 0 verir.
0 indeksini eşleşme yok olarak değerlendirmek. "aeiou".indexOf('a') sonucu 0'dır ve bu bir eşleşmedir. -1 olup olmadığını kontrol edin ya da PHP'de strpos değerini false ile !== kullanarak karşılaştırın; çünkü orada 0 == false olur.
C'de döngü koşulunda strlen(s) çağırmak. Bu, her yinelemede dizenin tamamını tarar; dolayısıyla 5 × 10^4 karakter yaklaşık 2.5 × 10^9 adıma mal olur. '\0' sonlandırıcısında durun ya da uzunluğu döngüden önce bir kez hesaplayın.

Sıkça sorulan sorular4

Bir string içindeki sesli harfleri nasıl sayarsın?

Bir sayaçla dizenin üzerinde bir kez ilerleyin. Her karakteri küçük harfe dönüştürün ve a, e, i, o veya u olup olmadığını kontrol edin; öyleyse 1 ekleyin. Döngü sona erdiğinde sayaç yanıtı tutar.

Sesli harfleri saymanın zaman karmaşıklığı nedir?

O(n)'dir; burada n dizenin uzunluğudur, çünkü her karakter bir kez kontrol edilir ve her kontrol en fazla beş harfle karşılaştırma yapar. Ek alan O(1)'dir: bir sayaç ve sabit sesli harf kümesi.

Bu problemde y bir sesli harf mi?

Hayır. İngilizce yazımında y bazen rhythm sözcüğünde olduğu gibi bir ünlü görevi görür, ancak programlama problemleri ünlüleri neredeyse her zaman a, e, i, o ve u olarak tanımlar; bu problem de öyle yapıyor. Bir problem y harfini içeriyorsa, kontrol ettiğin harflere onu da ekle.

Sesli harf kontrolünde bir küme mi, switch mi, yoksa dizgede arama mı kullanılmalı?

Beş harfle, üçünün de karakter başına çalışma süresi sabittir ve aralarındaki hız farkı önemsenmeyecek kadar küçüktür. Kullandığın dilde en okunaklı olanı seç: C, C++ veya Go'da bir switch, Python, JavaScript veya Ruby'de bir küme ya da dizge araması.

Python

def countVowels(s):
    # Kodu buraya yazın

Test durumları

Durum 1

Durum 2

Girdi

s = "Interview"

Beklenen