Bài viết này sẽ giới thiệu về các thuật toán và cấu trúc dữ liệu quan trọng trong Python, bao gồm các phương pháp như hai con trỏ, chia để trị, và quy hoạch động.

Phương Pháp Hai Con Trỏ

Phương pháp hai con trỏ (two pointers) là một kỹ thuật hiệu quả để giải quyết nhiều vấn đề liên quan đến mảng hoặc chuỗi. Có hai loại chính: con trỏ cùng hướng (đồng hướng) và con trỏ đối đầu (đối hướng).

Hai Con Trỏ Đồng Hướng

def two_pointers_same_direction(arr):
    dau, cuoi = 0, 0
    while cuoi < len(arr):
        # Xử lý logic tại đây
        cuoi += 1
    return result

Hai Con Trỏ Đối Đầu

def two_pointers_opposite_direction(arr):
    dau, cuoi = 0, len(arr) - 1
    while dau < cuoi:
        # Xử lý logic tại đây
        dau += 1
        cuoi -= 1
    return result

Chia Để Trị và Nhị Phân Tìm Kiếm

Nhị phân tìm kiếm (binary search) là một kỹ thuật tìm kiếm hiệu quả trên danh sách đã sắp xếp. Nó giảm thời gian tìm kiếm từ O(n) xuống còn O(log n).

Ví Dụ Nhị Phân Tìm Kiếm

def binary_search(nums, target):
    batdau, ketthuc = 0, len(nums) - 1
    while batdau <= ketthuc:
        giua = batdau + (ketthuc - batdau) // 2
        if nums[giua] == target:
            return giua
        elif nums[giua] < target:
            batdau = giua + 1
        else:
            ketthuc = giua - 1
    return -1

Cây Nhị Phân và Quy Hoạch Động

Duyệt Cây Nhị Phân

Có ba cách duyệt cây nhị phân: trước (pre-order), giữa (in-order), và sau (post-order). Mỗi cách đều có ứng dụng riêng.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def preorder(root):
    return [root.val] + preorder(root.left) + preorder(root.right) if root else []

def inorder(root):
    return inorder(root.left) + [root.val] + inorder(root.right) if root else []

def postorder(root):
    return postorder(root.left) + postorder(root.right) + [root.val] if root else []

Quy Hoạch Động

Quy hoạch động (dynamic programming) là một kỹ thuật giải quyết vấn đề bằng cách chia nhỏ vấn đề thành các trường hợp con và lưu trữ kết quả của chúng để tránh tính toán lặp lại.

Ví Dụ: Tính Tổng Dãy Liên Tiếp Lớn Nhất

def max_subarray_sum(nums):
    dp = [0] * len(nums)
    dp[0] = nums[0]
    ketqua = dp[0]
    for i in range(1, len(nums)):
        dp[i] = max(dp[i-1] + nums[i], nums[i])
        ketqua = max(ketqua, dp[i])
    return ketqua

Kết Luận

Việc nắm vững các kỹ thuật và cấu trúc dữ liệu cơ bản là rất quan trọng cho bất kỳ lập trình viên nào. Phương pháp hai con trỏ, chia để trị, và quy hoạch động là những công cụ mạnh mẽ giúp giải quyết nhiều bài toán phức tạp một cách hiệu quả.