Fereastra glisantă sare peste ultima fereastră (off-by-one la range)
O listă cu n elemente are n - k + 1 ferestre de lungime k, deci bucla trebuie să fie range(len(lista) - k + 1). Cu range(len(lista) - k) ultima fereastră nu e verificată, iar rezultatul e greșit fără nicio eroare.
Explicat de Tudor Andrei Dumitrescu, Senior Software Developer, fondatorul Academiei ProgramatorilorActualizat la
Ce înseamnă
La sliding window muți o fereastră de lungime k peste listă și calculezi ceva pentru fiecare poziție (suma, media, maximul). Ferestrele încep la indicii 0, 1, ..., n - k, adică sunt n - k + 1 ferestre. Bucla corectă este for i in range(len(lista) - k + 1).
Cu range(len(lista) - k) bucla se oprește cu o poziție mai devreme. Python nu dă nicio eroare, pentru că toți indicii folosiți sunt valizi; doar că ultima fereastră lipsește. Dacă răspunsul corect era chiar în ultima fereastră, funcția returnează un rezultat greșit, iar când n == k nu verifică nicio fereastră.
Acesta este un bug off-by-one. În „Repară tu” testele folosesc assert, deci vezi AssertionError cu valoarea primită. În propriul cod, testează mereu cazul în care răspunsul e la final și cazul len(lista) == k.
De ce apare: cauzele frecvente
1Numărul de ferestre calculat greșit
def suma_maxima(v, k):
best = 0
for i in range(len(v) - k):
best = max(best, sum(v[i:i + k]))
return bestdef suma_maxima(v, k):
best = sum(v[:k])
for i in range(1, len(v) - k + 1):
best = max(best, sum(v[i:i + k]))
return bestUltima fereastră începe la len(v) - k, iar range exclude capătul, deci limita trebuie să fie len(v) - k + 1.
2Pornești maximul de la 0
best = 0
for i in range(len(v) - k + 1):
best = max(best, sum(v[i:i + k]))best = sum(v[:k])
for i in range(1, len(v) - k + 1):
best = max(best, sum(v[i:i + k]))Dacă toate valorile sunt negative, maximul real e sub 0, iar inițializarea cu 0 dă un rezultat care nu există. Pornește cu prima fereastră.
3Fereastra glisantă incrementală
s = sum(v[:k])
for i in range(k, len(v) - 1):
s += v[i] - v[i - k]s = sum(v[:k])
for i in range(k, len(v)):
s += v[i] - v[i - k]În varianta O(n), i este elementul care intră în fereastră și trebuie să meargă până la ultimul indice, len(v) - 1 inclusiv.
Repară eroarea, direct în pagină
Funcția cele_mai_bune_zile(vizite, k) returnează suma maximă a vizitelor din k zile consecutive. Testele cu assert pică: când cele mai bune zile sunt la final, rezultatul e greșit. Repar-o ca testele să treacă și să afișeze 25, 9 și -3.
def cele_mai_bune_zile(vizite, k):
best = 0
for i in range(len(vizite) - k):
best = max(best, sum(vizite[i:i + k]))
return best
r1 = cele_mai_bune_zile([3, 1, 4, 10, 15], 2)
r2 = cele_mai_bune_zile([4, 5], 2)
r3 = cele_mai_bune_zile([-5, -3, -8], 1)
assert (r1, r2, r3) == (25, 9, -3), f"fereastra gresita: {r1}, {r2}, {r3}"
print(r1)
print(r2)
print(r3)25 9 -3
Indiciu
Numără câte ferestre de lungime k are o listă cu n elemente și pornește maximul de la prima fereastră, nu de la 0.
Reparația
def cele_mai_bune_zile(vizite, k):
best = sum(vizite[:k])
for i in range(1, len(vizite) - k + 1):
best = max(best, sum(vizite[i:i + k]))
return best
r1 = cele_mai_bune_zile([3, 1, 4, 10, 15], 2)
r2 = cele_mai_bune_zile([4, 5], 2)
r3 = cele_mai_bune_zile([-5, -3, -8], 1)
assert (r1, r2, r3) == (25, 9, -3), f"fereastra gresita: {r1}, {r2}, {r3}"
print(r1)
print(r2)
print(r3)De ce merge
O listă cu 5 elemente are 4 ferestre de lungime 2, care încep la 0, 1, 2 și 3. Codul stricat folosea range(3) și nu ajungea la fereastra 10 + 15. Pe lista [4, 5] cu k = 2 nu verifica nicio fereastră, iar pe valorile negative maximul rămânea 0. Cu best pornit de la prima fereastră și range(1, len(vizite) - k + 1), fiecare fereastră e verificată exact o dată.
Cum o eviți pe viitor
Înainte de buclă, scrie în comentariu câte ferestre există (n - k + 1) și care e ultimul indice de start (n - k). Verifică formula pe un exemplu mic: pentru n = 5, k = 2 ai ferestrele 0-1, 1-2, 2-3, 3-4, deci 4. Testează funcția pe trei cazuri: răspunsul la început, răspunsul la final și len(lista) == k.
Întrebări frecvente
De ce nu primesc nicio eroare?
Pentru că bucla folosește doar indici valizi: se oprește prea devreme, nu prea târziu. Erorile off-by-one de acest tip dau rezultate greșite, nu excepții, și se prind doar cu teste.
Cum îmi dau seama dacă formula e n - k sau n - k + 1?
Ia cel mai mic caz: n = k. Există exact o fereastră, deci bucla trebuie să ruleze o dată: range(n - k + 1) = range(1). range(n - k) = range(0) nu rulează deloc.
Erori înrudite
IndexError: list index out of range la lista[i + 1] Compari fiecare element cu următorul (lista[i] și lista[i + 1]), dar bucla merge până la ultimul element, care nu are un următor. Oprește bucla cu un pas mai devreme: for i in range(len(lista) - 1). ValueError: max() iterable argument is empty Ai apelat max() (sau min()) pe o listă goală, deci nu există un maxim. Tratează lista goală înainte (if not lista: return ...) sau dă-i lui max o valoare implicită: max(lista, default=0). Căutarea binară nu găsește elementul de la capăt (while stanga < dreapta) Ai folosit while stanga < dreapta cu intervalul închis [0, len - 1] și actualizări mijloc + 1 / mijloc - 1. Bucla se oprește când rămâne un singur element, fără să-l verifice, deci returnează -1 deși valoarea există. Folosește while stanga <= dreapta. Învață Algoritmi și structuri de date de la zero, cu exerciții la fiecare lecție
Curs Algoritmi pentru interviuri: lecții scurte, fiecare cu un exercițiu verificat automat, direct în browser. Primele 2 lecții sunt gratuite.
