Chào mừng bạn đến với bài viết hôm nay!

Trong bài viết này, mình sẽ giới thiệu hai bài toán thú vị liên quan đến hash map, thuộc nhóm dễ. Đó là bài toán chuyển đổi từ số La Mã sang số nguyên và bài toán kiểm tra vòng lặp trong danh sách liên kết. Chúng ta hãy cùng tìm hiểu sâu hơn về từng bài toán nhé!

Bài toán 1: Chuyển đổi số La Mã sang số nguyên

Giới thiệu về số La Mã

Số La Mã được biểu diễn bằng bảy ký hiệu: I, V, X, L, C, D và M, với các giá trị tương ứng như sau:

Quy tắc cơ bản

Số La Mã thường được viết từ lớn nhất đến nhỏ nhất, tuy nhiên có một số trường hợp ngoại lệ:

• Số 4 được viết là IV thay vì IIII, vì 1 (I) đứng trước 5 (V) và được trừ đi.
• Tương tự, số 9 được viết là IX, 40 là XL, 90 là XC, 400 là CD, và 900 là CM.

Hướng tiếp cận và giải thuật

Chúng ta sẽ cộng dồn giá trị từng ký hiệu và xử lý các trường hợp đặc biệt bằng cách nhận diện vị trí của từng ký hiệu trong chuỗi. Đây là cách triển khai của chúng ta:

class Solution:
    def romanToInt(self, s: str) -> int:
        if len(s) == 0:
            return 0
        roman_dict = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}
        total = roman_dict[s[0]]
        for i in range(1, len(s)):
            if roman_dict[s[i-1]] < roman_dict[s[i]]:
                total += roman_dict[s[i]] - 2 * roman_dict[s[i-1]]
            else:
                total += roman_dict[s[i]]
        return total

Thời gian và không gian phức tạp

• Thời gian: O(n) (n là chiều dài của chuỗi s)
• Không gian: O(1)

Ví dụ

solution = Solution()
print(solution.romanToInt("III")) # 3
print(solution.romanToInt('IV')) # 4
print(solution.romanToInt('XVI')) # 16
print(solution.romanToInt('MCMXCIV')) # 1994

Bài toán 2: Kiểm tra vòng lặp trong danh sách liên kết

Giới thiệu

Cho một head, đại diện cho đầu của danh sách liên kết (ListNode), chúng ta cần xác định xem danh sách này có vòng lặp hay không. Một danh sách liên kết được coi là có vòng lặp khi có một nút nào đó có thể được truy cập lại qua con trỏ next.

Hướng tiếp cận

Chúng ta sẽ sử dụng thuật toán Floyd's Tortoise and Hare với hai con trỏ:

• Slow: di chuyển một bước mỗi lần.
• Fast: di chuyển hai bước mỗi lần.

Hai con trỏ này sẽ chạy trong danh sách liên kết cho đến khi chúng gặp nhau hoặc cho đến khi fast hoặc fast.next là null.

Triển khai

from typing import Optional

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        if head is None or head.next is None:
            return False

        slow = head
        fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                return True
        return False

Thời gian và không gian phức tạp

• Thời gian: O(n) (trong trường hợp tệ nhất cần phải duyệt qua toàn bộ danh sách liên kết để tìm vòng lặp).
• Không gian: O(1)

Ví dụ

solution = Solution()
root = ListNode(3)
root.next = ListNode(2)
root.next.next = ListNode(0)
root.next.next.next = ListNode(-4)
root.next.next.next.next = root.next
print(solution.hasCycle(root))  # True

Kết luận

Hai bài toán này không chỉ giúp chúng ta hiểu cách làm việc với cấu trúc dữ liệu mà còn cung cấp nền tảng cho các bài toán phức tạp hơn sau này. Hy vọng qua bài viết này, bạn sẽ có cái nhìn rõ hơn về HashMap và các cấu trúc dữ liệu. Cảm ơn bạn đã theo dõi!
source: viblo