Max Consecutive Ones

Q: En Fazla Ardışık 1'lerin zaman karmaşıklığı nedir?

Tek geçişli çözüm O(n) zamanda çalışır, çünkü her değeri tam olarak bir kez okur. O(1) ek alan kullanır: geçerli seri için bir sayaç ve en iyi seri için bir sayaç. Her indekste sayımı yeniden başlatmak, tamamı 1'lerden oluşan bir dizide O(n²) zaman alır.

Q: Sayaç neden 1 yerine 0’a sıfırlanıyor?

Sayaç, geçerli dizinde sona eren 1’lerden oluşan dizinin uzunluğunu tutar. Geçerli değer 0 olduğunda, burada hiçbir 1 dizisi sona ermez; dolayısıyla uzunluğu 0 olur. Sonraki 1 ise değeri 1 ’e yükseltir; bu da yeni bir dizinin doğru uzunluğudur.

Q: Bu bir kayan pencere problemi mi?

Bunu tek bir pencere olarak düşünebilirsin: pencere mevcut diziyi tutar, her değerde sağ kenar ilerler ve bir 0 sol kenarı onun ötesine taşır. Burada pencerenin adım adım küçülmesi gerekmez, bu yüzden tek bir sayaç iki kenarın yerini alır. Pencere yaklaşımı, en fazla k tane sıfırı bire çevirebildiğin daha zor sürümde işe yarar.

Q: Bir tane 0'ı çevirebiliyorsan art arda gelen 1'leri nasıl sayarsın?

İki sayaç tut: burada biten, hiç bit değiştirilmemiş dizinin uzunluğu ve bir bit değiştirme hakkı zaten kullanılmış dizinin uzunluğu. 1 geldiğinde ikisi de bir artar. 0 geldiğinde, bit değiştirilmiş sayaç düz sayacın bir fazlası olur ve düz sayaç 0'a sıfırlanır. Yanıt, tek bir geçişte gördüğün en büyük bit değiştirilmiş sayaç değeridir.

BaşlangıçDiziler ve dizgiler

+10

Her değeri 0 veya 1 olan bir nums dizisi alırsın. Bir seri, aralarında 0 olmadan yan yana duran 1'lerden oluşan bir dizidir. En uzun serinin uzunluğunu döndür; dizide hiç 1 yoksa 0 döndür.

Fonksiyon

findMaxConsecutiveOnes(nums: integer-array) → integer

numsinteger-array: 0'lardan ve 1'lerden oluşan bir dizi
Döndürürinteger: ardışık 1'lerden oluşan en uzun dizinin uzunluğu

Kısıtlar

1 ≤ nums.length ≤ 2 × 10⁴
Her nums[i] değeri 0 veya 1'dir.

Örnekler

Girdi: nums = [1, 1, 0, 1, 1, 1, 0, 1]
Çıktı: 3
Açıklama: 1'ler üç ardışık dizi oluşturur: 0 ile 1 arasındaki indeksler (uzunluk 2), 3 ile 5 arasındaki indeksler (uzunluk 3) ve tek başına 7 indeksi (uzunluk 1). En uzun dizinin uzunluğu 3'tür.

Girdi: nums = [0, 1, 0, 1, 1]
Çıktı: 2
Açıklama: Diziler, 1 indeksindeki tek 1 ve 3 ile 4 indekslerindeki çifttir. 2 uzunluğuyla çift kazanır.

Girdi: nums = [0, 0, 0]
Çıktı: 0
Açıklama: Hiçbir yerde 1 yok, dolayısıyla bir seri yok ve cevap 0.

Gönderirken +14 gizli test

Ek soru

Peki, en fazla k tane 0'ı 1'e çevirebilseydin ne olurdu? En uzun 1 dizisi ne kadar uzayabilir ve yine de bunu tek geçişte bulabilir misin?

İpuçları

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

3 ipucundan 0 açıldı

Çözüm

Bir çalışma, 0 göründüğü anda sona erer; bu nedenle herhangi bir indekste bilmeniz gereken tek şey, orada sona eren çalışmanın uzunluğudur. Her indekste baştan saymak, aynı işi tekrar tekrar yapar. 1 geldiğinde artan ve 0 geldiğinde sıfırlanan tek bir sayaç, soruyu tek geçişte yanıtlar.

Her indeksten ileri doğru say

Doğru, ama en büyük testlerde bitmiyor

Sezgi

Her çalışma bir yerden başlar. Bu yüzden başlangıç olarak her indeksi deneyin ve 1’leri görmeye devam ettiğiniz sürece ileri doğru ilerleyin; adım sayısı, orada başlayan dizinin uzunluğudur. Tüm başlangıçlar arasındaki en büyük sayı yanıttır. [1, 1, 0, 1, 1, 1, 0, 1] için 3 indeksindeki başlangıç, 6 indeksindeki 0 ile karşılaşmadan önce üç tane 1’in üzerinden geçer; bu da 3 sonucunu verir.

Yanıt doğrudur; çünkü en uzun dizi denediğiniz indekslerden birinde başlar ve ilk indeksinden itibaren yapılan ilerleme, dizinin uzunluğunu tam olarak ölçer.

Maliyet, örtüşmelerde gizlidir. n tane 1 içeren bir dizide, 0 indeksindeki başlangıç n adım, sonraki başlangıç n-1 adım ilerler ve bu böyle devam eder; toplamda yaklaşık n² / 2 adım atılır. n = 2 × 10^4 için bu 2 × 10^8 adımdır; yavaş dillerde zaman sınırı için bu çok fazladır.

Algoritma

best = 0 olarak ayarla.
Her start indeksi için length = 0 olarak ayarla.
start + length dizinin içindeyken ve nums[start + length] değeri 1 iken length değerini 1 artır.
best ve length değerlerinden büyük olanı sakla.
best değerini döndür.

def findMaxConsecutiveOnes(nums):
    n = len(nums)
    best = 0
    for start in range(n):
        length = 0
        while start + length < n and nums[start + length] == 1:
            length += 1
        best = max(best, length)
    return best

Geçerli bir sayaçla tek geçiş

Sezgi

Diziyi bir kez dolaş ve bulunduğun indeksin sonunda biten 1 dizisinin uzunluğunu tutmak için current değerini kullan. Bir 1 bu diziyi uzatır, bu yüzden current bir artar. Bir 0 diziyi bitirir, bu yüzden current yeniden 0 değerine düşer. Her 1'den sonra current ile best değerini karşılaştır.

[1, 1, 0, 1, 1, 1, 0, 1] dizisinde current sırasıyla 1, 2, 0, 1, 2, 3, 0, 1 değerlerini alır ve bunların en büyüğü 3 olur. Her dizi, son indeksinde ölçülür; bu noktada current dizinin tam uzunluğuna eşittir. Bu nedenle görülen en iyi değer, en uzun dizinin uzunluğudur.

Her değer bir kez okunur; bu da O(n) zaman demektir ve ihtiyacın olan tüm bellek iki tam sayıdan ibarettir.

Algoritma

best = 0 ve current = 0 değerlerini ayarla.
nums içindeki her değer için: değer 1 ise current değerini 1 artır ve best ile current değerlerinden büyük olanı koru.
Değer 0 ise current = 0 olarak ayarla.
best değerini döndür.

def findMaxConsecutiveOnes(nums):
    best = 0
    current = 0
    for x in nums:
        if x == 1:
            current += 1
            best = max(best, current)
        else:
            # A 0 breaks the run.
            current = 0
    return best

Tuzaklar ve uç durumlar

Tek geçişli sürüm kısadır; bu nedenle hatalar, yanıtı nerede güncellediğinizden kaynaklanır.

best değerini yalnızca bir 0 ile karşılaştığınızda güncellemek. Dizinin sonuna ulaşan bir dizi, [0, 1, 1] örneğinde olduğu gibi, hiçbir zaman kaydedilmez. Her 1'den sonra güncelleyin veya döngüden sonra bir kez daha karşılaştırın.
Bir 0 ile karşılaştığınızda current değerini sıfırlamayı unutmak; bu, ayrı dizilerdeki 1 değerlerini toplar ve [1, 1, 0, 1, 1] için 4 döndürür.
best değerini 1 veya nums[0] olarak başlatmak. Yalnızca 0 değerlerinden oluşan bir dizi 0 döndürmelidir.
Lua ve R'de dizinin indeksi 1'den başlar; bu nedenle ileri yöndeki geçişte < n yerine start + length ≤ n denetlenir.

Sıkça sorulan sorular4

En Fazla Ardışık 1'lerin zaman karmaşıklığı nedir?

Tek geçişli çözüm O(n) zamanda çalışır, çünkü her değeri tam olarak bir kez okur. O(1) ek alan kullanır: geçerli seri için bir sayaç ve en iyi seri için bir sayaç. Her indekste sayımı yeniden başlatmak, tamamı 1'lerden oluşan bir dizide O(n²) zaman alır.

Sayaç neden 1 yerine 0’a sıfırlanıyor?

Sayaç, geçerli dizinde sona eren 1’lerden oluşan dizinin uzunluğunu tutar. Geçerli değer 0 olduğunda, burada hiçbir 1 dizisi sona ermez; dolayısıyla uzunluğu 0 olur. Sonraki 1 ise değeri 1’e yükseltir; bu da yeni bir dizinin doğru uzunluğudur.

Bu bir kayan pencere problemi mi?

Bunu tek bir pencere olarak düşünebilirsin: pencere mevcut diziyi tutar, her değerde sağ kenar ilerler ve bir 0 sol kenarı onun ötesine taşır. Burada pencerenin adım adım küçülmesi gerekmez, bu yüzden tek bir sayaç iki kenarın yerini alır. Pencere yaklaşımı, en fazla k tane sıfırı bire çevirebildiğin daha zor sürümde işe yarar.

Bir tane 0'ı çevirebiliyorsan art arda gelen 1'leri nasıl sayarsın?

İki sayaç tut: burada biten, hiç bit değiştirilmemiş dizinin uzunluğu ve bir bit değiştirme hakkı zaten kullanılmış dizinin uzunluğu. 1 geldiğinde ikisi de bir artar. 0 geldiğinde, bit değiştirilmiş sayaç düz sayacın bir fazlası olur ve düz sayaç 0'a sıfırlanır. Yanıt, tek bir geçişte gördüğün en büyük bit değiştirilmiş sayaç değeridir.

Python

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

Test durumları

Durum 1

Durum 2

Durum 3

Girdi

nums = [1, 1, 0, 1, 1, 1, 0, 1]

Beklenen