Ví dụ nhiệm vụ với việc sử dụng bảng băm

8.1 Nhiệm vụ tìm kiếm trùng lặp trong mảng

Nhiệm vụ: Cho một mảng số. Cần tìm và trả về tất cả các phần tử trùng lặp trong mảng.

Giải pháp: Sử dụng bảng băm để theo dõi các số đã xuất hiện. Nếu số xuất hiện lại, thêm nó vào danh sách các phần tử trùng lặp.

Ví dụ thực hiện:

def find_duplicates(arr):
    seen = set()
    duplicates = []
    for item in arr:
        if item in seen:
            duplicates.append(item)
        else:
            seen.add(item)
    return duplicates

# Ví dụ sử dụng
arr1 = [1, 2, 3, 2, 4, 5, 6, 4, 7]
print(find_duplicates(arr1))  # Đầu ra: [2, 4]

arr2 = []
print(find_duplicates(arr2))  # Đầu ra: []

arr3 = [1, 2, 3, 4, 5]
print(find_duplicates(arr3))  # Đầu ra: []

Giải thích:

• Tạo một tập rỗng seen để theo dõi các số duy nhất.
• Duyệt qua từng phần tử trong mảng. Nếu phần tử đã có trong seen, thêm nó vào danh sách duplicates.
• Nếu phần tử không có trong seen, thêm nó vào đó.
• Trả về danh sách các phần tử trùng lặp.

Lưu ý rằng hàm này hoạt động đúng với mảng rỗng và mảng không có trùng lặp, trả về danh sách rỗng trong cả hai trường hợp.

8.2 Nhiệm vụ kiểm tra anagrams

Nhiệm vụ: Cho hai chuỗi. Cần xác định xem chúng có phải là anagram (chứa cùng ký tự với số lượng bằng nhau) hay không.

Giải pháp: Sử dụng bảng băm để đếm tần số ký tự trong cả hai chuỗi và so sánh kết quả.

Ví dụ thực hiện:

def are_anagrams(str1, str2):
    # Chuyển chuỗi về dạng chữ thường để xử lý sự khác biệt về chữ in hoa
    str1 = str1.lower()
    str2 = str2.lower()
    
    if len(str1) != len(str2):
        return False
    char_count = {}
    # Đếm tần số ký tự trong chuỗi đầu tiên
    for char in str1:
        char_count[char] = char_count.get(char, 0) + 1
    # Trừ tần số ký tự trong chuỗi thứ hai
    for char in str2:
        if char in char_count:
            char_count[char] -= 1
        else:
            return False
    # Kiểm tra tất cả các giá trị trong từ điển bằng 0
    return all(count == 0 for count in char_count.values())

# Ví dụ sử dụng
print(are_anagrams("listen", "silent"))  # Đầu ra: True
print(are_anagrams("hello", "world"))  # Đầu ra: False
print(are_anagrams("", ""))  # Đầu ra: True
print(are_anagrams("Tea", "Eat"))  # Đầu ra: True

Giải thích:

• Nếu độ dài chuỗi không khớp, chúng không thể là anagram.
• Sử dụng từ điển char_count để đếm tần số ký tự trong chuỗi đầu tiên.
• Duyệt qua chuỗi thứ hai và trừ tần số ký tự.
• Kiểm tra tất cả các giá trị trong từ điển bằng không. Nếu đúng, các chuỗi là anagram.

Lưu ý rằng hàm này xử lý sự khác biệt về chữ in hoa bằng cách chuyển cả hai chuỗi về chữ thường trước khi so sánh. Nó cũng xử lý đúng với chuỗi rỗng, coi chúng là anagram của nhau.

8.3 Nhiệm vụ tìm cặp có tổng cho trước

Nhiệm vụ: Cho một mảng số và một giá trị tổng cần tìm. Cần tìm tất cả các cặp số mà tổng của chúng bằng với giá trị tổng được cho.

Giải pháp: Sử dụng bảng băm để lưu trữ các số và kiểm tra xem chúng có tạo thành một cặp với số hiện tại mà tạo ra tổng cần tìm hay không.

Ví dụ thực hiện:

def find_pairs_with_sum(arr, target_sum):
    seen = set()
    pairs = []
    for num in arr:
        complement = target_sum - num
        if complement in seen:
            pairs.append((complement, num))
        seen.add(num)
    return pairs

# Ví dụ sử dụng
arr = [1, 5, 7, -1, 5]
target_sum = 6
print(find_pairs_with_sum(arr, target_sum))  # Đầu ra: [(1, 5), (1, 5)]

Giải thích:

• Tạo một tập rỗng seen để theo dõi các số.
• Với từng số trong mảng, tính toán bổ sung của nó complement (sự khác biệt giữa tổng mục tiêu và số hiện tại).
• Nếu bổ sung đã có trong seen, thêm cặp (complement, num) vào danh sách pairs.
• Thêm số hiện tại vào seen.
• Trả về danh sách các cặp.

Điều quan trọng cần lưu ý là thuật toán này có độ phức tạp thời gian O(n), với n là số lượng phần tử trong mảng. Điều này hiệu quả hơn nhiều so với giải pháp ngây ngô sử dụng vòng lặp lồng, có độ phức tạp O(n^2). Sử dụng bảng băm cho phép chúng ta tìm tất cả các cặp chỉ với một lần duyệt qua mảng, điều này đặc biệt quan trọng khi làm việc với khối lượng dữ liệu lớn.

Để so sánh, đây là cách giải pháp ngây ngô với độ phức tạp thời gian O(n^2) trông như thế nào:

def find_pairs_naive(arr, target_sum):
    pairs = []
    n = len(arr)
    for i in range(n):
        for j in range(i+1, n):
            if arr[i] + arr[j] == target_sum:
                pairs.append((arr[i], arr[j]))
    return pairs

# Ví dụ sử dụng
arr = [1, 5, 7, -1, 5]
target_sum = 6
print(find_pairs_naive(arr, target_sum))  # Đầu ra: [(1, 5), (1, 5)]

Như đã thấy, giải pháp ngây ngô yêu cầu hai vòng lặp lồng nhau, điều này khiến nó không hiệu quả với các mảng lớn. Giải pháp sử dụng bảng băm cho phép đạt được mục tiêu nhanh hơn nhiều.