Max Consecutive Ones
Her değeri 0 veya 1 olan bir nums dizisi verilir. Bir seri, aralarında 0 olmadan yan yana duran 1’lerden oluşur. En uzun serinin uzunluğunu döndür; dizide hiç 1 yoksa 0 döndür.
Fonksiyon
- 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 × 104- Her
nums[i],0veya1değeridir.
Örnekler
- Girdi
- nums = [1, 1, 0, 1, 1, 1, 0, 1]
- Çıktı
- 3
- Açıklama
- 1'ler üç dizi oluşturur:
0ile1arasındaki indeksler (uzunluk 2),3ile5arasındaki indeksler (uzunluk 3) ve tek başına7indeksi (uzunluk 1). En uzun dizinin uzunluğu3'tür.
- Girdi
- nums = [0, 1, 0, 1, 1]
- Çıktı
- 2
- Açıklama
1indeksindeki tekli 1,3ve4indekslerindeki çifte yenilir, bu yüzden cevap2olur.
- Girdi
- nums = [0, 0, 0]
- Çıktı
- 0
- Açıklama
- Hiçbir yerde 1 yok, dolayısıyla 1 dizisi yok ve yanıt
0.
Ek soru
En fazla k tane sıfırı bire çevirebilseydin ne olurdu? En uzun ardışık dizi ne kadar uzayabilir ve bunu yine de tek geçişte bulabilir misin?
İpuçları
Tek tek açın. Her biri biraz daha fazlasını gösterir.
Bir 1 dizisi, bir
0göründüğü anda sona erer. Daha önce geçtiğin değerlerle ilgili neyi hatırlaman gerekiyor?Yalnızca mevcut indekste sona eren dizinin uzunluğu önemlidir. 1, diziyi bir uzatır; 0 ise uzunluğu sıfırlar.
Diziyi iki sayıyla bir kez dolaş: mevcut serinin uzunluğu ve şimdiye kadarki en iyi uzunluk. Her 1'den sonra mevcut seriyi uzat ve en iyisiyle karşılaştır; her 0'dan sonra mevcut seriyi sıfırla.
Çözüm
Bir dizi, 0 göründüğü anda sona erer; bu nedenle her indiste yalnızca orada sona eren dizinin uzunluğunu bilmen gerekir. 1'de artan ve 0'da sıfırlanan tek bir sayaç, tek geçişte en uzun diziyi bulur.
Her indeksten ileri doğru say
Doğru, ama en büyük testlerde bitmiyor
Sezgi
Her indeksi başlangıç olarak deneyin ve 1'leri gördüğünüz sürece ileri doğru ilerleyin; adım sayısı, orada başlayan dizinin uzunluğudur. En uzun dizi bu indekslerden birinde başlar, dolayısıyla en büyük sayı cevaptır.
Yürüyüşler çakışır. n tane 1 içeren bir dizide yaklaşık n² / 2 adım atarlar; n = 2 × 10^4 için 2 × 10^8.
Algoritma
best = 0olarak ayarla.- Her
startindeksi içinlength = 0olarak ayarla. start + lengthdizinin içindeyken venums[start + length]değeri1ikenlengthdeğerine 1 ekle.bestvelengthdeğerlerinden büyük olanı sakla.bestdeğ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Çalışan bir sayaçla tek geçiş
Sezgi
Üzerinde bulunduğun indeksle biten 1'ler dizisinin uzunluğu olan current değerini tut. Bir 1 bu diziyi bir artırır; bir 0 ise diziyi bitirir, dolayısıyla current değeri 0'a düşer. Her dizi, current değerinin tam uzunluğuna eşit olduğu son indeksinde ölçülür; bu nedenle current değerinin ulaştığı en büyük değer yanıttı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 en büyük değer 3'tür.
Algoritma
best = 0vecurrent = 0değerlerini ayarla.numsiçindeki her değer için: değer1isecurrentdeğerine 1 ekle vebestilecurrentdeğerlerinden büyük olanı koru.- Değer
0isecurrent = 0olarak ayarla. bestdeğ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
bestdeğerini yalnızca bir0ile karşılaştığında güncellemek.[0, 1, 1]örneğindeki gibi sona ulaşan bir seri hiçbir zaman kaydedilmez. Her1'den sonra güncelle veya döngüden sonra bir kez daha karşılaştır.- Bir
0ile karşılaştığındacurrentdeğerini sıfırlamamak. Ayrı seriler birbirine eklenir ve[1, 1, 0, 1, 1]sonucu4döndürür. bestdeğerini1veyanums[0]olarak başlatmak.[0, 0, 0]sonucu0döndürmelidir.- Dizilerin 1'den başladığı Lua ve R dillerinde, ileri yöndeki dolaşımı
≤ nyerine< nile sınırlamak. Son değer hiçbir zaman okunmaz, bu nedenle[0, 1]sonucu0döndürür.
Sıkça sorulan sorular3
Max Consecutive Ones algoritmasının zaman karmaşıklığı nedir?
Tek geçişli çözüm O(n) zamanda çalışır, çünkü her değeri bir kez okur ve O(1) ek alan kullanır: mevcut ardışık dizinin uzunluğu için bir sayaç ve en iyi dizi için bir sayaç. Sayımı her indekste 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 dizinin uzunluğunu tutar. Oradaki değer 0 olduğunda, orada hiçbir 1 dizisi sona ermez; bu nedenle uzunluk 0 olur. Sonraki 1, değeri 1'e yükseltir; bu da yeni dizinin uzunluğudur.
En Fazla Ardışık Birler problemi kayan pencere problemi midir?
Bunu tek bir pencere olarak düşünebilirsin: pencere mevcut diziyi tutar, sağ kenarı her değerde ilerler ve bir 0 sol kenarı onun ötesine taşır. Pencere adım adım asla küçülmez, bu yüzden iki kenarın yerini tek bir sayaç alır.
Benzer problemler
Aynı fikirleri kullanan problemler. İki üçünü çözmek bir kalıbı kalıcı hale getirir.
def findMaxConsecutiveOnes(nums):
# Kodu buraya yazınTest #1
Test #2
Test #3
Argüman
nums = [1, 1, 0, 1, 1, 1, 0, 1]
Beklenen Çıktı
3