Count Even Numbers

Q: Sıfır çift sayı mıdır?

Evet. Sıfırın 2 'ye bölümü, kalan olmadan 0 eder; bu nedenle çift sayının tanımına uyar. Ayrıca tek sayılar olan -1 ile 1 arasında, tam da bir çift sayının olması gereken yerde bulunur.

Q: Bir dizideki çift sayıların sayısını bulmanın zaman karmaşıklığı nedir?

Bir sayaçla tek geçiş O(n) zaman ve O(1) ek alan alır. Her değerin kontrol edilmesi gerekir; bu nedenle hiçbir yöntem O(n) ’den daha hızlı değildir. Önce filtrelenmiş bir liste oluşturmak aynı sayıyı verir, ancak O(n) ek bellek kullanır.

BaşlangıçDiziler ve dizgiler Matematik ve simülasyon

+10

Boş olmayan bir tam sayı listesi olan nums veriliyor. Değerlerinden kaç tanesinin çift olduğunu döndürün. Bir sayı, 2 ile bölündüğünde kalan bırakmıyorsa çifttir; buna 0 ve -4 gibi negatif sayılar da dahildir.

Fonksiyon

countEvens(nums: integer-array) → integer

numsinteger-array: kontrol edilecek tam sayılar listesi
Döndürürinteger: nums içindeki çift değerlerin sayısı

Kısıtlar

1 ≤ nums.length ≤ 5000
-10⁹ ≤ nums[i] ≤ 10⁹

Örnekler

Girdi: nums = [3, 8, 12, 5, 6]
Çıktı: 3
Açıklama: 8, 12 ve 6, 2'ye kalansız bölünürken 3 ve 5 kalan bırakır. Bu da 3 değerin çift olduğu anlamına gelir.

Girdi: nums = [-4, -3, 0, 7]
Çıktı: 2
Açıklama: -4 = 2 × (-2) ve 0 = 2 × 0, dolayısıyla ikisi de çifttir. -3 ve 7 tektir ve sayı 2'dir.

Girdi: nums = [1, 9, 15]
Çıktı: 0
Açıklama: 1, 9 ve 15 sayıların tümü tektir, bu yüzden hiçbir değer sayılmaz ve cevap 0'dır.

Gönderirken +12 gizli test

Ek soru

Şu biçimde birçok soru alıyorsun: l dizini ile r dizini arasında kaç çift değer bulunuyor? nums üzerinde bir geçiş yaptıktan sonra her soruyu O(1) zamanda yanıtlayabilir misin?

İpuçları

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

3 ipucundan 0 açıldı

Çözüm

Döngü tek satırdır; çözümlerin bozulduğu yer çiftlik testidir. Birçok dilde negatif bir sayının kalanı negatiftir, bu yüzden -3 % 2 sonucu -1 olur. x % 2 == 0 testini kullanmak, her dilde her işaret için doğrudur ve artan bir sayaç ek bellek gerektirmez.

Çift değerleri topla, ardından onları say

Sezgi

Görevi iki adıma böl: çift değerleri seç, sonra seçtiklerini say. x değeri, x % 2 == 0 olduğunda çifttir. Çoğu dilde yeni listeyi tek satırda oluşturan bir filtreleme işlevi vardır ve bu listenin uzunluğu yanıttır. [3, 8, 12, 5, 6] için filtrelenmiş liste [8, 12, 6] olur; dolayısıyla yanıt 3 olur.

Bu doğrudur ve okunması kolaydır, ancak yeni liste O(n) bellek kullanır; burada en fazla 5000 değer için, yalnızca uzunluğunu bir kez okumak amacıyla. Değerlerin kendileri bir daha kullanılmaz.

Algoritma

nums içindeki x % 2 == 0 koşulunu sağlayan her x'i içeren yeni bir liste oluştur.
Bu listenin uzunluğunu döndür.

def countEvens(nums):
    evens = [x for x in nums if x % 2 == 0]
    return len(evens)

Artan bir sayaçla say

Sezgi

Liste tutmak yerine bir sayaç kullan. Sayacı 0 ile başlat, her değere bir kez bak ve değer çiftse 1 ekle. Her değer tam olarak bir kez kontrol edildiği için sayı kesin olur ve kullanılan tek bellek bir tamsayıdır.

Testi dikkatli yapmak gerekir. C, C++, Java, C#, JavaScript, Go, Rust, Swift ve PHP'de kalan sayının işaretini alır; bu nedenle -3 % 2 sonucu 1 değil, -1 olur. Çift sayılar işaretleri ne olursa olsun 0 kalanını verir; dolayısıyla x % 2 == 0 her zaman doğrudur, oysa x % 2 == 1 şeklinde yazılan tek sayı testi negatif tek sayıların tümünü kaçırır. [-4, -3, 0, 7] için kalanlar sırasıyla 0, -1, 0 ve 1 olur; bu nedenle sayaç 2 değerine ulaşır.

Sıfır da sayılır: 0 % 2 sonucu 0 olduğundan 0 çifttir.

Algoritma

count değerini 0 olarak ayarla.
nums içindeki her x değeri üzerinde döngü yap.
x % 2 == 0 ise count değerine 1 ekle.
Döngüden sonra count değerini döndür.

def countEvens(nums):
    count = 0
    for x in nums:
        if x % 2 == 0:  # 0 also works for negatives, where the remainder can be -1
            count += 1
    return count

Tuzaklar ve uç durumlar

Buradaki hatalar negatif sayılardan ve sıfırdan kaynaklanıyor.

Tek değerleri x % 2 == 1 ile sayıp uzunluktan çıkarmak. C benzeri dillerde -3 % 2 sonucu -1 olur; bu nedenle -3 hiçbir zaman tek olarak sayılmaz ve çift olarak sayılır.
0 değerini ne çift ne de tek kabul etmek. 0 = 2 × 0, dolayısıyla çift sayıdır ve [0] sonucu 1 olur.
Bit testini x & 1 == 0 şeklinde yazmak. C, C++ ve JavaScript'te ==, & işlecinden daha yüksek önceliğe sahiptir; bu nedenle ifade x & (1 == 0) anlamına gelir, bu da her zaman 0 sonucunu verir ve hiçbir şeyi saymaz. (x & 1) == 0 şeklinde yazın.
Dizini 0 tabanlı bir dilde döngüyü 1 dizininden başlatmak, ilk değerin atlanmasına neden olur; ya da ilk değerin 1 dizininde bulunduğu Lua ve R'de 0 dizininden başlatmak.

Sıkça sorulan sorular4

Kodda bir sayının çift olup olmadığını nasıl kontrol edersiniz?

2’ye bölündükten sonra kalanın sıfır olup olmadığını test et: x % 2 == 0. Bu, tüm yaygın dillerde pozitif sayılar, negatif sayılar ve sıfır için çalışır. Başka bir yol, çift sayıların 0 bitiyle bittiği için en düşük biti (x & 1) == 0 ile kontrol etmektir.

Sıfır çift sayı mıdır?

Evet. Sıfırın 2'ye bölümü, kalan olmadan 0 eder; bu nedenle çift sayının tanımına uyar. Ayrıca tek sayılar olan -1 ile 1 arasında, tam da bir çift sayının olması gereken yerde bulunur.

Negatif sayılar için x % 2 == 1 neden başarısız oluyor?

C, C++, Java, C#, JavaScript, Go, Rust, Swift ve PHP'de kalan, bölünen sayının işaretini alır; bu nedenle -3 % 2 sonucu -1 olur. Python, Ruby, Dart, Lua ve R ise bunun yerine 1 döndürür. Tek sayılar için x % 2 != 0, çift sayılar için x % 2 == 0 koşulunu sınamak hepsinde aynı sonucu verir.

Bir dizideki çift sayıların sayısını bulmanın zaman karmaşıklığı nedir?

Bir sayaçla tek geçiş O(n) zaman ve O(1) ek alan alır. Her değerin kontrol edilmesi gerekir; bu nedenle hiçbir yöntem O(n)’den daha hızlı değildir. Önce filtrelenmiş bir liste oluşturmak aynı sayıyı verir, ancak O(n) ek bellek kullanır.

Python

def countEvens(nums):
    # Kodu buraya yazın

Test durumları

Durum 1

Durum 2

Durum 3

Girdi

nums = [3, 8, 12, 5, 6]

Beklenen