Clasa a XII-a · 7 algoritmiRead in English

Tehnici avansate: doi pointeri, căutare binară pe răspuns, stive monotoneAdvanced techniques: two pointers, binary search on the answer, monotonic stacks

Toți algoritmii din capitolul „Tehnici avansate: doi pointeri, căutare binară pe răspuns, stive monotone”, din programa de liceu: ideea explicată, complexitatea, exemple și cod C++ pe care îl poți modifica și rula chiar aici.

Fă-ți cont gratuit Vezi toți algoritmii

7algoritmi
6capitole
1clasă

Tehnici avansate: doi pointeri, căutare binară pe răspuns, stive monotone

Advanced techniques: two pointers, binary search on the answer, monotonic stacks · 7 algoritmi

Căutare binară pe răspunsBinary search on the answerAvem n capitole cu a[i] pagini, în ordine, și k corectori. Fiecare corector primește o…O(n log n)
Doi pointeri — perechi cu suma x într-un vector sortatTwo pointers: pairs with sum x in a sorted arrayVectorul are n valori distincte, în ordine strict crescătoare. Vrem perechile de poziții…O(n)
Element majoritar (Boyer-Moore)Majority element (Boyer-Moore)Elementul majoritar apare de mai mult de n / 2 ori. Algoritmul de vot ține un candidat…O(n)
Fereastra glisantă — cea mai lungă secvență cu suma ≤ SSliding window: the longest subarray with sum ≤ SToate numerele sunt strict pozitive. Ținem o fereastră [st, dr] și suma ei. Extindem…O(n)
Stiva monotonă — următorul element mai mareMonotonic stack: the next greater elementPentru fiecare a[i] căutăm prima valoare strict mai mare aflată în dreapta lui (sau -1).…O(n)
Generarea submulțimilor cu măști de bițiGenerating subsets with bitmasksO submulțime a lui {a[0], ..., a[n-1]} se poate codifica printr-un număr masca între 0…Exponențială
Sume parțiale pe matrice2D prefix sumss[i][j] = suma elementelor din dreptunghiul cu colțurile (1, 1) și (i, j). Se calculează…O(n²)