Repository files navigation

Kho lưu trữ này chứa các ví dụ dựa trên JavaScriptvề 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 READMEriê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

• BLinked List - Danh sách liên kết
• BDoubly Linked List - Danh sách liên kết kép
• BQueue - Hàng đợi
• BStack - Ngăn xếp
• BHash Table - Bảng băm
• BHeap - Đống - các phiên bản đống lớn nhất và nhỏ nhất
• BPriority Queue - Hàng đợi ưu tiên
• ATrie
• ATree - Cây
  • ABinary Search Tree - Cây tìm kiếm nhị phân
  • AAVL Tree - Cây AVL
  • ARed-Black Tree - Cây đỏ đen
  • ASegment 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
  • AFenwick Tree (Binary Indexed Tree) - Cây Fenwick (Cây chỉ số nhị phân)
• AGraph - Đồ thị (cả hai loại có hướng và không hướng)
• ADisjoint 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
• ABloom Filter - Bộ lọc Bloom
• ALRU 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
  • BBit 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.
  • BBinary 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.
  • BFactorial - Giai thừa
  • BFibonacci Number - Số Fibonacci - phiên bản cổ điển và phiên bản công thức đóng
  • BPrime 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
  • BPrimality Test - Kiểm tra số nguyên tố (phương pháp chia thử)
  • BEuclidean Algorithm - Thuật toán Euclide - tính Ước số chung lớn nhất (GCD)
  • BLeast Common Multiple - Bội số chung nhỏ nhất (LCM)
  • BSieve 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
  • BIs 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)
  • BPascal's Triangle - Tam giác Pascal
  • BComplex Number - Số phức - các số phức và các phép toán cơ bản với chúng
  • BRadian & Degree - Radian và Độ - chuyển đổi radian sang độ và ngược lại
  • BFast Powering - Luỹ thừa nhanh
  • BHorner's method - Phương pháp Horner - đánh giá đa thức
  • BMatrices - 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.)
  • BEuclidean Distance - Khoảng cách Euclide - khoảng cách giữa hai điểm/vectơ/ma trận
  • AInteger Partition - Phân chia số nguyên
  • ASquare Root - Căn bậc hai - phương pháp Newton
  • ALiu Hui π Algorithm - Thuật toán π Liu Hui - tính gần đúng π dựa trên N-gons
  • ADiscrete 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
  • BCartesian Product - Tích Descartes - sản phẩm của nhiều tập hợp
  • BFisher–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
  • APower 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)
  • APermutations - Hoán vị (có và không có lặp lại)
  • ACombinations - Tổ hợp (có và không có lặp lại)
  • ALongest Common Subsequence - Chuỗi con chung dài nhất (LCS)
  • ALongest Increasing Subsequence - Chuỗi tăng dài nhất
  • AShortest Common Supersequence - Chuỗi chung ngắn nhất (SCS)
  • AKnapsack Problem - Bài toán ba lô - các phiên bản "0/1" và "Không giới hạn"
  • AMaximum Subarray - Mảng con lớn nhất - các phiên bản "Vét cạn" và "Quy hoạch động" (Kadane)
  • ACombination 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
  • BHamming Distance - Khoảng cách Hamming - số lượng vị trí mà các ký tự khác nhau
  • BPalindrome - Chuỗi đối xứng - kiểm tra xem chuỗi có giống nhau khi đảo ngược không
  • ALevenshtein Distance - Khoảng cách Levenshtein - khoảng cách chỉnh sửa tối thiểu giữa hai chuỗi
  • AKnuth–Morris–Pratt Algorithm (KMP Algorithm) - Thuật toán Knuth–Morris–Pratt - tìm kiếm chuỗi con (so khớp mẫu)
  • AZ Algorithm - Thuật toán Z - tìm kiếm chuỗi con (so khớp mẫu)
  • ARabin Karp Algorithm - Thuật toán Rabin Karp - tìm kiếm chuỗi con
  • ALongest Common Substring - Chuỗi con chung dài nhất
  • ARegular Expression Matching - So khớp biểu thức chính quy
• Searches - Tìm kiếm
  • BLinear Search - Tìm kiếm tuyến tính
  • BJump 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
  • BBinary Search - Tìm kiếm nhị phân - tìm kiếm trong mảng đã sắp xếp
  • BInterpolation 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
  • BBubble Sort - Sắp xếp nổi bọt
  • BSelection Sort - Sắp xếp chọn
  • BInsertion Sort - Sắp xếp chèn
  • BHeap Sort - Sắp xếp đống
  • BMerge Sort - Sắp xếp trộn
  • BQuicksort - Sắp xếp nhanh - các phiên bản tại chỗ và không tại chỗ
  • BShellsort - Sắp xếp Shell
  • BCounting Sort - Sắp xếp đếm
  • BRadix Sort - Sắp xếp theo cơ số
  • BBucket Sort - Sắp xếp thùng
• Linked Lists - Danh sách liên kết
  • BStraight Traversal - Duyệt thẳng
  • BReverse Traversal - Duyệt ngược
• Trees - Cây
  • BDepth-First Search - Tìm kiếm theo chiều sâu (DFS)
  • BBreadth-First Search - Tìm kiếm theo chiều rộng (BFS)
• Graphs - Đồ thị
  • BDepth-First Search - Tìm kiếm theo chiều sâu (DFS)
  • BBreadth-First Search - Tìm kiếm theo chiều rộng (BFS)
  • BKruskal’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ố
  • ADijkstra 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
  • ABellman-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
  • AFloyd-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
  • ADetect 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)
  • APrim’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ố
  • ATopological Sorting - Sắp xếp topo - phương pháp DFS
  • AArticulation Points - Điểm nối - thuật toán Tarjan (dựa trên DFS)
  • ABridges - Cầu - thuật toán dựa trên DFS
  • AEulerian 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
  • AHamiltonian Cycle - Chu trình Hamilton - ghé thăm mỗi đỉnh một lần
  • AStrongly Connected Components - Thành phần liên thông mạnh - thuật toán Kosaraju
  • ATravelling 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
  • BPolynomial Hash - Băm đa thức - hàm băm dựa trên đa thức
  • BRail 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
  • BCaesar Cipher - Mật mã Caesar - mật mã thay thế đơn giản
  • BHill 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
  • BNanoNeuron - 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)
  • Bk-NN - k-Nearest Neighbors - thuật toán phân loại k láng giềng gần nhất
  • Bk-Means - k-Means - thuật toán phân cụm k-Means
• Image Processing - Xử lý ảnh
  • BSeam 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ê
  • BWeighted 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
  • AGenetic 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
  • BTower of Hanoi - Tháp Hà Nội
  • BSquare Matrix Rotation - Xoay ma trận vuông - thuật toán tại chỗ
  • BJump 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
  • BUnique Paths - Đường đi độc đáo - các ví dụ về vét cạn, quy hoạch động và Tam giác Pascal
  • BRain 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)
  • BRecursive Staircase - Cầu thang đệ quy - đếm số cách để đạt đến đỉnh (4 giải pháp)
  • BBest 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
  • AN-Queens Problem - Bài toán N quân hậu
  • AKnight'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
  • BLinear Search - Tìm kiếm tuyến tính
  • BRain Terraces - Mái hiên mưa - bài toán mắc kẹt nước mưa
  • BRecursive Staircase - Cầu thang đệ quy - đếm số cách để đạt đến đỉnh
  • AMaximum Subarray - Mảng con lớn nhất
  • ATravelling 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
  • ADiscrete 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
  • BJump Game - Trò chơi nhảy
  • AUnbound Knapsack Problem - Bài toán ba lô không giới hạn
  • ADijkstra Algorithm - Thuật toán Dijkstra - tìm đường đi ngắn nhất đến tất cả các đỉnh đồ thị
  • APrim’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ố
  • AKruskal’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 đó
  • BBinary Search - Tìm kiếm nhị phân
  • BTower of Hanoi - Tháp Hà Nội
  • BPascal's Triangle - Tam giác Pascal
  • BEuclidean Algorithm - Thuật toán Euclide - tính Ước số chung lớn nhất (GCD)
  • BMerge Sort - Sắp xếp trộn
  • BQuicksort - Sắp xếp nhanh
  • BTree Depth-First Search - Tìm kiếm theo chiều sâu cây (DFS)
  • BGraph Depth-First Search - Tìm kiếm theo chiều sâu đồ thị (DFS)
  • BMatrices - Ma trận - tạo và duyệt các ma trận có hình dạng khác nhau
  • BJump Game - Trò chơi nhảy
  • BFast Powering - Luỹ thừa nhanh
  • BBest 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
  • APermutations - Hoán vị (có và không có lặp lại)
  • ACombinations - Tổ hợp (có và không có lặp lại)
  • AMaximum 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 đó
  • BFibonacci Number - Số Fibonacci
  • BJump Game - Trò chơi nhảy
  • BUnique Paths - Đường đi độc đáo
  • BRain Terraces - Mái hiên mưa - bài toán mắc kẹt nước mưa
  • BRecursive Staircase - Cầu thang đệ quy - đếm số cách để đạt đến đỉnh
  • BSeam 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
  • ALevenshtein Distance - Khoảng cách Levenshtein - khoảng cách chỉnh sửa tối thiểu giữa hai chuỗi
  • ALongest Common Subsequence - Chuỗi con chung dài nhất (LCS)
  • ALongest Common Substring - Chuỗi con chung dài nhất
  • ALongest Increasing Subsequence - Chuỗi tăng dài nhất
  • AShortest Common Supersequence - Chuỗi chung ngắn nhất
  • A0/1 Knapsack Problem - Bài toán ba lô 0/1
  • AInteger Partition - Phân chia số nguyên
  • AMaximum Subarray - Mảng con lớn nhất
  • ABellman-Ford Algorithm - Thuật toán Bellman-Ford - tìm đường đi ngắn nhất đến tất cả các đỉnh đồ thị
  • AFloyd-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
  • ARegular 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.
• BJump Game - Trò chơi nhảy
• BUnique Paths - Đường đi độc đáo
• BPower Set - Tập lực lượng - tất cả các tập con của một tập hợp
• AHamiltonian Cycle - Chu trình Hamilton - Ghé thăm mỗi đỉnh một lần
• AN-Queens Problem - Bài toán N quân hậu
• AKnight's Tour - Chuyến du lịch của hiệp sĩ
• ACombination 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ướivề 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ụcnode_modules và cài đặt lại các gói npm:

rm -rf ./node_modulesnpm 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ụngnvm để quản lý phiên bản Node, bạn có thể chạynvm 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.jsvà 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ạitrekhleb.dev