Kho lưu trữ này chứa các ví dụ dựa trên JavaScript về nhiều thuật toán và cấu trúc dữ liệu phổ biến.

Mỗi thuật toán và cấu trúc dữ liệu đều có một tệp README riêng với các giải thích liên quan và các liên kết để đọc thêm (bao gồm cả các video trên YouTube).

Đọc tài liệu này bằng ngôn ngữ khác: English

Nguồn - Kho lưu trữ gốc

☝ Lưu ý rằng dự án này chỉ được sử dụng cho mục đích học tập và nghiên cứu, không dùng cho sản xuất.

Cấu trúc dữ liệu là một cách đặc biệt để tổ chức và lưu trữ dữ liệu trong máy tính sao cho có thể truy cập và sửa đổi hiệu quả. Một cách chính xác hơn, cấu trúc dữ liệu là tập hợp các giá trị dữ liệu, các mối quan hệ giữa chúng, và các hàm hoặc thao tác có thể được áp dụng cho dữ liệu.

B - Người mới bắt đầu, A - Nâng cao

• B Linked List - Danh sách liên kết
• B Doubly Linked List - Danh sách liên kết kép
• B Queue - Hàng đợi
• B Stack - Ngăn xếp
• B Hash Table - Bảng băm
• B Heap - Đống - các phiên bản đống lớn nhất và nhỏ nhất
• B Priority Queue - Hàng đợi ưu tiên
• A Trie
• A Tree - Cây
  • A Binary Search Tree - Cây tìm kiếm nhị phân
  • A AVL Tree - Cây AVL
  • A Red-Black Tree - Cây đỏ đen
  • A Segment Tree - Cây phân đoạn - với các ví dụ truy vấn phạm vi tìm min/max/tổng
  • A Fenwick Tree (Binary Indexed Tree) - Cây Fenwick (Cây chỉ số nhị phân)
• A Graph - Đồ thị (cả hai loại có hướng và không hướng)
• A Disjoint Set - Tập hợp rời rạc - cấu trúc dữ liệu hợp nhất–tìm kiếm hoặc tập hợp hợp nhất–tìm kiếm
• A Bloom Filter - Bộ lọc Bloom
• A LRU Cache - Bộ nhớ cache LRU (Least Recently Used)

Thuật toán là một đặc tả không mơ hồ về cách giải quyết một lớp vấn đề. Đó là một tập hợp các quy tắc xác định chính xác một chuỗi các thao tác.

B - Người mới bắt đầu, A - Nâng cao

• Math - Toán học
  • B Bit Manipulation - Thao tác bit - đặt/lấy/cập nhật/xóa bit, nhân/chia cho hai, làm số âm, v.v.
  • B Binary Floating Point - Điểm nổi nhị phân - biểu diễn nhị phân của các số dấu phẩy động.
  • B Factorial - Giai thừa
  • B Fibonacci Number - Số Fibonacci - phiên bản cổ điển và phiên bản công thức đóng
  • B Prime Factors - Thừa số nguyên tố - tìm thừa số nguyên tố và đếm chúng bằng định lý Hardy-Ramanujan
  • B Primality Test - Kiểm tra số nguyên tố (phương pháp chia thử)
  • B Euclidean Algorithm - Thuật toán Euclide - tính Ước số chung lớn nhất (GCD)
  • B Least Common Multiple - Bội số chung nhỏ nhất (LCM)
  • B Sieve of Eratosthenes - Rây Eratosthenes - tìm tất cả các số nguyên tố đến bất kỳ giới hạn nào được đưa ra
  • B Is Power of Two - Kiểm tra lũy thừa của hai - kiểm tra xem số có phải là lũy thừa của hai không (thuật toán ngây thơ và thuật toán bit)
  • B Pascal's Triangle - Tam giác Pascal
  • B Complex Number - Số phức - các số phức và các phép toán cơ bản với chúng
  • B Radian & Degree - Radian và Độ - chuyển đổi radian sang độ và ngược lại
  • B Fast Powering - Luỹ thừa nhanh
  • B Horner's method - Phương pháp Horner - đánh giá đa thức
  • B Matrices - Ma trận - ma trận và các thao tác cơ bản với ma trận (nhân, chuyển vị, v.v.)
  • B Euclidean Distance - Khoảng cách Euclide - khoảng cách giữa hai điểm/vectơ/ma trận
  • A Integer Partition - Phân chia số nguyên
  • A Square Root - Căn bậc hai - phương pháp Newton
  • A Liu Hui π Algorithm - Thuật toán π Liu Hui - tính gần đúng π dựa trên N-gons
  • A Discrete Fourier Transform - Biến đổi Fourier rời rạc - phân tích một hàm thời gian (tín hiệu) thành các tần số tạo thành nó
• Sets - Tập hợp
  • B Cartesian Product - Tích Descartes - sản phẩm của nhiều tập hợp
  • B Fisher–Yates Shuffle - Xáo trộn Fisher–Yates - hoán vị ngẫu nhiên của một chuỗi hữu hạn
  • A Power Set - Tập lực lượng - tất cả các tập con của một tập hợp (các giải pháp dựa trên bit, backtracking và dâng trào)
  • A Permutations - Hoán vị (có và không có lặp lại)
  • A Combinations - Tổ hợp (có và không có lặp lại)
  • A Longest Common Subsequence - Chuỗi con chung dài nhất (LCS)
  • A Longest Increasing Subsequence - Chuỗi tăng dài nhất
  • A Shortest Common Supersequence - Chuỗi chung ngắn nhất (SCS)
  • A Knapsack Problem - Bài toán ba lô - các phiên bản "0/1" và "Không giới hạn"
  • A Maximum Subarray - Mảng con lớn nhất - các phiên bản "Vét cạn" và "Quy hoạch động" (Kadane)
  • A Combination Sum - Tổng các tổ hợp - tìm tất cả các tổ hợp tạo thành tổng cụ thể
• Strings - Chuỗi
  • B Hamming Distance - Khoảng cách Hamming - số lượng vị trí mà các ký tự khác nhau
  • B Palindrome - Chuỗi đối xứng - kiểm tra xem chuỗi có giống nhau khi đảo ngược không
  • A Levenshtein Distance - Khoảng cách Levenshtein - khoảng cách chỉnh sửa tối thiểu giữa hai chuỗi
  • A Knuth–Morris–Pratt Algorithm (KMP Algorithm) - Thuật toán Knuth–Morris–Pratt - tìm kiếm chuỗi con (so khớp mẫu)
  • A Z Algorithm - Thuật toán Z - tìm kiếm chuỗi con (so khớp mẫu)
  • A Rabin Karp Algorithm - Thuật toán Rabin Karp - tìm kiếm chuỗi con
  • A Longest Common Substring - Chuỗi con chung dài nhất
  • A Regular Expression Matching - So khớp biểu thức chính quy
• Searches - Tìm kiếm
  • B Linear Search - Tìm kiếm tuyến tính
  • B Jump Search (or Block Search) - Tìm kiếm nhảy (hoặc Tìm kiếm khối) - tìm kiếm trong mảng đã sắp xếp
  • B Binary Search - Tìm kiếm nhị phân - tìm kiếm trong mảng đã sắp xếp
  • B Interpolation Search - Tìm kiếm nội suy - tìm kiếm trong mảng đã sắp xếp phân bố đều
• Sorting - Sắp xếp
  • B Bubble Sort - Sắp xếp nổi bọt
  • B Selection Sort - Sắp xếp chọn
  • B Insertion Sort - Sắp xếp chèn
  • B Heap Sort - Sắp xếp đống
  • B Merge Sort - Sắp xếp trộn
  • B Quicksort - Sắp xếp nhanh - các phiên bản tại chỗ và không tại chỗ
  • B Shellsort - Sắp xếp Shell
  • B Counting Sort - Sắp xếp đếm
  • B Radix Sort - Sắp xếp theo cơ số
  • B Bucket Sort - Sắp xếp thùng
• Linked Lists - Danh sách liên kết
  • B Straight Traversal - Duyệt thẳng
  • B Reverse Traversal - Duyệt ngược
• Trees - Cây
  • B Depth-First Search - Tìm kiếm theo chiều sâu (DFS)
  • B Breadth-First Search - Tìm kiếm theo chiều rộng (BFS)
• Graphs - Đồ thị
  • B Depth-First Search - Tìm kiếm theo chiều sâu (DFS)
  • B Breadth-First Search - Tìm kiếm theo chiều rộng (BFS)
  • B Kruskal’s Algorithm - Thuật toán Kruskal - tìm Cây bao trùm tối thiểu (MST) cho đồ thị vô hướng có trọng số
  • A Dijkstra Algorithm - Thuật toán Dijkstra - tìm đường đi ngắn nhất đến tất cả các đỉnh đồ thị từ một đỉnh
  • A Bellman-Ford Algorithm - Thuật toán Bellman-Ford - tìm đường đi ngắn nhất đến tất cả các đỉnh đồ thị từ một đỉnh
  • A Floyd-Warshall Algorithm - Thuật toán Floyd-Warshall - tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh
  • A Detect Cycle - Phát hiện chu trình - cho cả đồ thị có hướng và không hướng (các phiên bản dựa trên DFS và Tập hợp rời rạc)
  • A Prim’s Algorithm - Thuật toán Prim - tìm Cây bao trùm tối thiểu (MST) cho đồ thị vô hướng có trọng số
  • A Topological Sorting - Sắp xếp topo - phương pháp DFS
  • A Articulation Points - Điểm nối - thuật toán Tarjan (dựa trên DFS)
  • A Bridges - Cầu - thuật toán dựa trên DFS
  • A Eulerian Path and Eulerian Circuit - Đường đi Euler và Chu trình Euler - thuật toán Fleury - ghé thăm mỗi cạnh một lần
  • A Hamiltonian Cycle - Chu trình Hamilton - ghé thăm mỗi đỉnh một lần
  • A Strongly Connected Components - Thành phần liên thông mạnh - thuật toán Kosaraju
  • A Travelling Salesman Problem - Bài toán người bán hàng du lịch - tuyến đường ngắn nhất có thể ghé thăm mỗi thành phố và trở về thành phố xuất phát
• Cryptography - Mật mã học
  • B Polynomial Hash - Băm đa thức - hàm băm dựa trên đa thức
  • B Rail Fence Cipher - Mật mã hàng rào - thuật toán mật mã hoán vị để mã hóa tin nhắn
  • B Caesar Cipher - Mật mã Caesar - mật mã thay thế đơn giản
  • B Hill Cipher - Mật mã Hill - mật mã thay thế dựa trên đại số tuyến tính
• Machine Learning - Máy học
  • B NanoNeuron - 7 hàm JS đơn giản minh họa cách máy móc có thể học hỏi thực sự (lan truyền tiến/lùi)
  • B k-NN - k-Nearest Neighbors - thuật toán phân loại k láng giềng gần nhất
  • B k-Means - k-Means - thuật toán phân cụm k-Means
• Image Processing - Xử lý ảnh
  • B Seam Carving - Cắt chỉnh sửa nội dung - thuật toán thay đổi kích thước ảnh nhận thức nội dung
• Statistics - Thống kê
  • B Weighted Random - Ngẫu nhiên có trọng số - chọn mục ngẫu nhiên từ danh sách dựa trên trọng số của các mục
• Evolutionary algorithms - Thuật toán tiến hóa
  • A Genetic algorithm - Thuật toán di truyền - ví dụ về cách áp dụng thuật toán di truyền để huấn luyện xe tự đỗ
• Uncategorized - Không phân loại
  • B Tower of Hanoi - Tháp Hà Nội
  • B Square Matrix Rotation - Xoay ma trận vuông - thuật toán tại chỗ
  • B Jump Game - Trò chơi nhảy - các ví dụ về vét cạn, quy hoạch động (trên xuống + dưới lên) và tham lam
  • B Unique Paths - Đường đi độc đáo - các ví dụ về vét cạn, quy hoạch động và Tam giác Pascal
  • B Rain Terraces - Mái hiên mưa - bài toán mắc kẹt nước mưa (quy hoạch động và các phiên bản vét cạn)
  • B Recursive Staircase - Cầu thang đệ quy - đếm số cách để đạt đến đỉnh (4 giải pháp)
  • B Best Time To Buy Sell Stocks - Thời điểm tốt nhất để mua bán cổ phiếu - chia để trị và các ví dụ một lần
  • A N-Queens Problem - Bài toán N quân hậu
  • A Knight's Tour - Chuyến du lịch của hiệp sĩ

Một mô hình thuật toán là một phương pháp chung hoặc cách tiếp cận chung chung cho thiết kế một loạt thuật toán. Nó là một trừu tượng cao hơn so với khái niệm thuật toán, giống như thuật toán là một trừu tượng cao hơn so với chương trình máy tính.

• Brute Force - Vét cạn - xem xét tất cả các khả năng và chọn giải pháp tốt nhất
  • B Linear Search - Tìm kiếm tuyến tính
  • B Rain Terraces - Mái hiên mưa - bài toán mắc kẹt nước mưa
  • B Recursive Staircase - Cầu thang đệ quy - đếm số cách để đạt đến đỉnh
  • A Maximum Subarray - Mảng con lớn nhất
  • A Travelling Salesman Problem - Bài toán người bán hàng du lịch - tuyến đường ngắn nhất có thể ghé thăm mỗi thành phố và trở về thành phố xuất phát
  • A Discrete Fourier Transform - Biến đổi Fourier rời rạc - phân tích một hàm thời gian (tín hiệu) thành các tần số tạo thành nó
• Greedy - Tham lam - chọn giải pháp tốt nhất tại thời điểm hiện tại, mà không cần xem xét đến tương lai
  • B Jump Game - Trò chơi nhảy
  • A Unbound Knapsack Problem - Bài toán ba lô không giới hạn
  • A Dijkstra Algorithm - Thuật toán Dijkstra - tìm đường đi ngắn nhất đến tất cả các đỉnh đồ thị
  • A Prim’s Algorithm - Thuật toán Prim - tìm Cây bao trùm tối thiểu (MST) cho đồ thị vô hướng có trọng số
  • A Kruskal’s Algorithm - Thuật toán Kruskal - tìm Cây bao trùm tối thiểu (MST) cho đồ thị vô hướng có trọng số
• Divide and Conquer - Chia để trị - chia vấn đề thành các phần nhỏ hơn và sau đó giải quyết những phần đó
  • B Binary Search - Tìm kiếm nhị phân
  • B Tower of Hanoi - Tháp Hà Nội
  • B Pascal's Triangle - Tam giác Pascal
  • B Euclidean Algorithm - Thuật toán Euclide - tính Ước số chung lớn nhất (GCD)
  • B Merge Sort - Sắp xếp trộn
  • B Quicksort - Sắp xếp nhanh
  • B Tree Depth-First Search - Tìm kiếm theo chiều sâu cây (DFS)
  • B Graph Depth-First Search - Tìm kiếm theo chiều sâu đồ thị (DFS)
  • B Matrices - Ma trận - tạo và duyệt các ma trận có hình dạng khác nhau
  • B Jump Game - Trò chơi nhảy
  • B Fast Powering - Luỹ thừa nhanh
  • B Best Time To Buy Sell Stocks - Thời điểm tốt nhất để mua bán cổ phiếu - chia để trị và các ví dụ một lần
  • A Permutations - Hoán vị (có và không có lặp lại)
  • A Combinations - Tổ hợp (có và không có lặp lại)
  • A Maximum Subarray - Mảng con lớn nhất
• Dynamic Programming - Quy hoạch động - xây dựng giải pháp sử dụng các tiểu giải pháp đã tìm thấy trước đó
  • B Fibonacci Number - Số Fibonacci
  • B Jump Game - Trò chơi nhảy
  • B Unique Paths - Đường đi độc đáo
  • B Rain Terraces - Mái hiên mưa - bài toán mắc kẹt nước mưa
  • B Recursive Staircase - Cầu thang đệ quy - đếm số cách để đạt đến đỉnh
  • B Seam Carving - Cắt chỉnh sửa nội dung - thuật toán thay đổi kích thước ảnh nhận thức nội dung
  • A Levenshtein Distance - Khoảng cách Levenshtein - khoảng cách chỉnh sửa tối thiểu giữa hai chuỗi
  • A Longest Common Subsequence - Chuỗi con chung dài nhất (LCS)
  • A Longest Common Substring - Chuỗi con chung dài nhất
  • A Longest Increasing Subsequence - Chuỗi tăng dài nhất
  • A Shortest Common Supersequence - Chuỗi chung ngắn nhất
  • A 0/1 Knapsack Problem - Bài toán ba lô 0/1
  • A Integer Partition - Phân chia số nguyên
  • A Maximum Subarray - Mảng con lớn nhất
  • A Bellman-Ford Algorithm - Thuật toán Bellman-Ford - tìm đường đi ngắn nhất đến tất cả các đỉnh đồ thị
  • A Floyd-Warshall Algorithm - Thuật toán Floyd-Warshall - tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh
  • A Regular Expression Matching - So khớp biểu thức chính quy
• Backtracking - tương tự như vét cạn, thử tạo ra tất cả các giải pháp có thể, nhưng mỗi lần bạn tạo ra giải pháp tiếp theo, bạn kiểm tra xem nó có đáp ứng tất cả các điều kiện không và chỉ sau đó mới tiếp tục tạo ra các giải pháp tiếp theo. Nếu không, quay lại và đi theo một hướng khác để tìm giải pháp. Thường thì duyệt không gian trạng thái bằng DFS được sử dụng.
• B Jump Game - Trò chơi nhảy
• B Unique Paths - Đường đi độc đáo
• B Power Set - Tập lực lượng - tất cả các tập con của một tập hợp
• A Hamiltonian Cycle - Chu trình Hamilton - Ghé thăm mỗi đỉnh một lần
• A N-Queens Problem - Bài toán N quân hậu
• A Knight's Tour - Chuyến du lịch của hiệp sĩ
• A Combination Sum - Tổng các tổ hợp - tìm tất cả các tổ hợp tạo thành tổng cụ thể
• Branch & Bound - nhớ giải pháp có chi phí thấp nhất tìm thấy ở mỗi giai đoạn của quá trình backtracking, và sử dụng chi phí của giải pháp có chi phí thấp nhất tìm thấy cho đến nay làm ranh giới dưới về chi phí của giải pháp ít chi phí nhất cho vấn đề, để loại bỏ các giải pháp một phần có chi phí lớn hơn giải pháp có chi phí thấp nhất tìm thấy cho đến nay. Thường thì duyệt không gian trạng thái cây bằng BFS kết hợp với duyệt DFS được sử dụng.

Install all dependencies - Cài đặt tất cả các phụ thuộc

npm install

Run ESLint - Chạy ESLint

Bạn có thể muốn chạy nó để kiểm tra chất lượng mã.

npm run lint

Run all tests - Chạy tất cả các bài kiểm tra

npm test

Run tests by name - Chạy các bài kiểm tra theo tên

npm test -- 'LinkedList'

Troubleshooting - Khắc phục sự cố

Nếu việc linting hoặc kiểm tra thất bại, hãy thử xóa thư mục node_modules và cài đặt lại các gói npm:

rm -rf ./node_modules
npm i

Cũng đảm bảo rằng bạn đang sử dụng phiên bản Node đúng (>=16). Nếu bạn đang sử dụng nvm để quản lý phiên bản Node, bạn có thể chạy nvm use từ thư mục gốc của dự án và phiên bản đúng sẽ được chọn.

Playground - Sân chơi

Bạn có thể chơi với các cấu trúc dữ liệu và thuật toán trong tệp ./src/playground/playground.js và viết các bài kiểm tra cho nó trong ./src/playground/__test__/playground.test.js.

Sau đó chỉ cần chạy lệnh sau để kiểm tra xem mã sân chơi của bạn có hoạt động như mong đợi hay không:

npm test -- 'playground'

• ▶ Cấu trúc dữ liệu và Thuật toán trên YouTube
• ✍🏻 Bản vẽ Cấu trúc dữ liệu

Ký hiệu Big O được sử dụng để phân loại các thuật toán theo cách thời gian chạy hoặc yêu cầu không gian của chúng tăng lên như thế nào khi kích thước đầu vào tăng lên. Trên biểu đồ dưới đây, bạn có thể tìm thấy các trật tự tăng trưởng phổ biến nhất của các thuật toán được chỉ định trong ký hiệu Big O.

Nguồn: Big O Cheat Sheet.

Dưới đây là danh sách một số ký hiệu Big O phổ biến nhất và so sánh hiệu suất của chúng đối với các kích thước dữ liệu đầu vào khác nhau.

Bạn có thể hỗ trợ dự án này qua ❤️️ GitHub hoặc ❤️️ Patreon.

Những người đang tài trợ cho dự án này ∑ = 1

@trekhleb

Thêm một số dự án và bài viết về JavaScript và thuật toán tại trekhleb.dev