Патерни алгоритмів і структур даних - javascript.org.ua

1. Швидкий і Повільний вказівник

Опис: Ця техніка використовує два вказівники, які рухаються з різною швидкістю, щоб вирішити проблеми, пов'язані з циклами, такі як знаходження середини списку, виявлення циклів або перевірка на паліндроми.

2. Перекриті інтервали

Опис: Інтервали часто маніпулюються через сортування та об'єднання на основі їх початкового та кінцевого часу.

3. Префіксні суми

Опис: Префіксні суми/добутки — це техніки, які зберігають накопичувані суми або добутки до кожного індексу, дозволяючи швидко виконувати запити на діапазон підмасивів.

4. Слайдінг Вікно

Опис: Слайдінг вікно — це підмасив або підрядок, який рухається по даних для ефективного вирішення проблем за лінійний час.

Фіксований розмір

Змінний розмір

5. Два вказівники

Опис: Техніка з двома вказівниками передбачає наявність двох різних індексів, які рухаються через вхідні дані з різною швидкістю для вирішення різних проблем з масивами або зв'язаними списками.

Two Sum II — Input Array is Sorted
Dutch National Flag: Sort Colors
Next Permutation
Bag of Tokens
Container with most water
Trapping Rain Water
## 6. Циклічне сортування (Індексоване)

Опис: Циклічне сортування — це ефективний підхід до вирішення проблем, де числа мають послідовний порядок і повинні бути розташовані в правильному індексі.

7. Реверсія зв'язного списку (In-place)

Опис: Реверсія зв'язного списку на місці без використання додаткового простору є ключем до вирішення проблем, що вимагають маніпуляцій зі списками на місці.

8. Маніпуляція матрицями

Опис: Проблеми, що стосуються 2D масивів (матриць), часто вирішуються за допомогою обходу рядків і стовпців або маніпуляцій на основі властивостей матриць.

9. Пошук в ширину (BFS)

Опис: BFS досліджує вузли рівень за рівнем за допомогою черги. Він особливо корисний для задач на найкоротший шлях.

10. Пошук в глибину (DFS)

Опис: DFS досліджує гілку до кінця, перш ніж повернутися. Це корисно для обходу графів, пошуку шляхів і пошуку зв'язних компонентів.

11. Зворотний пошук (Backtracking)

Опис: Зворотний пошук допомагає в задачах, де потрібно досліджувати всі можливі рішення, наприклад, вирішення головоломок, генерація комбінацій або пошук шляхів.

Permutation ii
Combination Sum
Generate Parenthesis
N-Queens
Sudoku Solver
Palindrome Partitioning
Word Search: Word Search
## 12. Модифікований бінарний пошук

Опис: Модифікована версія бінарного пошуку, яка застосовується до обертованих масивів, не відсортованих масивів або спеціальних умов.

13. Побітовий XOR

Опис: XOR — це потужний побітовий оператор, який може вирішувати такі проблеми, як пошук єдиного числа або ефективне парування елементів.

14. Топ ‘K’ елементів

Опис: Цей шаблон використовує купи або quickselect для ефективного знаходження топових ‘K’ найбільших/найменших елементів з набору даних.

15. Об'єднання K списків

Опис: Техніка об'єднання K списків використовує купу для ефективного об'єднання кількох відсортованих списків або масивів.

16. Два купи

Опис: Цей шаблон використовує два купи (макс купа та мін купа) для вирішення задач, що стосуються відстеження медіан і ефективного управління динамічними даними.

17. Монотонний стек

Опис: Монотонний стек допомагає вирішувати задачі з діапазонними запитами, підтримуючи стек елементів у зростаючому або спадаючому порядку.

Next Greater Element II
Next Greater Node in Linked List
Daily Temperatures
Online Stock Span
Maximum Width Ramp
Largest Rectangle in Histogram
## Дерев’яні структури

1. Прохід по рівнях (BFS в бінарному дереві)

2. Побудова дерева

3. Проблеми, пов'язані з висотою

4. Проблеми шляху від кореня до листа

5. Проблема предка

6. Бінарне дерево пошуку

1. Взяти / Не взяти (DP)

Опис: Рішення задач оптимізації, таких як вибір елементів з максимальною/мінімальною вартістю за певних умов.

2. Нескінченний запас (DP)

Опис: Подібно до задачі рюкзака 0/1, але елементи можна вибирати кілька разів.

3. Найдовша зростаюча підпослідовність

Опис: Пошук найдовшої підпослідовності зростаючих елементів у заданій послідовності.

4. DP на решітках

Опис: Динамічне програмування на матрицях передбачає розв'язання задач, які можна розділити на менші накладаються підзадачі в межах матриці.

5. DP на рядках

Опис: Задачі на дві строки, де необхідно зосередитися на тому, що відбувається, коли останні символи двох підстрічок однакові, тобто, співпадають.

6. DP на акціях

Опис: Техніка, спрямована на максимізацію прибутку від купівлі та продажу акцій з урахуванням обмежень.

7. Розподіл DP (MCM)

Опис: Це включає послідовність, яку потрібно поділити на частини оптимальним способом.
Опис: Метою часто є мінімізація або максимізація функції вартості, такої як час обчислень, множення або інша метрика, шляхом дослідження всіх можливих розбиттів і комбінування результатів з підзадач.

20. Графи

Топологічне сортування

Опис: Топологічне сортування корисне для задач, що потребують вирішення залежностей (InDegree) у орієнтованих ациклічних графах (DAG).

Об'єднання і пошук (Disjoint Set)

Опис: Об'єднання і пошук (або Disjoint Set) використовуються для вирішення задач, що пов'язані з підключенням або групуванням, часто в графах.

Алгоритми графів

Опис: Просунуті алгоритми графів використовуються для вирішення складних задач, таких як знаходження найкоротших шляхів, мінімальні останні дерева та цикли графів.

21. Жадібні алгоритми

Опис: Жадібні алгоритми роблять локально оптимальні вибори на кожному кроці, що призводить до глобального оптимального рішення для задач, таких як планування та розподіл ресурсів.

22. Проектування структури даних

Опис: Це включає створення власних структур даних для ефективного виконання специфічних операцій, таких як керування доступом до даних, оновлення та використання пам'яті.
Опис: Зосереджено на оптимізації продуктивності та управлінні ресурсами.

Деякі корисні статті на LeetCode для кращого розуміння!

Два вказівники

Розв'язано всі проблеми з двома вказівниками за 100 днів