Giới Thiệu: Chinh Phục LeetCode Với Các Mẫu
LeetCode có thể khiến bạn cảm thấy như đang leo một dãy núi đầy khó khăn, với hàng trăm bài toán lập trình tưởng chừng không thể giải quyết. Nhưng nếu mình nói với bạn rằng có cách để vượt qua thử thách này một cách hiệu quả hơn? Bí quyết nằm ở việc nhận diện những mẫu lặp đi lặp lại. Như lập trình viên dày dặn kinh nghiệm Sahil đã chia sẻ trong video YouTube của anh ấy, làm chủ một vài mẫu cơ bản có thể giúp bạn giải quyết một phần lớn các bài toán LeetCode. Bài viết này sẽ phân tích 8 mẫu cần thiết, cung cấp giải thích, ví dụ và mẹo để giúp bạn nâng cao kỹ năng giải quyết vấn đề cho kỳ phỏng vấn lập trình sắp tới.
Mẫu 1: Sliding Window
Khái Niệm: Mẫu Sliding Window là lựa chọn của bạn khi làm việc với các cấu trúc dữ liệu tuyến tính (mảng, chuỗi, danh sách liên kết) và bạn cần tìm một đoạn con (một “cửa sổ”) thỏa mãn điều kiện đã cho. Nghĩ nó như một cửa sổ trượt qua dữ liệu của bạn, mỗi lần một phần tử.
Khi Nào Sử Dụng:
- Tìm chuỗi/consecutive substring/mảng con dài nhất/ngắn nhất thỏa mãn một điều kiện.
- Các bài toán liên quan đến dãy liên tiếp.
Ví Dụ: Chuỗi Con Dài Nhất Với K Ký Tự Đặc Biệt
Pseudocode:
function longestSubstringKUnique(str, k) {
windowStart = 0;
maxLength = 0;
charFrequency = {}; // Theo dõi tần suất ký tự trong cửa sổ
for (windowEnd = 0; windowEnd < str.length; windowEnd++) {
rightChar = str[windowEnd];
// Thêm rightChar vào charFrequency
while (Object.keys(charFrequency).length > k) {
// Thu nhỏ cửa sổ nếu có quá k ký tự đặc biệt
leftChar = str[windowStart];
// Xóa leftChar khỏi charFrequency
windowStart++;
}
maxLength = Math.max(maxLength, windowEnd - windowStart + 1); // Cập nhật độ dài max
}
return maxLength;
}
Ví Dụ Python:
def longest_substring_k_unique(s, k):
window_start = 0
max_length = 0
char_frequency = {}
for window_end in range(len(s)):
right_char = s[window_end]
char_frequency[right_char] = char_frequency.get(right_char, 0) + 1
while len(char_frequency) > k:
left_char = s[window_start]
char_frequency[left_char] -= 1
if char_frequency[left_char] == 0:
del char_frequency[left_char]
window_start += 1
max_length = max(max_length, window_end - window_start + 1)
return max_length
Mẫu 2: Subsets (Kết Hợp/Hoán Vị)
Khái Niệm: Mẫu này xử lý việc tìm tất cả các kết hợp hoặc hoán vị của các phần tử trong một tập hợp.
Khi Nào Sử Dụng:
- Tạo tất cả các tập con của một tập hợp.
- Tìm tất cả các hoán vị của một chuỗi hoặc mảng.
- Các bài toán liên quan đến kết hợp với hoặc không có lặp lại.
Ví Dụ: Hoán Vị Của Một Chuỗi
Cách Tiếp Cận Khái Niệm: Xây dựng các tập con lần lượt theo từng cấp độ, giống như tìm kiếm theo chiều rộng (BFS).
Ví Dụ Python:
def permute(nums):
if not nums:
return []
result = []
perms = [[]]
for num in nums:
new_perms = []
for perm in perms:
for i in range(len(perm) + 1):
new_perms.append(perm[:i] + [num] + perm[i:])
perms = new_perms
return perms
Mẫu 3: Tìm Kiếm Nhị Phân Sửa Đổi
Khái Niệm: Điều chỉnh thuật toán tìm kiếm nhị phân kinh điển để xử lý các biến thể như mảng đã quay, tìm phần tử gần nhất, hoặc xử lý trùng lặp.
Khi Nào Sử Dụng:
- Tìm kiếm trong các mảng đã sắp xếp, thậm chí khi có các sửa đổi như quay.
- Tìm phần tử gần nhất với giá trị mục tiêu.
- Các bài toán mà không gian tìm kiếm có thể giảm một nửa hiệu quả.
Ví Dụ: Tìm Kiếm Trong Mảng Đã Quay
Ý Tưởng Chính: Sửa đổi tìm kiếm nhị phân để xác định nửa mảng nào đã được sắp xếp và điều chỉnh tìm kiếm sao cho hợp lý.
Ví Dụ Python:
def search_rotated(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
if nums[left] <= nums[mid]:
if nums[left] <= target < nums[mid]:
right = mid - 1
else:
left = mid + 1
else:
if nums[mid] < target <= nums[right]:
left = mid + 1
else:
right = mid - 1
return -1
Mẫu 4: Các Phần Tử K Lớn Nhất
Khái Niệm: Tìm các phần tử k lớn nhất, nhỏ nhất, hay xuất hiện nhiều nhất trong một tập dữ liệu.
Khi Nào Sử Dụng:
- Tìm
kphần tử lớn nhất theo một tiêu chí cụ thể. - Các bài toán liên quan đến xếp hạng hoặc chọn một tập con của các phần tử.
Ví Dụ: Số Lớn Thứ K Trong Một Mảng
Giải Pháp Sử Dụng Min-Heap:
- Duy trì một min-heap có kích thước
k. - Lặp qua mảng. Với mỗi số, thêm nó vào heap.
- Nếu kích thước heap vượt quá
k, xóa phần tử nhỏ nhất (gốc của heap). - Sau khi lặp, gốc heap sẽ là phần tử lớn thứ k.
Ví Dụ Python:
import heapq
def find_kth_largest(nums, k):
min_heap = []
for num in nums:
heapq.heappush(min_heap, num)
if len(min_heap) > k:
heapq.heappop(min_heap)
return min_heap[0]
Mẫu 5: Tìm Kiếm Cây Nhị Phân Sâu (DFS)
Khái Niệm: Duyệt qua một cây nhị phân bằng cách khám phá càng xa càng tốt mỗi nhánh trước khi quay lại. Thường sử dụng đệ quy.
Khi Nào Sử Dụng:
- Các bài toán liên quan đến duyệt cây, tìm kiếm đường đi, hoặc tính toán các thuộc tính của nút.
- Duyệt theo thứ tự trước, giữa và sau.
Ví Dụ: Độ Sâu Tối Đa Của Cây Nhị Phân
Giải Pháp (Đệ Quy):
class TreeNode {
val: number;
left: TreeNode | null;
right: TreeNode | null;
constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
this.val = val === undefined ? 0 : val;
this.left = left === undefined ? null : left;
this.right = right === undefined ? null : right;
}
}
function maxDepth(root: TreeNode | null): number {
if (!root) {
return 0;
}
return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}
Ví Dụ Python:
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def maxDepth(root):
if not root:
return 0
return 1 + max(maxDepth(root.left), maxDepth(root.right))
Mẫu 6: Sắp Xếp Topological
Khái Niệm: Sắp xếp các phần tử trong đồ thị vô hướng có hướng (DAG) theo thứ tự phụ thuộc của chúng. Nếu có một cạnh có hướng từ nút A đến nút B, thì A phải đứng trước B trong thứ tự.
Khi Nào Sử Dụng:
- Các bài toán liên quan đến các yêu cầu hoặc phụ thuộc.
- Lịch trình công việc, hệ thống xây dựng và giải quyết phụ thuộc.
Ví Dụ: Lịch Trình Các Khóa Học
Cách Tiếp Cận Khái Niệm:
- Xây dựng đồ thị phụ thuộc (danh sách kề).
- Tính toán bậc vào (số cạnh đến) cho mỗi nút.
- Bắt đầu từ các nút có bậc vào bằng 0.
- Xử lý các nút này, loại bỏ các cạnh ra và giảm bậc vào của các nút kế tiếp.
- Lặp lại bước 4 cho đến khi tất cả các nút được xử lý.
Ví Dụ Python:
from collections import defaultdict, deque
def canFinish(numCourses, prerequisites):
graph = defaultdict(list)
in_degree = [0] * numCourses
for course, prereq in prerequisites:
graph[prereq].append(course)
in_degree[course] += 1
queue = deque([course for course in range(numCourses) if in_degree[course] == 0])
order = []
while queue:
course = queue.popleft()
order.append(course)
for next_course in graph[course]:
in_degree[next_course] -= 1
if in_degree[next_course] == 0:
queue.append(next_course)
return len(order) == numCourses
Mẫu 7: Tìm Kiếm Cây Nhị Phân Chiều Rộng (BFS)
Khái Niệm: Duyệt qua cây nhị phân theo từng cấp, sử dụng hàng đợi.
Khi Nào Sử Dụng:
- Các bài toán liên quan đến duyệt theo thứ tự cấp.
- Tìm đường đi ngắn nhất trong đồ thị không trọng số.
Ví Dụ: Duyệt Cây Nhị Phân Theo Cấp
Cách Tiếp Cận Khái Niệm:
- Dùng hàng đợi để lưu trữ các nút ở mỗi cấp.
- Bắt đầu với nút gốc trong hàng đợi.
- Trong khi hàng đợi chưa rỗng:
- Loại bỏ một nút.
- Xử lý nút đó.
- Thêm con của nó vào hàng đợi.
Ví Dụ Python:
from collections import deque
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def levelOrder(root):
if not root:
return []
result = []
queue = deque([root])
while queue:
level_size = len(queue)
current_level = []
for _ in range(level_size):
node = queue.popleft()
current_level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(current_level)
return result
Mẫu 8: Hai Con Trỏ
Khái Niệm: Sử dụng hai con trỏ để duyệt qua một mảng đã sắp xếp hoặc danh sách liên kết, thường di chuyển chúng về phía nhau hoặc đi xa nhau dựa trên một điều kiện cụ thể.
Khi Nào Sử Dụng:
- Các bài toán liên quan đến việc tìm cặp hoặc bộ ba thỏa mãn điều kiện trong mảng đã sắp xếp.
- Đảo ngược mảng hoặc danh sách liên kết tại chỗ.
Ví Dụ: Hai Tổng (giả sử mảng đầu vào đã sắp xếp)
Giải Pháp:
function twoSum(nums: number[], target: number): number[] | null {
let left = 0;
let right = nums.length - 1;
while (left < right) {
const sum = nums[left] + nums[right];
if (sum === target) {
return [left, right];
} else if (sum < target) {
left++;
} else {
right--;
}
}
return null;
}
Ví Dụ Python:
def two_sum(nums, target):
left, right = 0, len(nums) - 1
while left < right:
current_sum = nums[left] + nums[right]
if current_sum == target:
return [left, right]
elif current_sum < target:
left += 1
else:
right -= 1
return None
Kết Luận: Luyện Tập Để Hoàn Hảo
8 mẫu này là công cụ mạnh mẽ trong bộ công cụ LeetCode của bạn. Nhớ rằng, hiểu rõ các khái niệm cơ bản và luyện tập áp dụng các mẫu này là rất quan trọng. Đừng chỉ ghi nhớ các giải pháp; hãy tập trung vào việc nhận diện khi nào một mẫu cụ thể có thể được sử dụng. Giờ thì đi và chinh phục những thử thách lập trình thôi! 🚀