Count Even Numbers

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

Evet. Sıfırın 2 'ye bölümü kalansız 0 olduğundan, çift sayı tanımına uyar. Ayrıca, çift sayıların yer aldığı tek sayılar -1 ve 1 arasındadır.

Q: Dizideki çift sayıların sayılmasının zaman karmaşıklığı nedir?

Sayaçla yapılan tek bir 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.

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

+10

Boş olmayan bir tam sayı listesi olan nums verildiğinde, değerlerinden kaçının çift olduğunu döndür. Bir sayı, 2'ye 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ın 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ür; 3 ve 5 bölünmez. Cevap 3.

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 hepsi tektir, bu yüzden cevap 0.

Ek soru

Şu soruyla sık sık karşılaşırsın: l indeksi ile r indeksi arasında kaç tane çift değer var? nums üzerinde tek 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

Her değeri bir kez kontrol edin ve 2'ye bölündüğünde kalanı 0 olanları sayın. Tek olup olmadığını 1 ile test etmek yerine kalanı 0 ile karşılaştırmak, negatif sayılarda da doğru sonucu verir.

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

Sezgi

Çift değerleri filtreyle seç, ardından sonucun uzunluğunu döndür. [3, 8, 12, 5, 6] için filtrelenmiş liste [8, 12, 6] olur; dolayısıyla cevap 3'tür.

Zaman karmaşıklığı O(n)'dir, ancak yeni liste, uzunluğunu yalnızca bir kez okumak için en fazla 5000 değerlik bellek kullanır.

Algoritma

nums içinde 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 yerine bir sayaç tutun ve x % 2 == 0 koşulunu sağlayan her değer için 1 ekleyin. Bir çift sayı, işareti ne olursa olsun 0 kalanını verir; bu nedenle bu koşul her dilde -4 ve 0 için sağlanır. x % 2 == 1 şeklinde yazılan tek sayı koşulu ise bunu yapmaz: C, Java, JavaScript ve C benzeri dillerin çoğunda kalan, sayının işaretini alır; bu nedenle -3 % 2 sonucu -1 olur.

Tek geçiş ve tek tamsayı: O(n) zaman, O(1) alan.

Algoritma

count değerini 0 olarak ayarla.
nums içindeki her x değeri üzerinde döngü oluştur.
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

Tek değerleri x % 2 == 1 ile sayıp uzunluktan çıkarmak. C benzeri dillerde -3 % 2 sonucu -1 olur; bu nedenle [-3], 0 yerine 1 döndürür.
0 değerini ne çift ne de tek olarak değerlendirmek. 0 = 2 × 0 olduğundan [0], 1 döndürür.
Bit testini x & 1 == 0 şeklinde yazmak. C, C++ ve JavaScript'te ==, & işleminden daha sıkı bağlanır; dolayısıyla bu ifade x & (1 == 0) anlamına gelir ve sonucu her zaman 0 olduğundan hiçbir şeyi saymaz. (x & 1) == 0 şeklinde yazın.

Sıkça sorulan sorular3

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

Bölme işleminden sonra kalanının sıfır olup olmadığını test edin: x % 2 == 0. -3 % 2 işleminin -1 olduğu dillerde bile pozitif sayılar, negatif sayılar ve sıfır için çalışır. En düşük biti (x & 1) == 0 ile de kontrol edebilirsiniz.

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

Evet. Sıfırın 2'ye bölümü kalansız 0 olduğundan, çift sayı tanımına uyar. Ayrıca, çift sayıların yer aldığı tek sayılar -1 ve 1 arasındadır.

Dizideki çift sayıların sayılmasının zaman karmaşıklığı nedir?

Sayaçla yapılan tek bir 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.

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

Test #1

Test #2

Test #3

Argüman

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

Beklenen Çıktı