javascript-algorithms

Tài liệu luyện tập kiến thức cấu trúc dữ liệu và thuật toán về Javascript

🔖 Gợi ý từ Admin

📝 Tài liệu phỏng vấn kiến thức lập trình: Xem tại đây!!!

📌 Tìm hiểu về thuật toán: Xem tại đây!!!

📌 Roadmaps - Lộ trình trở thành một lập trình viên: Xem tại đây!!!

⚡️ Cheatsheet các ngôn ngữ lập trình: Xem tại đây!!!

⚡️ Handbook lập trình: Xem tại đây!!!

Mẹo

Bạn có thể tìm tất cả thông tin (tài liệu, công cụ...) thông qua núttìm kiếm 🔍ở góc trên bên phải màn hình.

---

Thông tin

Đây là một Github repository về cấu trúc dữ liệu và thuật toán trong JavaScript.

Các bạn có thể truy cập vào Github javascript-algorithms để xem đầy đủ hơn.

Phiên bản tiếng việt bạn có thể xem tại đây

Hãy tặng họ 1 ⭐️ nếu bạn yêu thích repo này !

1. Cấu trúc dữ liệu

Cấu trúc dữ liệu là một cách cụ thể để 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 hàm hoặc phép toán có thể được áp dụng cho dữ liệu.

B - Cơ bản, A - Nâng cao

• B Danh sách liên kết
• B Danh sách liên kết đôi
• B Hàng đợi
• B Ngăn xếp
• B Bảng băm
• B Đống - max và min heap
• B Hàng đợi ưu tiên
• A Cây tiền tố
• A Cây
• A Cây tìm kiếm nhị phân
• A Cây AVL
• A Cây đỏ đen
• A Cây phân đoạn - với các ví dụ truy vấn phạm vi nhỏ nhất/lớn nhất/tổng
• A Cây Fenwick (Cây chỉ mục nhị phân)
• A Đồ thị (có hướng và vô hướng)
• A Tập hợp không giao nhau
• A Bộ lọc Bloom

2. Thuật toán

Thuật toán là một đặc tả rõ ràng về cách giải quyết một lớp 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 phép toán.

B - Cơ bản, A - Nâng cao

Thuật toán theo chủ đề

Toán

• B Thao tác bit - đặt/lấy/cập nhật/xóa bit, nhân/chia 2, đổi dấu âm,...
• B Giai thừa
• B Số Fibonacci - cổ điển và dạng đóng
• B Thừa số nguyên tố - tìm và đếm thừa số nguyên tố sử dụng định luật Hardy-Ramanujan's
• B Kiểm tra tính nguyên tố (phân chia thử nghiệm)
• B Thuật toán Euclid - tính ước số chung lớn nhất (GCD)
• B Bội số chung nhỏ nhất (LCM)
• B Sàng số nguyên tố - tìm tất cả các số nguyên tố trong bất kỳ phạm vi nhất định nào
• B Xác định lũy thừa của 2 - kiểm tra xem số có phải là lũy thừa của 2 hay không (thuật toán nguyên bản và theo bit)
• B Tam giác Pascal
• B Số phức - số phức và các phép toán cơ bản với số phức
• B Radian & độ - chuyển đổi giữa đơn vị radian và độ
• B Tính nhanh lũy thừa
• B Phương pháp Horner's - tính giá trị đa thức
• B Ma trận - ma trận và các phép toán cơ bản (phép nhân, phép chuyển vị,...)
• B Khoảng cách Euclid - khoảng cách giữa hai điểm/véc-tơ/ma trận
• A Phân hoạch
• A Căn bậc hai - phương pháp Newton
• A Thuật cắt đường tròn - Lưu Huy - phép tính gần đúng số π dựa vào đa giác
• A Biến đổi Fourier rời rạc - phân giải tín hiệu thời gian thành các tần số tạo nên tín hiệu đó

Tập hợp

• B Tích Đề-các - tích của nhiều tập hợp
• B Thuật toán xáo trộn - dãy hữu hạn hoán vị ngẫu nhiên
• A Tập lũy thừa - tập hợp chứa tất cả các tập con (theo bit và quay lui)
• A Hoán vị (lặp và không lặp)
• A Tổ hợp (lặp và không lặp)
• A Dãy con chung dài nhất (LCS)
• A Dãy con chung tăng dần dài nhất
• A Dãy con chung ngắn nhất (SCS)
• A Bài toán xếp ba lô - dạng 0-1 và không bị chặn
• A Mảng con lớn nhất - phiên bản vét cạn và quy hoạch động (Kadane)
• A Tổ hợp của tổng - tìm tất cả các tổ hợp tạo thành tổng cụ thể

Chuỗi

• B Khoảng cách Hamming - số các vị trí các ký hiệu khác nhau
• A Khoảng cách Levenshtein - khoảng cách thay đổi nhỏ nhất giữa hai chuỗi ký tự
• A Thuật toán Knuth–Morris–Pratt (thuật toán KMP) - tìm chuỗi con (đối sánh mẫu)
• A Thuật toán Z - tìm chuỗi con (đối sánh mẫu)
• A Thuật toán Rabin Karp - tìm chuỗi con
• A Xâu con chung dài nhất
• A Phối biểu thức chính quy

Tìm kiếm

• B Tìm kiếm tuyến tính
• B Tìm kiếm nhảy (tìm khối) - tìm kiếm trong mảng đã sắp xếp
• B Tìm kiếm nhị phân - tìm kiếm trong mảng đã sắp xếp
• B Tìm kiếm nội suy - Tìm kiếm strong mảng có thứ tự được phân phối đồng nhất

Sắp xếp

• B Sắp xếp nổi bọt
• B Sắp xếp chọn
• B Sắp xếp chèn
• B Sắp xếp vun đống
• B Sắp xếp trộn
• B Sắp xếp nhanh - Tại chỗ và không tại chỗ
• B Shellsort
• B Sắp xếp đếm
• B Sắp xếp theo cơ số

Danh sách liên kết

• B Di chuyển chính hướng
• B Di chuyển ngược hướng

Cây

• B Depth-First Search (DFS)
• B Breadth-First Search (BFS)

Đồ thị

• B Tìm kiếm theo chiều sâu (DFS)
• B Tìm kiếm theo chiều rộng (BFS)
• B Thuật toán Kruskal - tìm cây bao trùm nhỏ nhất (MST) cho đồ thị vô hướng có trọng số
• A Thuật toán Dijkstra Algorithm - tìm những đường ngắn nhất từ một định tới tất cả các đỉnh
• A Thuật toán Bellman-Ford - tìm những đường ngắn nhất từ một đỉnh tới tất cả các đỉnh của đồ thị
• A Thuật toán Floyd-Warshall - tìm những đường ngắn nhất giữa tất cả các cặp đỉnh
• A Phát hiện vòng - cho cả đồ thị có hướng và vô hướng (dựa trên DFS và tập không giao)
• A Thuật toán Prim - tìm cây bao trùm nhỏ nhất (MST) cho đồ thị vô hướng có trọng số
• A Sắp xếp tô pô - phương pháp DFS
• A Điểm khớp - Thuật toán Tarjan (dựa trên DFS)
• A Cầu nối - dựa trên DFS
• A Đường đi Euler và Chu trình Euler - thuật toán Fleury - đi qua các cạnh chỉ một lần duy nhất
• A Chu trình Hamilton - đi qua các đỉnh chỉ một lần duy nhất
• A Các thành phần kết nối chặt - Thuật toán Kosaraju
• A Bài toán người bán hàng - tuyến đường ngắn nhất có thể đến thăm từng thành phố và trở về thành phố gốc

Mật mã học

• B Băm đa thức - lăn hàm băm dựa trên đa thức
• B Mật mã hàng rào đường sắt - một thuật toán mật mã chuyển vị để mã hóa thông điệp
• B Mật mã Caesar - mật mã chuyển vị đơn giản
• B Mật mã Hill - mật mã chuyển vị đơn giản dựa trên đại số tuyến tính

Học máy

• B NanoNeuron - 7 hàm JS đơn giản minh họa cách máy tính thực sự có thể học (truyền thuận / truyền ngược)
• B k-NN - thuật toán phân loại k láng giềng gần nhất
• B k-Means - thuật toán phân cụm k-Means

Khác

• B Tháp Hà Nội
• B Xoay ma trận vuông - thuật toán tại chỗ
• B Trò chơi nhảy - ví dụ quay lui, quy hoạch động (từ trên xuống + từ dưới lên), dynamic programming (top-down + bottom-up) và tham lam
• B Các đường đi đặc trưng duy nhất - ví dụ quay lui, quy hoạch động và tam giác Pascal
• B Thu thập nước mưa - bài toán bẫy nước mưa (phiên bản quy hoạch động và vét cạn)
• B Cầu thang đệ quy - đếm số cách lên đến đỉnh (4 lời giải)
• B Thời điểm tốt nhất để mua bán cổ phiếu - ví dụ chia để trị và một đường chuyền
• A Bài toán n quân hậu
• A Mã đi tuần

Thuật toán theo mẫu hình

Mẫu 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à một sự trừu tượng cao hơn một chương trình máy tính.

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 Tìm kiếm tuyến tính
• B Thu thập nước mưa - bài toán bẫy nước mưa
• B Cầu thang đệ quy - đếm số cách lên đến đỉnh
• A Mảng con lớn nhất
• A Bài toán người bán hàng - tuyến đường ngắn nhất có thể đến thăm từng thành phố và trở về thành phố gốc
• A Biến đổi Fourier rời rạc - phân giải tín hiệu thời gian thành các tần số tạo nên tín hiệu đó

Tham lam - chọn phương án tốt nhất vào thời điểm hiện tại mà không cần cân nhắc đến tương lai

• B Trò chơi nhảy
• A Bài xếp ba lô không bị chặn
• A Thuật toán Dijkstra - tìm những đường ngắn nhất từ một định tới tất cả các đỉnh
• A Thuật toán Prim - tìm cây bao trùm nhỏ nhất (MST) cho đồ thị vô hướng có trọng số
• A Thuật toán Kruskal - tìm cây bao trùm nhỏ nhất (MST) cho đồ thị vô hướng có trọng số

Chia để trị - chia vấn đề thành các phần nhỏ hơn rồi giải quyết các phần đó

• B Tìm kiếm nhị phân
• B Tháp Hà Nội
• B Tam giác Pascal
• B Thuật toán Euclid - tính ước số chung lớn nhất
• B Sắp xếp trộn
• B Sắp xếp nhanh
• B Cây tìm kiếm theo chiều sâu (DFS)
• B Đồ thị tìm kiếm theo chiều sâu (DFS)
• B Ma trận - tạo và duyệt các ma trận có kích thước khác nhau
• B Trò chơi nhảy
• B Tính nhanh lũy thừa
• B Thời điểm tốt nhất để mua bán cổ phiếu - ví dụ chia để trị và một đường chuyền
• A Hoán vị (lặp và không lặp)
• A Tổ hợp (lặp và không lặp)

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 Số Fibonacci
• B Trò chơi nhảy
• B Đường đi độc nhất
• B Thu thập nước mưa - bài toán bẫy nước mưa
• B Cầu thang đệ quy - đếm số cách lên đến đỉnh
• A Khoảng cách Levenshtein - khoảng cách thay đổi nhỏ nhất giữa hai chuỗi ký tự
• A Dãy con chung dài nhất (LCS)
• A Xâu con chung dài nhất
• A Dãy con chung tăng dần dài nhất
• A Dãy con chung ngắn nhất
• A Bài xếp ba lô dạng 0-1
• A Integer Partition
• A Mảng con lớn nhất
• A Thuật toán Bellman-Ford - tìm những đường ngắn nhất từ một đỉnh tới tất cả các đỉnh của đồ thị
• A Thuật toán Floyd-Warshall - tìm những đường ngắn nhất giữa tất cả các cặp đỉnh
• A Phối biểu thức chính quy

Quay lui - tương tự như vét cạn, cố 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 sẽ kiểm tra xem nó có thỏa mãn tất cả các điều kiện hay không và chỉ khi thỏa mãn mới tiếp tục tạo ra các giải pháp tiếp theo. Nếu không, hãy quay lại và đi trên một con đường khác để tìm ra giải pháp. Thông thường, truyền DFS của không gian trạng thái được sử dụng.

• B Trò chơi nhảy
• B Đường đi độc nhất
• B Tập lũy thừa - tập hợp chứa tất cả các tập con
• A Chu trình Hamilton - đi qua các đỉnh một lần duy nhất
• A Bài toán n quân hậu
• A Mã đi tuần
• A Tổ hợp của tổng - tìm tất cả các tổ hợp tạo thành tổng cụ thể

Branch & Bound - ghi nhớ giải pháp chi với phí thấp nhất được tìm thấy ở mỗi giai đoạn của quá trình tìm kiếm quay lui, sử dụng chi phí của giải pháp có chi phí thấp nhất được tìm thấy cho đến nay như một giới hạn dưới về chi phí của một giải pháp ít chi phí nhân cho bài toán, để loại bỏ các giải pháp từng phần 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. Thông thường BFS duyệt kết hợp với duyệt DFS của cây không gian trạng thái đang được sử dụng.

--- Còn tiếp ---

Các bạn có thể truy cập vào Github javascript-algorithms để xem đầy đủ hơn.

Phiên bản tiếng việt bạn có thể xem tại đây