[[0] * m] * n: modifici o celulă și se schimbă toată coloana
[[0] * m] * n nu creează n rânduri, ci n referințe la același rând, așa că dp[0][1] = 5 apare în toate rândurile. Creează fiecare rând separat: [[0] * m for _ in range(n)].
Explicat de Tudor Andrei Dumitrescu, Senior Software Developer, fondatorul Academiei ProgramatorilorActualizat la
Ce înseamnă
Operatorul * pe o listă copiază referințele la elemente, nu elementele. [0] * m e corect, pentru că numerele sunt imuabile. Dar [[0] * m] * n ia o singură listă-rând și pune de n ori referința la ea în lista exterioară. Toate rândurile sunt același obiect: când scrii grila[0][1] = 5, vezi 5 în coloana 1 a fiecărui rând.
În algoritmi, asta strică tabelele DP 2D, matricele de vizitate pentru grile și hărțile de distanțe. Programul nu dă nicio eroare: tabelul pur și simplu conține valori greșite, iar rezultatul final e greșit sau ciudat de mare.
Poți verifica rapid cu grila[0] is grila[1]: dacă e True, rândurile sunt comune. Reparația e list comprehension: [[0] * m for _ in range(n)] evaluează [0] * m din nou pentru fiecare rând.
De ce apare: cauzele frecvente
1Tabel DP creat cu * n
dp = [[0] * 3] * 2
dp[0][0] = 1
print(dp)dp = [[0] * 3 for _ in range(2)]
dp[0][0] = 1
print(dp)Prima variantă afișează [[1, 0, 0], [1, 0, 0]], pentru că ambele rânduri sunt aceeași listă. A doua afișează [[1, 0, 0], [0, 0, 0]].
2Matrice de vizitate pentru o grilă
vizitat = [[False] * coloane] * randurivizitat = [[False] * coloane for _ in range(randuri)]Marcarea unei celule ar marca toată coloana, deci BFS-ul ar sări peste celule nevizitate.
3Copierea unei matrice
copie = grila[:]
copie[0][0] = '#'copie = [rand[:] for rand in grila]
copie[0][0] = '#'grila[:] copiază doar lista exterioară; rândurile rămân comune cu originalul. Copiază fiecare rând.
Repară eroarea, direct în pagină
Funcția harta(n, m, obstacole) construiește harta unui depozit cu n rânduri și m coloane, cu . pentru celulele libere și # pentru obstacole. Grila e creată cu [['.'] * m] * n, iar testul cu assert pică: fiecare obstacol apare pe toate rândurile. Repar-o ca testul să treacă și să afișeze cele trei rânduri #.., ... și ..#.
def harta(n, m, obstacole):
grila = [['.'] * m] * n
for r, c in obstacole:
grila[r][c] = '#'
return [''.join(rand) for rand in grila]
h = harta(3, 3, [(0, 0), (2, 2)])
assert h == ['#..', '...', '..#'], f"harta gresita: {h}"
for rand in h:
print(rand)#.. ... ..#
Indiciu
Fiecare rând al grilei trebuie să fie o listă creată separat.
Reparația
def harta(n, m, obstacole):
grila = [['.'] * m for _ in range(n)]
for r, c in obstacole:
grila[r][c] = '#'
return [''.join(rand) for rand in grila]
h = harta(3, 3, [(0, 0), (2, 2)])
assert h == ['#..', '...', '..#'], f"harta gresita: {h}"
for rand in h:
print(rand)De ce merge
Cu [['.'] * m] * n, lista exterioară conținea de trei ori referința la același rând. Obstacolul din (0, 0) și cel din (2, 2) au fost scrise în acel unic rând, deci toate cele trei rânduri arătau #.#. Comprehension-ul [['.'] * m for _ in range(n)] evaluează ['.'] * m din nou pentru fiecare rând, așa că fiecare obstacol modifică doar rândul lui. Aceeași capcană strică tabelele DP 2D și matricele de vizitate.
Cum o eviți pe viitor
Regula simplă: * e sigur doar pentru liste de valori imuabile ([0] * m, [False] * n, [None] * n). Pentru orice listă de liste folosește comprehension: [[0] * m for _ in range(n)]. La copiere, copiază fiecare rând ([r[:] for r in grila]) sau folosește copy.deepcopy. După ce creezi un tabel, verifică pe un exemplu mic că o singură modificare schimbă o singură celulă.
Întrebări frecvente
De ce [0] * m merge, dar [[0] * m] * n nu?
Și [0] * m conține de m ori referința la același obiect 0. Dar numerele nu se pot modifica: rand[1] = 5 înlocuiește referința din poziția 1, nu modifică obiectul 0. Un rând e o listă, care se modifică pe loc, deci schimbarea se vede prin toate referințele.
Merge la fel cu dicționare sau set-uri?
Da, [{}] * n sau [set()] * n creează n referințe la același dicționar sau set. Folosește [{} for _ in range(n)] sau [set() for _ in range(n)].
Erori înrudite
TypeError: 'int' object is not subscriptable la dp[i][j] Ai creat tabelul DP cu o singură dimensiune (dp = [0] * n), deci dp[i] este un număr, iar dp[i][j] încearcă să ia un element dintr-un număr. Creează o matrice: dp = [[0] * coloane for _ in range(randuri)]. Backtracking-ul returnează liste goale: [[], [], []] Ai adăugat în rezultat chiar lista de lucru (rezultat.append(drum)), nu o copie a ei. La final backtracking-ul golește lista, deci toate intrările arată goale. Adaugă o copie: rezultat.append(drum[:]) sau list(drum). IndexError: list index out of range la parcurgerea unei matrice Ai inversat numărul de rânduri cu numărul de coloane (sau i cu j) la o matrice care nu e pătrată. len(grila) e numărul de rânduri, len(grila[0]) e numărul de coloane, iar accesul se face mereu grila[rand][coloana]. Î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.
