Bảng Băm Trong Ngữ Cảnh Python

Trong Python, cấu trúc bảng băm thường được triển khai thông qua kiểu từ điển (dict). Khác với C, Python cung cấp sẵn cơ chế này như một thành phần ngôn ngữ, giúp tối ưu hóa thao tác tìm kiếm.

Tìm Cặp Số Tổng Mục Tiêu (Mức Độ Dễ)

Yêu cầu: Cho mảng số nguyên và giá trị mục tiêu, trả về chỉ số của hai số có tổng bằng mục tiêu. Mỗi phần tử chỉ được sử dụng một lần.

class TimCapSo:
    def tim_cap(self, mang_so: list[int], muc_tieu: int) -> list[int]:
        da_duyet = {}
        for chi_so, gia_tri in enumerate(mang_so):
            gia_tri_can_tim = muc_tieu - gia_tri
            if gia_tri_can_tim in da_duyet:
                return [da_duyet[gia_tri_can_tim], chi_so]
            da_duyet[gia_tri] = chi_so

Thuật toán sử dụng từ điển lưu trữ giá trị đã duyệt qua với chỉ số tương ứng. Độ phức tạp thời gian O(n) nhờ thao tác kiểm tra tồn tại trong từ điển là O(1).

Nhóm Từ Đảo Chữ (Mức Độ Trung Bình)

Yêu cầu: Gom nhóm các từ có cùng bộ chữ cái (không tính thứ tự) thành từng nhóm.

class NhomTuDao:
    def nhom_tu(self, danh_sach_tu: list[str]) -> list[list[str]]:
        nhom_tu = {}
        for tu in danh_sach_tu:
            khoa_chuan = "".join(sorted(tu))
            nhom_tu[khoa_chuan] = nhom_tu.get(khoa_chuan, []) + [tu]
        return list(nhom_tu.values())

Chuỗi đã sắp xếp đóng vai trò khóa băm. Sử dụng phương thức get() để xử lý trường hợp khóa chưa tồn tại, thay thế cho defaultdict.

Chuỗi Số Liên Tiếp Dài Nhất (Mức Độ Trung Bình)

Yêu cầu: Tìm độ dài chuỗi số nguyên liên tiếp dài nhất trong mảng không cần thứ tự, với độ phức tạp O(n).

class TimChuoiLienTuc:
    def do_dai_lon_nhat(self, mang_so: list[int]) -> int:
        if not mang_so:
            return 0
            
        so_duy_nhat = set(mang_so)
        do_dai_toi_da = 0
        
        for so in so_duy_nhat:
            if so - 1 not in so_duy_nhat:
                bat_dau = so
                do_dai_hien_tai = 1
                
                while bat_dau + 1 in so_duy_nhat:
                    bat_dau += 1
                    do_dai_hien_tai += 1
                    
                do_dai_toi_da = max(do_dai_toi_da, do_dai_hien_tai)
                
        return do_dai_toi_da

Tận dụng tập hợp (set) để loại bỏ phần tử trùng lặp. Kiểm tra điều kiện bắt đầu chuỗi bằng cách xác minh sự tồn tại của số liền trước.