Note de curs, clasele 9-10, 15 martie 2013
From Algopedia
Jump to navigationJump to search
Algoritmi pe vectori și matrice
Mulți erau cunoscuți, dar am vrut să mă asigur, căci intervin foarte des.
- problema majorității: se dă un vector, să se identifice (dacă există) un element care apare de n/2 + 1 ori.
- soluție O(n): eliminarea numerelor în perechi
- soluție O(n): găsirea medianului (cu algoritmul de selecție)
- soluție O(n): construim o tabelă hash care mapează valori la frecvențe
- MSW (minimum over a sliding window): se dă un vector, să se tipărească min(v[i], v[i + 1], ..., v[i + k - 1]) pentru fiecare i = 0, 1, ..., n - k
- soluție O(n) amortizat: cu un deque (coadă cu două capete)
- soluție cu heap: O(n log k)
- subsecvența de sumă maximă: se dă un vector, să se găsească o subsecvență de sumă maximă
- soluție O(n): programare dinamică
- dreptunghiul de sumă maximă
- naiv O(n6): generăm toate dreptunghiurile în O(n4) și le verificăm în O(n2)
- soluție O(n4): precalculăm s[i][j] = suma elementelor din dreptunghiul (1, 1) - (i, j)
- soluție O(n3): pentru fiecare pereche de rânduri i și j, căutăm în O(n) coloanele k și l care ne dau dreptunghiul maxim
- implică niște precalculări, apoi reducerea la subsecvența de sumă maximă
- dreptunghiul de sumă maximă de dimensiune p*q
- soluție O(n2): cu precalcularea unor sume de p elemente pe linie, respectiv q pe coloană
- maximum gap: se dă un vector nesortat; să se găsească distanța maximă între două elemente consecutive în vectorul sortat
- soluție O(n): cu principiul cutiei
- șmenul lui Mars
- dreptunghiul maximal: se dă o matrice de 0 și 1, să se găsească dreptunghiul de arie maximă care conține doar 0
- soluție naivă O(n6): generăm toate dreptunghiurile în O(n4) și le verificăm în O(n2)
- soluție O(n4): precalculăm s[i][j] = suma elementelor din dreptunghiul (1, 1) - (i, j)
- soluție O(n4): fixăm colțul stânga-sus, apoi pentru fiecare linie numărăm zerourile dinspre dreapta
- soluție O(n3): idem, dar precalculăm numărul de zerouri dinspre dreapta
- soluție O(n2): cu o coadă dublă (sau stivă), similar cu problema Skyline / cel mai mare dreptunghi de sub histogramă
Discuții inginerești
- despre munca la Google, unelte pentru code versioning, unit testing, practici inginerești sănătoase
Temă
- cel mai mare dreptunghi gol (maximum empty rectangle sau MER): se dă un dreptunghi prin coordonatele sus, jos, stânga, dreapta ale marginilor. În acest dreptunghi sunt n puncte de coordonate reale. Să se găsească aria celui mai mare dreptunghi conținut în primul care să nu aibă niciun punct în interior.
- căutați o soluție O(n2)
- are elemente comune cu maximum gap
- subsecvență de sumă S: se dau un vector și un număr S. Să se găsească o subsecvență (interval continuu) de sumă S
- căutați o soluție O(n)