1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295# JavaScript Algorytmy i Struktury Danych
[](https://github.com/trekhleb/javascript-algorithms/actions?query=workflow%3ACI+branch%3Amaster)
[](https://codecov.io/gh/trekhleb/javascript-algorithms)
To repozytorium zawiera wiele przykładów JavaScript opartych na
znanych algorytmach i strukturach danych.
Każdy algorytm i struktura danych zawiera osobny plik README
wraz z powiązanymi wyjaśnieniami i odnośnikami do dalszego czytania
(włącznie z tymi do YouTube videos).
_Read this in other languages:_
[_English_](https://github.com/trekhleb/javascript-algorithms/)
[_简体中文_](README.zh-CN.md),
[_繁體中文_](README.zh-TW.md),
[_한국어_](README.ko-KR.md),
[_日本語_](README.ja-JP.md),
[_Français_](README.fr-FR.md),
[_Español_](README.es-ES.md),
[_Português_](README.pt-BR.md),
[_Русский_](README.ru-RU.md),
[_Türk_](README.tr-TR.md),
[_Italiana_](README.it-IT.md),
[_Bahasa Indonesia_](README.id-ID.md),
[_Українська_](README.uk-UA.md),
[_Arabic_](README.ar-AR.md),
[_Tiếng Việt_](README.vi-VN.md),
[_Deutsch_](README.de-DE.md)
## Struktury Danych
Struktura danych to sposób uporządkowania i przechowywania informacji w
komputerze żeby mogłaby być sprawnie dostępna i efektywnie zmodyfikowana.
Dokładniej, struktura danych jest zbiorem wartości danych, relacjami
pomiędzy nimi, zadaniami lub działaniami, które mogą dotyczyć danych.
`B` - Początkujący, `A` - Zaawansowany
* `B` [Lista](src/data-structures/linked-list)
* `B` [Lista Dwukierunkowa](src/data-structures/doubly-linked-list)
* `B` [Kolejka](src/data-structures/queue)
* `B` [Stos](src/data-structures/stack)
* `B` [Tabela Skrótu](src/data-structures/hash-table)
* `B` [Sterta](src/data-structures/heap)
* `B` [Kolejka Priorytetowa](src/data-structures/priority-queue)
* `A` [Trie](src/data-structures/trie)
* `A` [Drzewo](src/data-structures/tree)
* `A` [Wyszukiwanie Binarne](src/data-structures/tree/binary-search-tree)
* `A` [AVL Drzewo](src/data-structures/tree/avl-tree)
* `A` [Drzewa czerwono-czarne](src/data-structures/tree/red-black-tree)
* `A` [Drzewo Segmentu](src/data-structures/tree/segment-tree) - z przykładami zapytań o min / max / sumie sum
* `A` [Drzewo Fenwicka](src/data-structures/tree/fenwick-tree) (Drzewo Indeksowane Binarnie)
* `A` [Graf](src/data-structures/graph) (zarówno skierowane i nieukierunkowane)
* `A` [Rozłączny Zestaw](src/data-structures/disjoint-set)
* `A` [Filtr Blooma](src/data-structures/bloom-filter)
## Algorytmy
Algorytm jest to skończony ciąg jasno zdefiniowanych czynności, koniecznych
do wykonania pewnego rodzaju zadań. Sposób postępowania prowadzący do
rozwiązania problemu.
`B` - Początkujący, `A` - Zaawansowany
### Algorytmy według tematu
* **Matematyka**
* `B` [Manipulacja Bitami](src/algorithms/math/bits) - ustaw / uzyskaj / aktualizuj / usuwaj bity, mnożenie / dzielenie przez dwa, tworzenie negatywów itp.
* `B` [Silnia](src/algorithms/math/factorial)
* `B` [Ciąg Fibonacciego](src/algorithms/math/fibonacci)
* `B` [Test Pierwszorzędności](src/algorithms/math/primality-test) (metoda podziału na próby)
* `B` [Algorytm Euclideana](src/algorithms/math/euclidean-algorithm) - obliczyć Największy Wspólny Dzielnik (GCD)
* `B` [Najmniejsza Wspólna Wielokrotność](src/algorithms/math/least-common-multiple) (LCM)
* `B` [Sito Eratosthenes-a](src/algorithms/math/sieve-of-eratosthenes) - znajdowanie wszystkich liczb pierwszych do określonego limitu
* `B` [Jest Potęgą Dwójki](src/algorithms/math/is-power-of-two) - sprawdź, czy liczba jest potęgą dwóch (algorytmy naiwne i bitowe)
* `B` [Trójkąt Pascala](src/algorithms/math/pascal-triangle)
* `A` [Partycja Całkowita](src/algorithms/math/integer-partition)
* `A` [Algorytm Liu Huia](src/algorithms/math/liu-hui) - przybliżone obliczenia na podstawie N-gonów
* **Zestawy**
* `B` [Produkt Kartezyjny](src/algorithms/sets/cartesian-product) - wynik wielu zestawów
* `B` [Przetasowanie Fisher Yates-a](src/algorithms/sets/fisher-yates) - losowa permutacja kończącej się serii
* `A` [Zestaw Zasilający](src/algorithms/sets/power-set) - podzbiór wszystkich serii
* `A` [Permutacje](src/algorithms/sets/permutations) (z albo bez powtórzeń)
* `A` [Kombinacje](src/algorithms/sets/combinations) (z albo bez powtórzeń)
* `A` [Najdłuższa Wspólna Podsekwencja](src/algorithms/sets/longest-common-subsequence) (LCS)
* `A` [Najdłuższa Wzrostająca Podsekwencja](src/algorithms/sets/longest-increasing-subsequence)
* `A` [Najkrótsza Wspólna Supersekwencja](src/algorithms/sets/shortest-common-supersequence) (SCS)
* `A` [Problem Knapsacka](src/algorithms/sets/knapsack-problem) - "0/1" i "Rozwiązany"
* `A` [Maksymalna Podtablica](src/algorithms/sets/maximum-subarray) - "Metoda Siłowa" i "Dynamiczne Programowanie" (Kadane-a) wersje
* `A` [Suma Kombinacji](src/algorithms/sets/combination-sum) -
znajdź wszystkie kombinacje, które tworzą określoną sumę
* **Łańcuchy**
* `B` [Odległość Hamminga](src/algorithms/string/hamming-distance) - liczba pozycji, w których symbole są różne
* `A` [Odległość Levenshteina](src/algorithms/string/levenshtein-distance) - minimalna odległość edycji między dwiema sekwencjami
* `A` [Algorytm Knuth–Morris–Pratta](src/algorithms/string/knuth-morris-pratt) (Algorytm KMP) - dopasowywanie wzorców (dopasowywanie wzorców)
* `A` [Algorytm Z](src/algorithms/string/z-algorithm) - szukanie podłańcucha(dopasowywanie wzorców)
* `A` [Algorytm Rabin Karpa](src/algorithms/string/rabin-karp) - szukanie podłańcucha
* `A` [Najdłuższa Wspólna Podłańcucha](src/algorithms/string/longest-common-substring)
* `A` [Dopasowanie Wyrażeń Regularnych](src/algorithms/string/regular-expression-matching)
* **Szukanie**
* `B` [Wyszukiwanie Liniowe](src/algorithms/search/linear-search)
* `B` [Jump Search](src/algorithms/search/jump-search) (lub Przeszukiwanie Bloku) - szukaj w posortowanej tablicy
* `B` [Wyszukiwanie Binarne](src/algorithms/search/binary-search) - szukaj w posortowanej tablicy
* `B` [Wyszukiwanie Interpolacyjne](src/algorithms/search/interpolation-search) - szukaj w równomiernie rozłożonej, posortowanej tablicy
* **Sortowanie**
* `B` [Sortowanie bąbelkowe](src/algorithms/sorting/bubble-sort)
* `B` [Sortowanie przez wymiane](src/algorithms/sorting/selection-sort)
* `B` [Sortowanie przez wstawianie](src/algorithms/sorting/insertion-sort)
* `B` [Sortowanie stogowe](src/algorithms/sorting/heap-sort)
* `B` [Sortowanie przez scalanie](src/algorithms/sorting/merge-sort)
* `B` [Sortowanie szybkie](src/algorithms/sorting/quick-sort) - wdrożenia w miejscu i nie na miejscu
* `B` [Sortowanie Shella](src/algorithms/sorting/shell-sort)
* `B` [Sortowanie przez zliczanie](src/algorithms/sorting/counting-sort)
* `B` [Sortowanie pozycyjne](src/algorithms/sorting/radix-sort)
* **Drzewa**
* `B` [Przeszukiwanie w głąb](src/algorithms/tree/depth-first-search) (DFS)
* `B` [Przeszukiwanie wszerz](src/algorithms/tree/breadth-first-search) (BFS)
* **Grafy**
* `B` [Przeszukiwanie w głąb](src/algorithms/graph/depth-first-search) (DFS)
* `B` [Przeszukiwanie wszerz](src/algorithms/graph/breadth-first-search) (BFS)
* `B` [Algorytm Kruskala](src/algorithms/graph/kruskal) - znalezienie Minimalnego Drzewa Opinającego (MST) dla ważonego nieukierunkowanego wykresu
* `A` [Algorytm Dijkstry](src/algorithms/graph/dijkstra) - znajdowanie najkrótszej ścieżki z pojedynczego źródła w grafie
* `A` [Algorytm Bellmana-Forda](src/algorithms/graph/bellman-ford) - znajdowanie najkrótszych ścieżek do wszystkich wierzchołków wykresu z jednego wierzchołka
* `A` [Algorytm Floyd-Warshalla](src/algorithms/graph/floyd-warshall) - znajdź najkrótsze ścieżki między wszystkimi parami wierzchołków
* `A` [Detect Cycle](src/algorithms/graph/detect-cycle) - zarówno dla wykresów skierowanych, jak i nieukierunkowanych(wersje oparte na DFS i Rozłączny Zestaw)
* `A` [Algorytm Prima](src/algorithms/graph/prim) - znalezienie Minimalnego Drzewa Opinającego (MST) dla ważonego nieukierunkowanego wykresu
* `A` [Sortowanie Topologiczne](src/algorithms/graph/topological-sorting) - metoda DFS
* `A` [Punkty Artykulacji](src/algorithms/graph/articulation-points) - Algorytm Tarjana (oparty o DFS)
* `A` [Mosty](src/algorithms/graph/bridges) - Oparty na algorytmie DFS
* `A` [Ścieżka Euleriana i Obwód Euleriana](src/algorithms/graph/eulerian-path) - Algorytm Fleurya - Odwiedź każdą krawędź dokładnie raz
* `A` [Cykl Hamiltoniana](src/algorithms/graph/hamiltonian-cycle) - Odwiedź każdy wierzchołek dokładnie raz
* `A` [Silnie Połączone Komponenty](src/algorithms/graph/strongly-connected-components) - Algorytm Kosaraja
* `A` [Travelling Salesman Problem](src/algorithms/graph/travelling-salesman) - najkrótsza ścieżka która odwiedza każde miasto i wraca miasta początkującego
* **Niezkategorizowane**
* `B` [Wieża Hanoi](src/algorithms/uncategorized/hanoi-tower)
* `B` [Kwadratowa Matryca Obrotu](src/algorithms/uncategorized/square-matrix-rotation) - algorytm w miejscu
* `B` [Jump Game](src/algorithms/uncategorized/jump-game) - cofanie, dynamiczne programowanie (od góry do dołu + od dołu do góry) i przykłady chciwego
* `B` [Unikatowe Ścieżki](src/algorithms/uncategorized/unique-paths) - cofanie, dynamiczne programowanie i przykłady oparte na Trójkącie Pascala
* `A` [Problem N-Queens](src/algorithms/uncategorized/n-queens)
* `A` [Knight's Tour](src/algorithms/uncategorized/knight-tour)
### Algorytmy według paradygmatu
Paradygmat algorytmiczny jest ogólną metodą lub podejściem, które jest
podstawą projektowania klasy algorytmów. Jest abstrakcją wyższą niż
pojęcie algorytmu, podobnie jak algorytm jest abstrakcją wyższą niż
program komputerowy.
* **Metoda Siłowa** - Sprawdza wszystkie możliwosci i wybiera najlepsze rozwiązanie.
* `B` [Wyszukiwanie Liniowe](src/algorithms/search/linear-search)
* `A` [Maksymalna Podtablica](src/algorithms/sets/maximum-subarray)
* `A` [Problem z Podróżującym Sprzedawcą](src/algorithms/graph/travelling-salesman) - najkrótsza możliwa trasa, która odwiedza każde miasto i wraca do miasta początkowego
* **Chciwy** - wybierz najlepszą opcję w obecnym czasie, bez względu na przyszłość
* `B` [Jump Game](src/algorithms/uncategorized/jump-game)
* `A` [Niezwiązany Problem Knapsacka ](src/algorithms/sets/knapsack-problem)
* `A` [Algorytm Dijkstry](src/algorithms/graph/dijkstra) -
znalezienie najkrótszej ścieżki do wszystkich wierzchołków grafu
* `A` [Algorytm Prima](src/algorithms/graph/prim) - znalezienie Minimalnego Drzewa Opinającego (MST) dla ważonego nieukierunkowanego wykresu
* `A` [Algorytm Kruskala](src/algorithms/graph/kruskal) - znalezienie Minimalnego Drzewa Opinającego (MST) dla ważonego nieukierunkowanego wykresu
* **Dziel i Zwyciężaj** - podziel problem na mniejsze części, a następnie rozwiąż te części
* `B` [Wyszukiwanie Binarne](src/algorithms/search/binary-search)
* `B` [Wieża Hanoi](src/algorithms/uncategorized/hanoi-tower)
* `B` [Trójkąt Pascala](src/algorithms/math/pascal-triangle)
* `B` [Algorytm Euclideana](src/algorithms/math/euclidean-algorithm) - obliczyć Największy Wspólny Dzielnik(GCD)
* `B` [Sortowanie przez scalanie](src/algorithms/sorting/merge-sort)
* `B` [Szybkie Sortowanie](src/algorithms/sorting/quick-sort)
* `B` [Drzewo Przeszukiwania W Głąb](src/algorithms/tree/depth-first-search) (DFS)
* `B` [Graf Przeszukiwania W Głąb](src/algorithms/graph/depth-first-search) (DFS)
* `B` [Jump Game](src/algorithms/uncategorized/jump-game)
* `A` [Permutacje](src/algorithms/sets/permutations) (z albo bez powtórzeń)
* `A` [Kombinacje](src/algorithms/sets/combinations) (z albo bez powtórzeń)
* **Programowanie Dynamiczne** - zbuduj rozwiązanie, korzystając z wcześniej znalezionych podrzędnych rozwiązań
* `B` [Ciąg Fibonacciego](src/algorithms/math/fibonacci)
* `B` [Jump Game](src/algorithms/uncategorized/jump-game)
* `B` [Unikatowe Scieżki](src/algorithms/uncategorized/unique-paths)
* `A` [Dystans Levenshteina](src/algorithms/string/levenshtein-distance) - minimalna odległość edycji między dwiema sekwencjami
* `A` [Najdłuższa Wspólna Podsekwencja](src/algorithms/sets/longest-common-subsequence) (LCS)
* `A` [Najdłuższa Wspólna Podłańcucha](src/algorithms/string/longest-common-substring)
* `A` [Najdłuższa Wzrostająca Podsekwencja](src/algorithms/sets/longest-increasing-subsequence)
* `A` [Najkrótsza Wspólna Supersekwencja](src/algorithms/sets/shortest-common-supersequence)
* `A` [0/1 Problem Knapsacka](src/algorithms/sets/knapsack-problem)
* `A` [Partycja Całkowita](src/algorithms/math/integer-partition)
* `A` [Maksymalne Podtablice](src/algorithms/sets/maximum-subarray)
* `A` [Algorytm Bellman-Forda](src/algorithms/graph/bellman-ford) - znalezienie najkrótszej ścieżki wszystkich wierzchołków wykresu
* `A` [Algorytm Floyd-Warshalla](src/algorithms/graph/floyd-warshall) -
znajdź najkrótsze ścieżki między wszystkimi parami wierzchołków
* `A` [Dopasowanie Wyrażeń Regularnych](src/algorithms/string/regular-expression-matching)
* **Algorytm z nawrotami** - podobny do metody siłowej, próbuje wygenerować wszystkie możliwe rozwiązania, jednak za każdym razem generujesz następne rozwiązanie które testujesz
jeżeli zaspokaja wszystkie warunki, tylko wtedy generuje kolejne rozwiązania. W innym wypadku, cofa sie, i podąża inna ścieżka znaleźenia rozwiązania. Zazwyczaj, używane jest przejście przez Przeszukiwania W Głąb(DFS) przestrzeni stanów.
* `B` [Jump Game](src/algorithms/uncategorized/jump-game)
* `B` [Unikatowe Scieżki](src/algorithms/uncategorized/unique-paths)
* `A` [Cykl Hamiltoniana](src/algorithms/graph/hamiltonian-cycle) - Odwiedź każdy wierzchołek dokładnie raz
* `A` [Problem N-Queens](src/algorithms/uncategorized/n-queens)
* `A` [Knight's Tour](src/algorithms/uncategorized/knight-tour)
* `A` [Zestaw Sumy](src/algorithms/sets/combination-sum) - znajduje wszystkie zestawy które tworzą określoną sumę
* **Metoda Podziału i Ograniczeń** - Pamięta o niskonakładowym rozwiązaniu znalezionym na każdym etapie szukania nawrotu,
używa kosztu niskonakładowego kosztu, które dotychczas zostało znalezione jako niska granica najmniejszego kosztu
do rozwiązanie problemu, aby odrzucić cząstkowe rozwiązania o kosztach większych niż niskonakładowe
rozwiązanie znalezione do tej pory.
Zazwyczan trajektoria BFS, w połączeniu z trajektorią Przeszukiwania W Głąb (DFS) drzewa przestrzeni stanów jest użyte.
## Jak używać repozytorium
**Zainstaluj wszystkie zależnosci**
```
npm install
```
**Uruchom ESLint**
Możesz to uruchomić aby sprawdzić jakość kodu.
```
npm run lint
```
**Uruchom wszystkie testy**
```
npm test
```
**Uruchom testy używając określonej nazwy**
```
npm test -- 'LinkedList'
```
**Playground**
Możesz pociwiczyć ze strukturą danych i algorytmami w `./src/playground/playground.js` zakartotekuj i napisz
testy do tego w `./src/playground/__test__/playground.test.js`.
Następnie uruchom następującą komendę w celu przetestowania czy twoje kod działa według oczekiwań:
```
npm test -- 'playground'
```
## Pomocne informacje
### Źródła
[â–¶ Struktury Danych i Algorytmy na YouTube](https://www.youtube.com/playlist?list=PLLXdhg_r2hKA7DPDsunoDZ-Z769jWn4R8)
### Big O Notacja
Kolejność wzrastania algorytmów według Big O notacji.
Źródło: [Big O Cheat Sheet](http://bigocheatsheet.com/).
Poniżej umieszczamy listę najbardziej używanych Big O notacji i ich porównania wydajności do róznych rozmiarów z wprowadzonych danych.
| Big O notacja | Obliczenia na 10 elementów | Obliczenia na 100 elementów | Obliczenia na 1000 elementów |
| -------------- | ---------------------------- | ----------------------------- | ------------------------------- |
| **O(1)** | 1 | 1 | 1 |
| **O(log N)** | 3 | 6 | 9 |
| **O(N)** | 10 | 100 | 1000 |
| **O(N log N)** | 30 | 600 | 9000 |
| **O(N^2)** | 100 | 10000 | 1000000 |
| **O(2^N)** | 1024 | 1.26e+29 | 1.07e+301 |
| **O(N!)** | 3628800 | 9.3e+157 | 4.02e+2567 |
### Złożoność operacji struktury danych
| Struktura Danych | Dostęp | Szukaj | Umieszczanie | Usuwanie | Komentarze |
| ------------------------------- | :-------: | :-------: | :----------: | :-------: | :----------- |
| **Szereg** | 1 | n | n | n | |
| **Sterta** | n | n | 1 | 1 | |
| **Kolejka** | n | n | 1 | 1 | |
| **Lista Powiązana** | n | n | 1 | 1 | |
| **Tablica funkcji mieszanej** | - | n | n | n | W wypadku idealnej funkcji skrótu koszt mógłby sie równać O(1) |
| **Binarne Drzewo Poszukiwań** | n | n | n | n | W przypadku zrównoważonych kosztów drzew byłoby O(log(n)) |
| **B-Drzewo** | log(n) | log(n) | log(n) | log(n) | |
| **Drzewa czerwono-czarne** | log(n) | log(n) | log(n) | log(n) | |
| **AVL Drzewo** | log(n) | log(n) | log(n) | log(n) | |
| **Filtr Blooma** | - | 1 | 1 | - | Fałszywe dotatnie są możliwe podczas wyszukiwania |
### Sortowanie Tablic Złożoności Algorytmów
| Nazwa | Najlepszy | Średni | Najgorszy | Pamięć | Stabilność | Komentarze |
| ----------------------------------- | :-------------: | :-----------------: | :-----------------: | :-------: | :---------: | :---------- |
| **Sortowanie bąbelkowe** | n | n<sup>2</sup> | n<sup>2</sup> | 1 | Yes | |
| **Sortowanie przez wstawianie** | n | n<sup>2</sup> | n<sup>2</sup> | 1 | Yes | |
| **Sortowanie przez wybieranie** | n<sup>2</sup> | n<sup>2</sup> | n<sup>2</sup> | 1 | No | |
| **Sortowanie przez kopcowanie** | n log(n) | n log(n) | n log(n) | 1 | No | |
| **Sortowanie przez scalanie** | n log(n) | n log(n) | n log(n) | n | Yes | |
| **Szybkie sortowanie** | n log(n) | n log(n) | n<sup>2</sup> | log(n) | No | Szybkie sortowanie jest zazwyczaj robione w miejsce O(log(n)) stosu przestrzeni |
| **Sortowanie Shella** | n log(n) | zależy od luki w układzie | n (log(n))<sup>2</sup> | 1 | No | |
| **Sortowanie przez zliczanie** | n + r | n + r | n + r | n + r | Yes | r - największy numer w tablicy|
| **Sortowanie Radix** | n * k | n * k | n * k | n + k | Yes | k -długość najdłuższego klucza |
> ℹ️ A few more [projects](https://trekhleb.dev/projects/) and [articles](https://trekhleb.dev/blog/) about JavaScript and algorithms on [trekhleb.dev](https://trekhleb.dev)