Đây là repository về các giải thuật và cấu trúc dữ liệu phổ biến được viết bằng JavaScript.

Mỗi giải thuật sẽ có một folder và file README giải thích cùng các liên kết khác.

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

B - Beginner (Cơ bản), A - Advanced (Nâng cao)

• B Linked List
• B Doubly Linked List
• B Queue
• B Stack
• B Hash Table
• B Heap
• B Priority Queue
• A Trie
• A Tree
  • A Binary Search Tree
  • A AVL Tree
  • A Red-Black Tree
  • A Segment Tree
  • A Fenwick Tree
• A Graph
• A Disjoint Set
• A Bloom Filter

Giải thuật hay thuật toán là một đặc tả rõ ràng về cách giải quyết một vấn đề. Nó là một tập hợp các quy tắc xác định chính xác một chuỗi hoạt động.

B - Beginner (Cơ bản), A - Advanced (Nâng cao)

• Các phép toán (Math)
  • B Bit Manipulation - set/get/cập nhật/xoá bit, nhân/chia hai bit, tạo bit âm etc.
  • B Binary Floating Point - biểu diễn nhị phân của dấu phẩy động.
  • B Factorial
  • B Fibonacci Number - dạng cổ điển và dạng đóng
  • B Prime Factors - tìm thừa số nguyên tố và đếm chúng bằng định lý Hardy-Ramanujan.
  • B Primality Test (kiểm tra nguyên hàm)
  • B Euclidean Algorithm - tìm ước số chung lớn nhất (GCD)
  • B Least Common Multiple - tìm bội số chung nhỏ nhất (LCM)
  • B Sieve of Eratosthenes - tìm tất cả số nguyên tố trong giới hạn được cho.
  • B Is Power of Two - kiểm tra một số có phải luỹ thừa của 2.
  • B Pascal's Triangle - tam giác Pascal.
  • B Complex Number - số phức và các phép toán cơ bản.
  • B Radian & Degree - chuyển từ radian sang độ và ngược lại.
  • B Fast Powering
  • B Horner's method - lược đồ Horner.
  • B Matrices - ma trận và các phép toán cơ bản (cộng, nhân, chuyển đổi, etc.)
  • B Euclidean Distance - khoảng cách giữa hai điểm/vector/ma trận.
  • A Integer Partition
  • A Square Root - phương thức Newton.
  • A Liu Hui π Algorithm - tính gần đúng π dựa trên N-gons
  • A Discrete Fourier Transform - phép biến đổi Fourier.
• Tập hợp (Sets)
  • B Cartesian Product - tích Descartes.
  • B Fisher–Yates Shuffle - thuật toán ngẫu nhiên không trùng.
  • A Power Set - tất cả các tập hợp con của một tập hợp (dùng phương pháp quay lùi)
  • A Permutations (sử dụng và không sử dụng vòng lặp)
  • A Combinations (sử dụng và không sử dụng vòng lặp)
  • A Longest Common Subsequence (LCS)
  • A Longest Increasing Subsequence
  • A Shortest Common Supersequence (SCS)
  • A Knapsack Problem
  • A Maximum Subarray
  • A Combination Sum
• Chuỗi (Strings)
  • B Hamming Distance - khoảng cách Hamming
  • A Levenshtein Distance - khoảng cách Levenshtein
  • A Knuth–Morris–Pratt Algorithm (Thuật toán KMP) - tìm kiếm chuỗi con (so sánh mẫu)
  • A Z Algorithm - tìm kiếm chuỗi con (so sánh mẫu)
  • A Rabin Karp Algorithm - tìm kiếm chuỗi con
  • A Longest Common Substring
  • A Regular Expression Matching
• Thuật toán tìm kiếm (Searches)
  • B Linear Search
  • B Jump Search (or Block Search) - tìm kiếm trong mảng đã sắp xếp.
  • B Binary Search - tìm kiếm trong mảng đã sắp xếp.
  • B Interpolation Search - tìm kiếm trong mảng được sắp xếp được phân phối thống nhất.
• Thuật toán sắp xếp (Sorting)
  • B Bubble Sort
  • B Selection Sort
  • B Insertion Sort
  • B Heap Sort
  • B Merge Sort
  • B Quicksort
  • B Shellsort
  • B Counting Sort
  • B Radix Sort
• Danh sách liên kết (Linked Lists)
  • B Straight Traversal
  • B Reverse Traversal
• Cây (Trees)
  • B Depth-First Search (DFS)
  • B Breadth-First Search (BFS)
• Lưu đồ (Graphs)
  • B Depth-First Search (DFS)
  • B Breadth-First Search (BFS)
  • B Kruskal’s Algorithm - tìm cây con nhỏ nhất của một đồ thị vô hướng có trọng số.
  • A Dijkstra Algorithm - tìm đường đi ngắn nhât của một đồ thị có hướng không trọng số.
  • A Bellman-Ford Algorithm - tính các đường đi ngắn nhất trong một đồ thị có hướng có trọng số
  • A Floyd-Warshall Algorithm - tìm đường đi ngắn nhât của một đồ thị có hướng dựa trên đỉnh trung gian.
  • A Detect Cycle - cho cả đồ thị có hướng và vô hướng (DFS and Disjoint Set based versions)
  • A Prim’s Algorithm - giống thuật toán Kruskal's.
  • A Topological Sorting - phương thức DFS.
  • A Articulation Points - thuật toán của Tarjan(dựa trên DFS)
  • A Bridges
  • A Eulerian Path and Eulerian Circuit - giải thuật Fleury
  • A Hamiltonian Cycle - Đi qua mọi đỉnh chính xác một lần.
  • A Strongly Connected Components - giải thuật Kosaraju
  • A Travelling Salesman Problem - đường đi ngắn nhất qua mọi điểm và trở về vị trí ban đầu.
• Mã hoá
  • B Polynomial Hash - hàm băm dựa trên đa thức
  • B Rail Fence Cipher - mã hoá bằng phương pháp chuyển vị.
  • B Caesar Cipher - mã hoá bằng phương pháp thay thế.
  • B Hill Cipher - má hoá bằng phương pháp tuyến tính.
• Máy học
  • B NanoNeuron - 7 hàm JS đơn giản minh họa cách máy móc thực sự có thể học (truyền tiến / lùi)
  • B k-NN - thuật toán K láng giềng gần nhất
  • B k-Means - thuật toán phân cụm k-Means
• Xứ lý hình ảnh
  • B Seam Carving - thuật toán thay đổi kích thước hình ảnh.
• Khác
  • B Tower of Hanoi - bài toán tháp Hà Nội.
  • B Square Matrix Rotation
  • B Jump Game - ví dụ về giải thuât quay lùi, tham lam và quy hoạch động.
  • B Unique Paths - ví dụ về giải thuật quay lùi, quy hoạch động và tam giác Pascal.
  • B Rain Terraces -
  • B Recursive Staircase - đếm số cách đi hết cầu thang (4 giải pháp)
  • B Best Time To Buy Sell Stocks - ví dụ về chia để trị.
  • A N-Queens Problem - bài toán N quân hậu.
  • A Knight's Tour - bài toán ngựa đi đường.

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

• Phá mã Brute Force - 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
  • B Rain Terraces
  • B Recursive Staircase
  • A Maximum Subarray
  • A Travelling Salesman Problem
  • A Discrete Fourier Transform - biến đổi Fourier.
• Giải thuật tham lam - chọn phương án tốt nhất tại thời điểm hiện tại mà không cần cân nhắc đến các lựa chọn khác trong tương lai.
  • B Jump Game
  • A Unbound Knapsack Problem
  • A Dijkstra Algorithm
  • A Prim’s Algorithm
  • A Kruskal’s Algorithm
• Giải thuật chia để trị - chia nhỏ vấn đề và giải quyết các phần nhỏ đấy.
  • B Binary Search
  • B Tower of Hanoi
  • B Pascal's Triangle
  • B Euclidean Algorithm
  • B Merge Sort
  • B Quicksort
  • B Tree Depth-First Search (DFS)
  • B Graph Depth-First Search (DFS)
  • B Matrices -tạo và duyệt các ma trận có hình dạng khác nhau.
  • B Jump Game
  • B Fast Powering
  • B Best Time To Buy Sell Stocks
  • A Permutations
  • A Combinations
• Quy hoạch động - xây dựng một giải pháp bằng cách sử dụng các giải pháp phụ đã tìm thấy trước đây.
  • B Fibonacci Number
  • B Jump Game
  • B Unique Paths
  • B Rain Terraces
  • B Recursive Staircase
  • B Seam Carving -
  • A Levenshtein Distance
  • A Longest Common Subsequence (LCS)
  • A Longest Common Substring
  • A Longest Increasing Subsequence
  • A Shortest Common Supersequence
  • A 0/1 Knapsack Problem
  • A Integer Partition
  • A Maximum Subarray
  • A Bellman-Ford Algorithm
  • A Floyd-Warshall Algorithm
  • A Regular Expression Matching
• Giải thuật quay lùi - tương tự brute force ta cũng tìm tất cả các khả năng nhưng trong quá trình tìm kiếm, nếu ta gặp một hướng lựa chọn không thỏa mãn, ta quay lui về điểm lựa chọn nơi có các hướng khác và thử hướng lựa chọn tiếp theo. Khi đã thử hết các lựa chọn xuất phát từ điểm lựa chọn đó, ta quay lại điểm lựa chọn trước đó và thử hướng lựa chọn tiếp theo tại đó. Quá trình tìm kiếm thất bại khi không còn điểm lựa chọn nào nữa
  • B Jump Game
  • B Unique Paths
  • B Power Set
  • A Hamiltonian Cycle
  • A N-Queens Problem
  • A Knight's Tour
  • A Combination Sum
• Giải thuật nhánh cận - ghi nhớ giải pháp chi phí thấp nhất được tìm thấy ở mỗi giai đoạn của tìm kiếm quay lùi, và sử dụng chi phí của giải pháp chi phí thấp nhất được tìm thấy như là một ràng buộc thấp hơn về chi phí của một giải pháp chi phí thấp nhất cho vấn đề, để loại bỏ các giải pháp với chi phí lớn hơn giải pháp chi phí thấp nhất được tìm thấy cho đến nay.

Ký hiệu 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 phát triển 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 hầu hết các thứ tự tăng trưởng phổ biến của các thuật toán được chỉ định trong ký hiệu Big O.

Source: Big O Cheat Sheet.

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

▶ Data Structures and Algorithms on YouTube

Repostiry gốc