Các thuật toán python
Các thuật toán và kỹ thuật quan trọng trong Python, ứng dụng khi đi thi học sinh giỏi, cấp quốc gia
8Sau khi thành thạo for, while, List và Hàm, học viên nên tiếp tục học các kỹ thuật xử lý dữ liệu dưới đây. Đây là những kỹ thuật xuất hiện rất nhiều trong các kỳ thi lập trình và phỏng vấn.
1. Prefix Sum (Mảng cộng dồn)
Mục đích: Tính tổng một đoạn trong danh sách rất nhanh.
A = [2, 4, 1, 5, 3]
preSum = [0]
for x in A:
preSum.append(preSum[-1] + x)
print(preSum)
# Tổng từ chỉ số 1 đến 3
print(preSum[4] - preSum[1])Ứng dụng:
- Tính tổng từ L đến R.
- Tính tổng nhiều lần.
- Sliding Window.
- Binary Search.
2. Frequency Array (Mảng đếm)
Mục đích: Đếm số lần xuất hiện của từng số.
A = [2,4,2,3,2,1]
dem = [0] * 10
for x in A:
dem[x] += 1
print(dem)
print("Số 2 xuất hiện:", dem[2])Ứng dụng:
- Đếm số lần xuất hiện.
- Tìm số xuất hiện nhiều nhất.
- Kiểm tra dữ liệu trùng.
3. Sliding Window (Cửa sổ trượt)
Mục đích: Tìm tổng lớn nhất hoặc nhỏ nhất của một đoạn liên tiếp.
A = [2,4,1,5,3]
k = 3
tong = sum(A[:k])
lonNhat = tong
for i in range(k, len(A)):
tong = tong - A[i-k] + A[i]
lonNhat = max(lonNhat, tong)
print(lonNhat)
Ứng dụng:
- Tìm đoạn có tổng lớn nhất.
- Tìm đoạn có tổng nhỏ nhất.
- Xử lý chuỗi.
4. Two Pointers (Hai con trỏ)
Mục đích: Duyệt hai đầu của danh sách để giảm số lần lặp.
A = [1,2,3,5,7,9]
L = 0
R = len(A)-1
while L < R:
s = A[L] + A[R]
if s == 10:
print(A[L], A[R])
break
elif s < 10:
L += 1
else:
R -= 1
Ứng dụng:
- Tìm hai số có tổng bằng X.
- Tìm đoạn thỏa điều kiện.
- Tăng tốc thuật toán.
5. Binary Search (Tìm kiếm nhị phân)
Mục đích: Tìm kiếm cực nhanh trên danh sách đã sắp xếp.
A = [2,4,6,8,10,12]
x = 8
L = 0
R = len(A)-1
while L <= R:
mid = (L+R)//2
if A[mid] == x:
print("Tìm thấy")
break
elif A[mid] < x:
L = mid + 1
else:
R = mid - 1
Ứng dụng:
- Tìm kiếm.
- Tối ưu đáp án.
- Thuật toán O(log n).
6. Dictionary (Hash Map)
Mục đích: Lưu dữ liệu theo dạng khóa và giá trị.
A = [2,4,2,3,2,1]
dem = {}
for x in A:
dem[x] = dem.get(x,0)+1
print(dem)
Ứng dụng:
- Đếm số lần xuất hiện.
- Tra cứu rất nhanh.
- Thống kê dữ liệu.
7. Sort (Sắp xếp)
Mục đích: Sắp xếp dữ liệu.
A = [5,2,8,1,3]
A.sort()
print(A)Ứng dụng:
- Sắp xếp tăng dần.
- Sắp xếp giảm dần.
- Chuẩn bị cho Binary Search.
8. Greedy (Thuật toán tham lam)
Mục đích: Luôn chọn phương án tốt nhất ở hiện tại.
tien = 6800
for to in [5000,2000,1000,500,200,100]:
print(to, ":", tien // to)
tien %= toỨng dụng:
- Đổi tiền.
- Chọn công việc.
- Tối ưu số bước.
9. DFS (Depth First Search)
Mục đích: Duyệt đồ thị theo chiều sâu.
graph = {
1:[2,3],
2:[4],
3:[],
4:[]
}
def dfs(u):
print(u)
for v in graph[u]:
dfs(v)
dfs(1)
Ứng dụng:
- Duyệt cây.
- Duyệt mê cung.
- Tìm đường.
10. BFS (Breadth First Search)
Mục đích: Duyệt đồ thị theo từng tầng.
from collections import deque
graph = {
1:[2,3],
2:[4],
3:[],
4:[]
}
q = deque([1])
while q:
u = q.popleft()
print(u)
for v in graph[u]:
q.append(v)
Ứng dụng:
- Tìm đường ngắn nhất.
- Duyệt cây.
- Duyệt đồ thị.
11. Dynamic Programming (Quy hoạch động)
Mục đích: Lưu kết quả đã tính để không tính lại.
n = 10
dp = [0]*(n+1)
dp[1]=1
for i in range(2,n+1):
dp[i]=dp[i-1]+dp[i-2]
print(dp[n])
Ứng dụng:
- Fibonacci.
- Tối ưu chi phí.
- Balo (Knapsack).
12. Difference Array (Mảng hiệu)
Mục đích: Cập nhật nhanh giá trị trên một đoạn.
A = [0,0,0,0,0]
diff = [0]*6
diff[1] += 3
diff[4] -= 3
for i in range(1,5):
diff[i] += diff[i-1]
print(diff[:-1])
Ứng dụng:
- Cộng nhiều đoạn liên tiếp.
- Tăng tốc xử lý dữ liệu lớn.
Lộ trình học đề xuất
- for, while
- List
- String
- Hàm (Function)
- Prefix Sum
- Frequency Array
- Sliding Window
- Two Pointers
- Dictionary (Hash Map)
- Binary Search
- Sort
- Greedy
- DFS
- BFS
- Dynamic Programming
- Difference Array
Gợi ý: Nếu mục tiêu là thi học sinh giỏi hoặc thi lập trình, hãy ưu tiên học thật chắc Prefix Sum, Sliding Window, Two Pointers, Dictionary và Binary Search trước khi chuyển sang các thuật toán nâng cao.
- Cài và code Python trong vòng 10 phút
- Tài liệu Python (PDF) miễn phí
- Phần mềm lập trình python mà coder nên dùng
- Cú pháp Python
- Comment trong Python
- Cách in ra màn hình python
- Một số ký tự đặc biệt trong Python
- Làm việc với chuỗi trong Python
- Hàm print trong python
- Nguyên lý cấp phát bộ nhớ cho biến trong Python
- Biến và kiểu dữ liệu trong Python
- Ép kiểu dữ liệu trong Python
- Kiểu ngày trong Python
- Hàm input trong python
- Mệnh đề so sánh trong Python
- Biểu thức trong Python
- Câu lệnh if trong Python
- Vòng lặp Python
- Một số hàm toán học trong python
- Các hàm xử lý chuỗi trong Python
- Hàm trong Python
- Phân biệt hai kiểu hàm trong python để hiểu bản chất
- Mảng trong Python
- Dictionary trong Python
- Quản lý file và thư mục trong Python
- Lập trình hướng đối tượng trong Python
- Quản lý lỗi trong Python
- Trí tuệ nhân tạo với Python
- Lập trình Web với Python
- Hồi quy tuyến tính trong Python là gì ?
- Số thực và số nguyên trong Python
- Sai lệch số thực trong Python
- Khi nào dùng from datetime import datetime , khi nào import datetime trong python
- So sánh del và pop() trong biển kiểu danh sách Python
- Tạo ứng dụng nhận diện khuôn mặt bằng Python
- Tạo ứng dụng Chatbot bằng Python
- Tuples và Sets trong Python
- Mẹo học Python hiệu quả
- Xử lý ngoại lệ (Exception Handling) trong Python
- Khóa học Python miễn phí
- MicroPython là gì ?
- Cấu hình IIS với python
- Pseudocode - Thuật toán mã giả trong Python
- Đề thi Python
- Tạo số ngẫu nhiên trong Python
- Phân biệt hàm và phương thức trong Python
- Hàm strip trong Python
- Lambda trong Python
- if rút gọn trong python
- Hàm map trong Python
- So sánh sort và sorted trong python
- Một số thuật toán tìm kiếm
- Các thuật toán python
Các thuật toán và kỹ thuật quan trọng trong Python, ứng dụng khi đi thi học sinh giỏi, cấp quốc gia
