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:
Ký hiệu | Giá trị |
---|---|
I | 1 |
V | 5 |
X | 10 |
L | 50 |
C | 100 |
D | 500 |
M | 1000 |
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:
python
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ụ
python
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
python
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ụ
python
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!