Các bài tập hôm nay
454. Tổng bốn số II
Liên kết bài tập: 454. Tổng bốn số II - LeetCode
Phân tích: Nếu không dùng bảng băm (hashmap), phương pháp brute-force với bốn vòng lặp sẽ dẫn đến thời gian chạy quá lâu. Trong bài trước, khi giải bài 242. Kiểm tra chuỗi anagram - LeetCode, ta đã sử dụng một bảng băm để cộng và trừ giá trị. Trong bài 349. Giao của hai mảng - LeetCode, ta dùng hai bảng băm riêng biệt để đếm tần suất phần tử trong từng mảng.
Với bài này có bốn mảng, nếu dùng bốn bảng băm thì không đơn giản hóa được vấn đề. Vì vậy, nên kết hợp hai mảng thành một, và hai mảng còn lại cũng tương tự. Tuy nhiên, do tổng cần đạt tới 0, giống như bài 242, chỉ cần một bảng băm là đủ. Trong đó, khóa (key) là tổng của hai phần tử từ hai mảng đầu, và giá trị (value) là số lượng tổ hợp tạo ra tổng đó. Ta chỉ cần tìm các cặp phần tử từ hai mảng sau sao cho tổng của chúng là âm của khóa, rồi cộng dồn số lượng tổ hợp phù hợp vào kết quả.
Mã nguồn:
class Solution:
def fourSumCount(self, nums1, nums2, nums3, nums4):
hash_map = {}
# Tính tất cả các tổng của nums1 và nums2
for num1 in nums1:
for num2 in nums2:
total = num1 + num2
if total in hash_map:
hash_map[total] += 1
else:
hash_map[total] = 1
count = 0
# Tìm các tổng của nums3 và nums4 sao cho tổng cộng với các giá trị trước bằng 0
for num3 in nums3:
for num4 in nums4:
complement = -(num3 + num4)
if complement in hash_map:
count += hash_map[complement]
return count
383. Thư đòi nợ
Liên kết bài tập: 383. Thư đòi nợ - LeetCode
Phân tích: Kiểm tra xem chuỗi ransomNote có thể được tạo từ các ký tự trong magazine hay không, mỗi ký tự trong magazine chỉ được sử dụng một lần. Điều này tương đương với việc giao giữa ransomNote và magazine phải bằng chính ransomNote.
Giải pháp tương tự như bài 242. Kiểm tra chuỗi anagram - LeetCode. Vì hai chuỗi không hoàn toàn giống nhau, và magazine dài hơn hoặc bằng ransomNote, nên ta cần xây dựng hai bảng đếm riêng biệt, sau đó kiểm tra xem phần tử tại cùng vị trí trong bảng đếm có thỏa mãn điều kiện magazine >= ransomNote hay không.
Mã nguồn:
class Solution:
def canConstruct(self, ransomNote, magazine):
count1 = [0] * 26
count2 = [0] * 26
# Đếm tần suất ký tự trong ransomNote
for char in ransomNote:
count1[ord(char) - ord('a')] += 1
# Đếm tần suất ký tự trong magazine
for char in magazine:
count2[ord(char) - ord('a')] += 1
# Kiểm tra xem mỗi ký tự trong ransomNote có đủ trong magazine không
for i in range(26):
if count1[i] > count2[i]:
return False
return True
15. Ba số tổng bằng 0
Liên kết bài tập: 15. Ba số tổng bằng 0 - LeetCode
Phân tích: Bài này khó hơn một chút. Khi bắt đầu làm, mình không biết cách tiếp cận. Việc tham khảo hướng dẫn trong tài liệu "Code Follow-up" sẽ giúp dễ hiểu hơn.
Mã nguồn:
class Solution:
def threeSum(self, nums):
result = []
nums.sort()
for i in range(len(nums)):
# Nếu phần tử đầu tiên lớn hơn 0, thì tổng ba số không thể bằng 0
if nums[i] > 0:
return result
# Bỏ qua các phần tử trùng lặp
if i > 0 and nums[i] == nums[i-1]:
continue
left = i + 1
right = len(nums) - 1
while left < right:
total = nums[i] + nums[left] + nums[right]
if total < 0:
left += 1
elif total > 0:
right -= 1
else:
result.append([nums[i], nums[left], nums[right]])
# Bỏ qua các phần tử trùng lặp ở bên phải
while left < right and nums[right] == nums[right - 1]:
right -= 1
# Bỏ qua các phần tử trùng lặp ở bên trái
while left < right and nums[left] == nums[left + 1]:
left += 1
right -= 1
left += 1
return result
18. Bốn số tổng bằng mục tiêu
Liên kết bài tập: 18. Bốn số tổng bằng mục tiêu - LeetCode
Phân tích: Bài này tương tự như bài ba số tổng bằng 0, nhưng thay vì tổng bằng 0, nó là tổng bằng một giá trị mục tiêu (target). Cách tiếp cận cũng tương tự: hai vòng lặp ngoài kết hợp với con trỏ hai đầu (two pointers) để biểu diễn chỉ số của bốn phần tử. Do target không cố định là 0, nên điều kiện kiểm tra sẽ khác.
Mã nguồn:
class Solution:
def fourSum(self, nums, target):
nums.sort()
n = len(nums)
result = []
for i in range(n):
# Ngắt vòng lặp nếu phần tử đầu tiên lớn hơn target và target dương
if nums[i] > target and nums[i] > 0 and target > 0:
break
# Bỏ qua phần tử trùng lặp
if i > 0 and nums[i] == nums[i-1]:
continue
for j in range(i+1, n):
# Ngắt vòng lặp nếu tổng hai phần tử đầu vượt quá target và target dương
if nums[i] + nums[j] > target and target > 0:
break
# Bỏ qua phần tử trùng lặp
if j > i+1 and nums[j] == nums[j-1]:
continue
left = j + 1
right = n - 1
while left < right:
current_sum = nums[i] + nums[j] + nums[left] + nums[right]
if current_sum == target:
result.append([nums[i], nums[j], nums[left], nums[right]])
# Bỏ qua các phần tử trùng lặp
while left < right and nums[left] == nums[left+1]:
left += 1
while left < right and nums[right] == nums[right-1]:
right -= 1
left += 1
right -= 1
elif current_sum < target:
left += 1
else:
right -= 1
return result