Hi mọi người, hôm nay mình sẽ giới thiệu 2 bài toán sử dụng HashMap thuộc vào nhóm easy.
Bài toán
Roman to Int
Các số La Mã được biểu diễn bằng bảy ký hiệu khác nhau: I, V, X, L, C, D và M. Ký hiệu Giá trị I 1 V 5 X 10 L 50 C 100 D 500 M 1000 Ví dụ:
Số 2 được viết là II trong số La Mã, nghĩa là hai số 1 cộng lại với nhau. Số 12 được viết là XII, tức là X + II. Số 27 được viết là XXVII, tức là XX + V + II. Các số La Mã thường được viết từ lớn nhất đến nhỏ nhất từ trái sang phải. Tuy nhiên, số 4 không được viết là IIII mà viết là IV. Vì số 1 (I) đứng trước số 5 (V) nên ta thực hiện phép trừ, dẫn đến kết quả là 4. Nguyên tắc này cũng áp dụng cho số 9, được viết là IX. Có sáu trường hợp sử dụng phép trừ trong số La Mã:
I có thể đứng trước V (5) và X (10) để tạo thành 4 và 9. X có thể đứng trước L (50) và C (100) để tạo thành 40 và 90. C có thể đứng trước D (500) và M (1000) để tạo thành 400 và 900.
Hướng tiếp cận
Nhìn sơ qua bài toán ta có thể thấy muốn tính giá trị các số la mã ta cộng tổng các chữ số từ trái sang phải và đồng thời gộp chung trường hợp đặc biệt IV, IX, XL , XC, CD, CM để tính cặp riêng ( các trường hợp này có điểm chung là chữ số đầu tiên nhỏ hơn chữ số đằng sau nó). Vì vậy chúng ta có thể giải bài toán như sau, mình xin phép trình bày bài giải bằng python nhé:
time complexity: O(n) - n is length of s
space complexity: O(1)
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} sum = roman_dict[s[0]] for i in range(1, len(s)): if roman_dict[s[i-1]] < roman_dict[s[i]]: sum += roman_dict[s[i]] - 2 * roman_dict[s[i-1]] else: sum += roman_dict[s[i]] return sum solution = Solution()
print(solution.romanToInt("III")) # 3
print(solution.romanToInt('IV')) # 4
print(solution.romanToInt('XVI')) # 16
print(solution.romanToInt('MCMXCIV')) # 1000 + 900 + 40 + 4 Vòng lặp Linked list
Cho 1 head, đầu của một danh sách liên kết (ListNode), hãy xác định xem danh sách liên kết đó có vòng lặp hay không.
Một danh sách liên kết có vòng lặp nếu có một nút trong danh sách có thể được truy cập lại bằng cách liên tục theo con trỏ next. Trong đó, pos được sử dụng để biểu thị chỉ số của nút mà con trỏ next của nút cuối cùng (tail) trỏ tới. Lưu ý rằng pos không được truyền dưới dạng tham số.
Trả về true nếu danh sách liên kết có vòng lặp. Nếu không có vòng lặp, trả về false.
class ListNode:
def init(self, x):
self.val = x
self.next = None
Ex: 
Hướng tiếp cận
Chúng ta sẽ sử dụng thuật toán Floyd 's Tortoise and hare cho 2 con trỏ slow và fast. Trong đó:
- Slow: Mỗi lần chỉ được di chuyển 1 nước
- Fast: Mỗi lần di chuyển được 2 nước
-> Theo nguyên tắc vòng lặp, đến 1 lúc nào đó 2 con trỏ sẽ phải gặp nhau.
Các bước thực hiện: Khởi tạo hai con trỏ slow và fast, cả hai đều bắt đầu từ đầu danh sách liên kết (head). Di chuyển: slow tiến một bước mỗi lần. fast tiến hai bước mỗi lần. Kiểm tra: Nếu slow và fast gặp nhau, nghĩa là có vòng lặp trong danh sách liên kết. Nếu fast hoặc fast.next là null, nghĩa là không có vòng lặp (đã tới cuối danh sách). Kết quả: Trả về true nếu có vòng lặp. Trả về false nếu không có vòng lặp.
Time complexity: O(n) - trong trường hợp tệ nhất cần loop qua toàn bộ mảng đến đến được phần tử trùng
Space complexity: O(1)
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 first_node = head second_node = head.next while first_node != second_node: if second_node.next is None or second_node.next.next is None: return False first_node = first_node.next second_node = second_node.next.next return True 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))