Pozitif gidiş için en küçük başlangıç
Görev tanımı
Problem
Başlangıç değeri olarak pozitif bir tam sayı seçiyorsun, sonra bir listenin sayılarını soldan sağa birer birer ona ekliyorsun. Kümülatif toplamın hiçbir adımda 1'in altına düşmediği en küçük başlangıç değerini döndür.
Örnekler
Input: nums = [-3, 2, -3, 4, 2]
Output: 5
Neden: 5 sırayla 2, 4, 1, 5, 7 olur; 4 ise üçüncü adımdan sonra 0'a ulaşırdı
Input: nums = [1, 2]
Output: 1
Neden: toplam yalnız büyüyor, bu yüzden en küçük pozitif başlangıç işe yarar
Input: nums = [1, -2, -3]
Output: 5
Neden: edge case: en düşük nokta en sonda geliyor
İpuçları
0 / 3
Başlangıç değerlerini tek tek denemek işe yarar ama her seferinde bütün dolaşmayı tekrarlar. Listeyle ilgili hangi tek bilgi cevaba karar verir?
Başlangıç her kümülatif toplama eklenir, bu yüzden yalnız en düşük kümülatif toplam önemli. En az 1'e çıkarılması gerekir.
Listeyi bir kez dolaş; kümülatif toplamı ve ulaştığı en düşük değeri tut, herhangi bir adımdan önceki durum da sayılsın diye 0'dan başla. Cevap 1 eksi bu en düşük değer.
- Hedef zaman
- O(n)
- Hedef alan
- O(1)
Çözüm
Bu, gas station dersindeki yakıt deposu: kümülatif toplam depodur, başlangıç değeri de yanında getirdiğin yakıttır. Bir s başlangıç değeri eklemek her kümülatif toplamı tam olarak s kadar yükseltir; yani dolaşma tam olarak s artı en düşük kümülatif toplam en az 1 olduğunda 1'de ya da üstünde kalır. Tek bir geçiş bu en düşük toplamı bulur. Minimumu 0'dan başlatmak, kümülatif toplamı hiç negatife düşmeyen listeleri kapsar; orada cevap en küçük pozitif başlangıç olan 1'dir. Zaman O(n), alan O(1).
def smallest_start(nums):
total = lowest = 0
for x in nums:
total += x
lowest = min(lowest, total) # the deepest dip of the running sum
return 1 - lowest # lowest <= 0, so this is at least 1
print(smallest_start([-3, 2, -3, 4, 2])) # -> 5
print(smallest_start([1, 2])) # -> 1
print(smallest_start([1, -2, -3])) # -> 5Kodda değil de fikirde mi takıldın? Gas Station bunu anlatıyor.