Son indekse ulaşılabilir mi
Görev tanımı
Problem
Negatif olmayan tam sayılardan oluşan bir listenin 0. indeksinden başlıyorsun. Her indeksteki değer oradan yapabileceğin en uzun sıçrayıştır; yani i indeksinden i + 1 ile i + jumps[i] arasındaki herhangi bir indekse inebilirsin. Son indekse ulaşabiliyorsan True, değilse False döndür.
Örnekler
Input: jumps = [2, 3, 1, 1, 4]
Output: True
Neden: 1 adım sıçrayıp 1. indekse, sonra 3 adımla sona
Input: jumps = [3, 2, 1, 0, 4]
Output: False
Neden: her rota 3. indekse iniyor, onun 0 değeri de hiçbir yere götürmüyor
Input: jumps = [0]
Output: True
Neden: edge case: zaten son indekste duruyorsun
İpuçları
0 / 3
Her sıçrayış dizisini denemek patlar. Bunun yerine daha küçük bir soru sor: ulaşabildiğin indekslerden herhangi birini kullanarak sağa en fazla ne kadar gidebilirsin?
Soldan sağa tara ve şimdiye kadar ulaşılabilen en uzak indeks olan reach'i tut. reach'e kadarki her indeks ulaşılabilirdir, yani her biri onu i + jumps[i]'ye uzatabilir.
Tarama reach'ten büyük bir indekse varırsa geçemeyeceğin bir boşluk vardır ve cevap False. Tarama biterse son indeks ulaşılabilir mesafedeydi.
- Hedef zaman
- O(n)
- Hedef alan
- O(1)
Kısıtlar
- the values are non-negative integers
Çözüm
Ulaşılabilen indeksler her zaman 0'dan başlayan kesintisiz tek bir blok oluşturur, çünkü i indeksine inebiliyorsan tam sıçrayışından önceki herhangi bir yerde de durabilirsin. Yani bütün durum tek bir sayıdır: o bloğun sağ kenarı. Soldan sağa dolaşırken bloğun içindeki her indeks kenarı daha ileri itebilir; dışındaki ilk indeks de ötesine hiçbir şeyin ulaşılamayacağını kanıtlar, çünkü ulaşılabilen hiçbir indeks yeterince uzağa sıçramadı. Greedy (açgözlü) seçimin güvenli olmasının sebebi bu: en uzak erişimi tutmak oraya hangi rotanın götürdüğüne dair hiçbir bilgi kaybettirmez. Tek geçiş, O(n) zaman ve O(1) alan.
def can_reach_end(jumps):
reach = 0 # farthest index reachable so far
for i, step in enumerate(jumps):
if i > reach: # a gap nobody can jump over
return False
reach = max(reach, i + step)
return True
print(can_reach_end([2, 3, 1, 1, 4])) # -> True
print(can_reach_end([3, 2, 1, 0, 4])) # -> False
print(can_reach_end([0])) # -> TrueKodda değil de fikirde mi takıldın? Jump Game bunu anlatıyor.