Şablon düşüncəsi
Çox alqoritmik məsələ az sayda şablonun variantıdır. Müvəffəqiyyətin yarısı şərtdəki siqnalı tanımaqdır: "sıralı massiv", "ardıcıl alt massiv", "ən qısa yol", "bütün kombinasiyalar", "ən yaxşı nəticə, alt məsələlər təkrarlanır". Sonra uyğun şablonun kodunu yazırsınız. Bu dərs xəritədir; hər şablonun ətraflı mövzusu kursda var.
Siqnaldan şablona
| Şərtdəki siqnal | Şablon | Tipik mürəkkəblik |
|---|---|---|
| sıralı massiv, cüt/üçlük axtar | iki göstərici | O(n) |
ardıcıl alt massiv/alt sətir, uzunluq k | sürüşən pəncərə | O(n) |
| "var?", sayma, təkrar, cüt tapmaq | hash map / set | O(n) |
| sıralı və ya monoton, "ilk uyğun" | ikili axtarış | O(log n) |
| qrafda/şəbəkədə ən qısa yol (çəkisiz) | BFS | O(V + E) |
| komponent, dövr, bütün yollar | DFS | O(V + E) |
"ən böyük k", axın ortası | heap | O(n log k) |
| intervallar, birləşdirmə, üst-üstə düşmə | sort + sweep | O(n log n) |
| bütün alt çoxluqlar/permutasiyalar | backtracking | eksponensial |
| optimal, alt məsələlər təkrarlanır | dinamik proqramlaşdırma | cədvəl ölçüsü |
İki göstərici və sürüşən pəncərə
Sıralı massivdə iki ucdan başlayıb içəri sıxırıq: cəm çox isə sağı, az isə solu hərəkət etdiririk. Hər element ən çox bir dəfə keçilir: O(n). Pəncərədə yeni elementi əlavə edir, köhnəni çıxarırıq: təkrar cəmləmək əvəzinə O(1) yeniləmə. Ətraflı: iki göstərici, sürüşən pəncərə.
