Bỏ qua

Sắp xếp, Tìm kiếm, và Thiết kế Thuật toán

Sắp xếp và tìm kiếm là những thao tác thuật toán cơ bản nhất. Tệp này trình bày các thuật toán sắp xếp, các mẫu tìm kiếm nhị phân, chia để trị, thuật toán tham lam, quy hoạch động, và quay lui.

  • Mọi cấu trúc dữ liệu đều hỗ trợ các thuật toán, và mọi thuật toán đều dựa vào cấu trúc dữ liệu. Tệp này trình bày các mô hình thiết kế (design paradigms): các chiến thuật cấp cao để giải quyết bài toán. Một khi bạn nhận ra mô hình nào áp dụng, việc cài đặt sẽ theo sau một cách tự nhiên.

Các Thuật toán Sắp xếp

  • Sắp xếp là bài toán được nghiên cứu nhiều nhất trong khoa học máy tính. Hiểu các thuật toán xây dựng trực giác về đệ quy, chia để trị, và phân tích độ phức tạp.
Thuật toán Tốt nhất Trung bình Xấu nhất Không gian Ổn định?
Sắp xếp nổi bọt (Bubble sort) \(O(n)\) \(O(n^2)\) \(O(n^2)\) \(O(1)\) Có
Sắp xếp chèn (Insertion sort) \(O(n)\) \(O(n^2)\) \(O(n^2)\) \(O(1)\) Có
Sắp xếp trộn (Merge sort) \(O(n \log n)\) \(O(n \log n)\) \(O(n \log n)\) \(O(n)\) Có
Sắp xếp nhanh (Quick sort) \(O(n \log n)\) \(O(n \log n)\) \(O(n^2)\) \(O(\log n)\) Không
Sắp xếp đống (Heap sort) \(O(n \log n)\) \(O(n \log n)\) \(O(n \log n)\) \(O(1)\) Không
Sắp xếp đếm (Counting sort) \(O(n + k)\) \(O(n + k)\) \(O(n + k)\) \(O(k)\) Có
Sắp xếp cơ số (Radix sort) \(O(d(n + k))\) \(O(d(n + k))\) \(O(d(n + k))\) \(O(n + k)\) Có

  • Ổn định (Stable) nghĩa là các phần tử bằng nhau giữ nguyên thứ tự tương đối. Điều này quan trọng khi sắp xếp theo nhiều khóa.

  • Cận dưới (lower bound) cho sắp xếp dựa trên so sánh là \(\Omega(n \log n)\). Chứng minh dùng cây quyết định (chương 13): mọi phép sắp xếp so sánh phải phân biệt tất cả \(n!\) hoán vị, đòi hỏi ít nhất \(\log_2(n!) = \Omega(n \log n)\) lần so sánh. Sắp xếp đếm và sắp xếp cơ số đánh bại cận này bằng cách không so sánh các phần tử.

Sắp xếp Trộn (Merge Sort)

  • Chia đôi mảng, đệ quy sắp xếp từng nửa, rồi trộn các nửa đã sắp xếp. \(O(n \log n)\) luôn, \(O(n)\) không gian thêm.
def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])

    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:  # <= để ổn định
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result
  • Cạm bẫy: dùng < thay vì <= trong phép trộn phá vỡ tính ổn định (các phần tử bằng nhau từ nửa phải sẽ đứng trước những phần tử từ nửa trái).

Sắp xếp Nhanh (Quick Sort)

  • Chọn một trục (pivot), phân hoạch các phần tử thành "nhỏ hơn trục" và "lớn hơn trục", đệ quy sắp xếp từng phân hoạch. \(O(n \log n)\) trung bình, \(O(n^2)\) trường hợp xấu nhất (khi trục luôn là phần tử nhỏ nhất hoặc lớn nhất).
def quicksort(arr, lo=0, hi=None):
    if hi is None:
        hi = len(arr) - 1
    if lo >= hi:
        return

    pivot_idx = partition(arr, lo, hi)
    quicksort(arr, lo, pivot_idx - 1)
    quicksort(arr, pivot_idx + 1, hi)

def partition(arr, lo, hi):
    pivot = arr[hi]  # Lomuto: trục là phần tử cuối
    i = lo
    for j in range(lo, hi):
        if arr[j] < pivot:
            arr[i], arr[j] = arr[j], arr[i]
            i += 1
    arr[i], arr[hi] = arr[hi], arr[i]
    return i

  • Chiến thuật chọn trục: phần tử cuối (đơn giản, tệ với đầu vào đã sắp xếp), ngẫu nhiên (kỳ vọng \(O(n \log n)\)), trung vị-của-ba (lựa chọn thực tế). Luôn ưu tiên trục ngẫu nhiên trong phỏng vấn để tránh thảo luận trường hợp xấu nhất.

  • Cạm bẫy: trường hợp xấu nhất \(O(n^2)\) của quicksort xảy ra trên các mảng đã sắp xếp với trục đầu/cuối. Trong thực tế, trục ngẫu nhiên hoặc trung vị-của-ba loại bỏ điều này.

Sắp xếp Đếm (Counting Sort)

  • Khi các giá trị là số nguyên trong một phạm vi đã biết \([0, k)\), đếm số lần xuất hiện và tái tạo lại: thời gian \(O(n + k)\). Không dựa trên so sánh, nên nó có thể đánh bại \(O(n \log n)\).
def counting_sort(arr, k):
    count = [0] * k
    for x in arr:
        count[x] += 1
    result = []
    for val in range(k):
        result.extend([val] * count[val])
    return result
  • Khi nào dùng: phạm vi \(k\) không lớn hơn nhiều so với \(n\). Nếu \(k = O(n)\), đây là \(O(n)\). Nếu \(k \gg n\) (ví dụ, sắp xếp 10 số trong phạm vi \([0, 10^9]\)), sắp xếp đếm lãng phí bộ nhớ.

  • Tìm kiếm nhị phân tìm một mục tiêu trong một mảng đã sắp xếp trong \(O(\log n)\) bằng cách liên tục chia đôi không gian tìm kiếm. Nhưng tìm kiếm nhị phân còn hơn cả "tìm một số trong mảng đã sắp xếp." Mẫu tổng quát là: tìm kiếm trên một điều kiện đơn điệu.

  • Khuôn mẫu (cái tránh được lỗi lệch một đơn vị):

def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1

    while lo <= hi:
        mid = lo + (hi - lo) // 2  # tránh tràn số trong các ngôn ngữ khác
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1

    return -1  # không tìm thấy
  • Cận dưới (lower bound) (phần tử đầu tiên \(\geq\) mục tiêu):
def lower_bound(arr, target):
    lo, hi = 0, len(arr)
    while lo < hi:
        mid = (lo + hi) // 2
        if arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo
  • Cạm bẫy: sự khác biệt giữa lo <= hi và lo < hi, và giữa hi = mid và hi = mid - 1, quyết định liệu bạn tìm thấy khớp chính xác hay biên giới. Hãy vẽ với một mảng 2 phần tử để kiểm chứng.

Dễ: Tìm kiếm Nhị phân

  • Bài toán chuẩn. Dùng khuôn mẫu ở trên.

Trung bình: Tìm kiếm trong Mảng Đã Sắp xếp Bị Xoay (Search in Rotated Soted Array)

  • Bài toán: một mảng đã sắp xếp bị xoay tại một trục nào đó. Tìm một mục tiêu.

  • Mẫu: ở mỗi bước, luôn có một nửa đã sắp xếp. Xác định nửa nào đã sắp xếp, và kiểm tra xem mục tiêu có nằm trong nửa đó không.

def search_rotated(nums, target):
    lo, hi = 0, len(nums) - 1

    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid

        # nửa trái đã sắp xếp
        if nums[lo] <= nums[mid]:
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        # nửa phải đã sắp xếp
        else:
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1
            else:
                hi = mid - 1

    return -1
  • Cạm bẫy: dấu <= trong nums[lo] <= nums[mid] (không phải <) là then chốt. Khi lo == mid (còn 2 phần tử), ta phải xác định đúng nửa đã sắp xếp.

Khó: Trung vị của Hai Mảng Đã Sắp xếp (Median of Two Sorted Arrays)

  • Bài toán: tìm trung vị của hai mảng đã sắp xếp trong \(O(\log(m + n))\).

  • Mẫu: tìm kiếm nhị phân trên điểm phân hoạch của mảng ngắn hơn. Phân hoạch chia cả hai mảng sao cho mọi phần tử bên trái đều nhỏ hơn mọi phần tử bên phải.

def find_median(nums1, nums2):
    if len(nums1) > len(nums2):
        nums1, nums2 = nums2, nums1  # đảm bảo nums1 ngắn hơn
    m, n = len(nums1), len(nums2)
    lo, hi = 0, m
    half = (m + n + 1) // 2

    while lo <= hi:
        i = (lo + hi) // 2          # điểm phân hoạch trong nums1
        j = half - i                 # điểm phân hoạch trong nums2

        left1 = nums1[i - 1] if i > 0 else float('-inf')
        right1 = nums1[i] if i < m else float('inf')
        left2 = nums2[j - 1] if j > 0 else float('-inf')
        right2 = nums2[j] if j < n else float('inf')

        if left1 <= right2 and left2 <= right1:
            # phân hoạch đúng
            if (m + n) % 2 == 1:
                return max(left1, left2)
            return (max(left1, left2) + min(right1, right2)) / 2
        elif left1 > right2:
            hi = i - 1
        else:
            lo = i + 1
  • Đây là một trong những bài toán tìm kiếm nhị phân khó nhất. Hiểu biết then chốt là bạn không tìm kiếm một giá trị mà tìm một điểm phân hoạch thỏa mãn một điều kiện.

Siêu Mẫu: Tìm kiếm Nhị phân trên Đáp án (Binary Search on Answer)

  • Nhiều bài toán trông không giống tìm kiếm nhị phân có thể được giải bằng cách tìm kiếm nhị phân trên đáp án. Nếu đáp án là một con số, và bạn có thể viết một hàm is_feasible(x) đơn điệu (True với mọi \(x \geq\) tối ưu, hoặc False với mọi \(x \geq\) tối ưu), thì hãy tìm kiếm nhị phân trên \(x\).

  • Ví dụ: "sức chứa tối thiểu của một con tàu để giao tất cả hàng trong \(d\) ngày là bao nhiêu?" Tìm kiếm nhị phân trên sức chứa. Với mỗi sức chứa ứng viên, kiểm tra tham lam xem mọi gói hàng có thể được giao trong \(d\) ngày không.

def ship_within_days(weights, days):
    lo, hi = max(weights), sum(weights)

    while lo < hi:
        mid = (lo + hi) // 2
        # có thể giao với sức chứa mid trong <= days không?
        current_load, num_days = 0, 1
        for w in weights:
            if current_load + w > mid:
                num_days += 1
                current_load = 0
            current_load += w

        if num_days <= days:
            hi = mid
        else:
            lo = mid + 1

    return lo

Mẫu: Các Thuật toán Tham lam (Greedy Algorithms)

  • Một thuật toán tham lam (greedy) đưa ra lựa chọn tối ưu cục bộ tại mỗi bước, hy vọng điều này dẫn đến lời giải tối ưu toàn cục. Tham lam hoạt động khi bài toán có tính chất lựa chọn tham lam (tối ưu cục bộ dẫn đến tối ưu toàn cục) và cấu trúc tối ưu (lời giải tối ưu chứa các lời giải tối ưu của bài toán con).

Trung bình: Trò chơi Nhảy (Jump Game)

  • Bài toán: cho một mảng где nums[i] là độ dài nhảy tối đa tại vị trí \(i\), xác định xem bạn có thể đến được chỉ số cuối cùng không.
def can_jump(nums):
    max_reach = 0
    for i, jump in enumerate(nums):
        if i > max_reach:
            return False  # không thể đến được vị trí này
        max_reach = max(max_reach, i + jump)
    return True
  • Tại sao tham lam hoạt động: ta chỉ cần biết vị trí xa nhất có thể đến được. Nếu vị trí hiện tại vượt quá tầm với xa nhất, ta bị kẹt. Ngược lại, ta cập nhật tầm với xa nhất.

Trung bình: Trộn các Khoảng (Merge Intervals)

  • Bài toán: trộn các khoảng chồng lấp.
def merge_intervals(intervals):
    intervals.sort(key=lambda x: x[0])
    merged = [intervals[0]]

    for start, end in intervals[1:]:
        if start <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])

    return merged

  • Mẫu: sắp xếp theo thời gian bắt đầu, rồi trộn tham lam. Nếu khoảng hiện tại chồng lấp với khoảng đã trộn cuối, hãy mở rộng nó. Ngược lại, bắt đầu một khoảng đã trộn mới.

  • Cạm bẫy: dùng merged[-1][1] = end thay vì merged[-1][1] = max(merged[-1][1], end). Một khoảng có thể hoàn toàn nằm trong một khoảng khác (ví dụ, [1, 10] và [2, 5]).

Mẫu: Quy hoạch Động (Dynamic Programming)

  • Quy hoạch động (DP) giải quyết các bài toán bằng cách chia chúng thành các bài toán con chồng chéo, giải mỗi bài toán con một lần, và lưu kết quả. Nó hoạt động khi một bài toán có cấu trúc tối ưu và các bài toán con chồng chéo.

  • Hai cách tiếp cận:

    • Từ trên xuống (memoisation): viết lời giải đệ quy tự nhiên, rồi lưu kết quả vào một từ điển.
    • Từ dưới lên (tabulation): xây dựng một bảng từ các bài toán con nhỏ nhất trở lên.

  • Cách nhận diện DP: bài toán yêu cầu một giá trị tối ưu (min/max), đếm, hoặc sự tồn tại, và quyết định hiện tại phụ thuộc vào các quyết định trước. Nếu bạn vẽ cây đệ quy và thấy các bài toán con lặp lại, đó là DP.

Dễ: Cầu thang (Climbing Stairs)

  • Bài toán: \(n\) bậc thang, bạn có thể leo 1 hoặc 2 bậc mỗi lần. Có bao nhiêu cách khác nhau?

  • Đây là Fibonacci: \(f(n) = f(n-1) + f(n-2)\).

def climb_stairs(n):
    if n <= 2:
        return n
    a, b = 1, 2
    for _ in range(3, n + 1):
        a, b = b, a + b
    return b
  • \(O(n)\) thời gian, \(O(1)\) không gian. Bảng ghi nhớ đầy đủ không cần thiết vì mỗi trạng thái chỉ phụ thuộc vào hai trạng thái trước.

Trung bình: Đổi tiền (Coin Change)

  • Bài toán: cho các mệnh giá tiền và một số tiền mục tiêu, tìm số lượng đồng tiền tối thiểu cần thiết.

  • Trạng thái: dp[amount] = số đồng tiền tối thiểu để tạo ra amount.

  • Chuyển trạng thái: dp[amount] = min(dp[amount - coin] + 1) cho mỗi đồng tiền.
  • Trường hợp cơ sở: dp[0] = 0.
def coin_change(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0

    for a in range(1, amount + 1):
        for coin in coins:
            if coin <= a and dp[a - coin] + 1 < dp[a]:
                dp[a] = dp[a - coin] + 1

    return dp[amount] if dp[amount] != float('inf') else -1
  • Cạm bẫy: khởi tạo bằng float('inf') (không phải 0 hay -1). Phép so sánh cực tiểu chỉ hoạt động nếu các trạng thái không thể đến được là vô cực.

Trung bình: Dãy con Chung Dài nhất (Longest Common Subsequence)

  • Bài toán: cho hai chuỗi, tìm độ dài của dãy con chung dài nhất.

  • Trạng thái: dp[i][j] = LCS của text1[:i] và text2[:j].

  • Chuyển trạng thái: nếu text1[i-1] == text2[j-1], thì dp[i][j] = dp[i-1][j-1] + 1. Ngược lại, dp[i][j] = max(dp[i-1][j], dp[i][j-1]).
def longest_common_subsequence(text1, text2):
    m, n = len(text1), len(text2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i - 1] == text2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    return dp[m][n]

Khó: Ba lô 0/1 (0/1 Knapsack)

  • Bài toán: cho các vật phẩm có trọng lượng và giá trị, và một dung lượng \(W\), cực đại hóa tổng giá trị mà không vượt quá \(W\).

  • Trạng thái: dp[i][w] = giá trị lớn nhất dùng \(i\) vật phẩm đầu tiên với dung lượng \(w\).

  • Chuyển trạng thái: dp[i][w] = max(dp[i-1][w], dp[i-1][w - weight[i]] + value[i]) (bỏ qua hoặc lấy vật phẩm \(i\)).
def knapsack(weights, values, capacity):
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for w in range(capacity + 1):
            dp[i][w] = dp[i - 1][w]  # bỏ qua vật phẩm i
            if weights[i - 1] <= w:
                dp[i][w] = max(dp[i][w],
                               dp[i - 1][w - weights[i - 1]] + values[i - 1])

    return dp[n][capacity]
  • Tối ưu không gian: vì mỗi hàng chỉ phụ thuộc vào hàng trước, hãy dùng một mảng 1D và lặp \(w\) từ phải sang trái:
def knapsack_optimised(weights, values, capacity):
    dp = [0] * (capacity + 1)
    for i in range(len(weights)):
        for w in range(capacity, weights[i] - 1, -1):  # phải sang trái!
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    return dp[capacity]
  • Cạm bẫy: lặp từ trái sang phải trong bản 1D cho phép dùng vật phẩm \(i\) nhiều lần (ba lô không bị chặn). Phải sang trái đảm bảo mỗi vật phẩm được dùng nhiều nhất một lần.

Mẫu: Quay lui (Backtracking)

  • Quay lui là tìm kiếm toàn bộ có cắt tỉa. Xây dựng một lời giải tăng dần, và bỏ cuộc (quay lui) ngay khi lời giải một phần không thể dẫn đến một lời giải hoàn chỉnh hợp lệ.

  • Khuôn mẫu:

def backtrack(candidates, path, result):
    if is_solution(path):
        result.append(path[:])  # copy!
        return

    for candidate in get_candidates(path):
        if is_valid(candidate, path):
            path.append(candidate)     # choose
            backtrack(candidates, path, result)  # explore
            path.pop()                 # unchoose (backtrack)

Trung bình: Các Tập con (Subsets)

def subsets(nums):
    result = []
    def backtrack(start, path):
        result.append(path[:])
        for i in range(start, len(nums)):
            path.append(nums[i])
            backtrack(i + 1, path)
            path.pop()
    backtrack(0, [])
    return result

Trung bình: Tổng Hợp (Combination Sum)

  • Bài toán: tìm mọi tổ hợp không trùng lặp có tổng bằng một mục tiêu (các phần tử có thể được tái sử dụng).
def combination_sum(candidates, target):
    result = []
    def backtrack(start, path, remaining):
        if remaining == 0:
            result.append(path[:])
            return
        for i in range(start, len(candidates)):
            if candidates[i] > remaining:
                break  # cắt tỉa: đã sắp xếp, nên mọi ứng viên tiếp theo đều quá lớn
            path.append(candidates[i])
            backtrack(i, path, remaining - candidates[i])  # i, không i+1: cho phép tái sử dụng
            path.pop()

    candidates.sort()  # sắp xếp để cắt tỉa
    backtrack(0, [], target)
    return result
  • Cạm bẫy: backtrack(i, ...) cho phép tái sử dụng cùng một phần tử. backtrack(i + 1, ...) sẽ chuyển sang phần tử tiếp theo (không tái sử dụng). Sai sót ở đây là lỗi quay lui phổ biến nhất.

Khó: N-Queens

  • Bài toán: đặt \(n\) quân hậu trên một bàn cờ \(n \times n\) sao cho không có hai quân nào tấn công nhau.
def solve_n_queens(n):
    result = []
    cols = set()
    pos_diag = set()  # (row + col) là hằng số trên đường chéo /
    neg_diag = set()  # (row - col) là hằng số trên đường chéo \

    board = [['.'] * n for _ in range(n)]

    def backtrack(row):
        if row == n:
            result.append([''.join(r) for r in board])
            return

        for col in range(n):
            if col in cols or (row + col) in pos_diag or (row - col) in neg_diag:
                continue

            cols.add(col)
            pos_diag.add(row + col)
            neg_diag.add(row - col)
            board[row][col] = 'Q'

            backtrack(row + 1)

            cols.remove(col)
            pos_diag.remove(row + col)
            neg_diag.remove(row - col)
            board[row][col] = '.'

    backtrack(0)
    return result
  • Hiểu biết then chốt: mã hóa đường chéo. Đối với đường chéo /, row + col là hằng số. Đối với đường chéo \, row - col là hằng số. Dùng các tập hợp để theo dõi cột và đường chéo làm cho kiểm tra tính hợp lệ thành \(O(1)\).

Tóm tắt các Cạm bẫy Thường gặp

Cạm bẫy Ví dụ Sửa
lo <= hi so với lo < hi trong tìm kiếm nhị phân Lệch một đơn vị trong biên Chọn dựa trên việc hi là bao gồm hay loại trừ
Ba lô 1D trái-sang-phải Vật phẩm được dùng nhiều lần Lặp phải-sang-trái cho ba lô 0/1
Không copy đường dẫn trong quay lui result.append(path) — mọi mục đều trỏ vào cùng danh sách result.append(path[:]) hoặc path.copy()
backtrack(i) so với backtrack(i+1) Tái sử dụng hay không tái sử dụng phần tử Khớp với đề bài
Thiếu break trong quay lui đã sắp xếp Khám phá các ứng viên quá lớn Sắp xếp + break khi ứng viên vượt quá remaining
Khởi tạo DP dp[0] sai → mọi giá trị sau đều sai Định nghĩa cẩn thận trường hợp cơ sở
Tham lam không chứng minh Tham lam không phải lúc nào cũng đúng Xác minh tính chất lựa chọn tham lam
Sắp xếp không ổn định cho đa khóa Mất thứ tự tương đối của các phần tử bằng nhau Dùng sắp xếp ổn định (merge sort, sorted của Python)

Bài tập Tự luyện (NeetCode)

Tìm kiếm Nhị phân

Tham lam

Quy hoạch Động

Quay lui