Bài viết này trình bày các giải pháp cho ba bài toán LeetCode: 135. Phân phối Kẹo, 140. Tách Từ II và 149. Điểm Tối Đa Trên Một Đường Thẳng.
135. Phân phối Kẹo
Bài toán yêu cầu phân phối kẹo cho các trẻ em dựa trên xếp hạng của họ sao cho mỗi trẻ em nhận được ít nhất một viên kẹo và trẻ em có xếp hạng cao hơn phải nhận được nhiều kẹo hơn trẻ em liền kề có xếp hạng thấp hơn.
Giải pháp 1: Tham lam
Sử dụng hai mảng `left` và `right` để lưu số kẹo cần thiết cho từng trẻ em khi đi từ trái sang phải và từ phải sang trái. Sau đó, kết hợp kết quả từ cả hai hướng để xác định số kẹo cuối cùng cho mỗi trẻ.
class Solution:
def candy(self, ratings: list[int]) -> int:
n = len(ratings)
left = [1] * n
right = [1] * n
# Duyệt từ trái sang phải
for i in range(1, n):
if ratings[i] > ratings[i - 1]:
left[i] = left[i - 1] + 1
# Duyệt từ phải sang trái
total_candies = left[-1]
for i in range(n - 2, -1, -1):
if ratings[i] > ratings[i + 1]:
right[i] = right[i + 1] + 1
total_candies += max(left[i], right[i])
return total_candies
Giải pháp 2: Tham lam
Một cách tiếp cận khác là chỉ sử dụng một mảng `candy_nums` và thực hiện hai lượt duyệt. Lượt đầu tiên từ trái sang phải để đảm bảo các điều kiện tăng dần, và lượt thứ hai từ phải sang trái để cập nhật các giá trị sao cho các điều kiện giảm dần cũng được thỏa mãn.
class Solution:
def candy(self, ratings: list[int]) -> int:
n = len(ratings)
if n == 0:
return 0
candy_nums = [1] * n
# Duyệt từ trái sang phải
for i in range(1, n):
if ratings[i] > ratings[i - 1]:
candy_nums[i] = candy_nums[i - 1] + 1
# Duyệt từ phải sang trái
for i in range(n - 1, 0, -1):
if ratings[i - 1] > ratings[i]:
candy_nums[i - 1] = max(candy_nums[i - 1], candy_nums[i] + 1)
return sum(candy_nums)
Giải pháp 3: Tham lam, Toán học
Giải pháp này tập trung vào việc xác định các đoạn tăng và giảm liên tiếp trong mảng `ratings`. Số kẹo được tính toán dựa trên độ dài của các đoạn này bằng công thức cấp số cộng và cộng thêm số kẹo cho các đỉnh.
class Solution:
def candy(self, ratings: list[int]) -> int:
n = len(ratings)
ans = n # Khởi tạo mỗi trẻ em nhận 1 kẹo
i = 0
while i < n:
# Tìm điểm bắt đầu của đoạn tăng (hoặc chính nó nếu không tăng)
start = i - 1 if i > 0 and ratings[i - 1] < ratings[i] else i
# Tìm đỉnh của đoạn tăng
while i + 1 < n and ratings[i] < ratings[i + 1]:
i += 1
peak = i
# Tìm kết thúc của đoạn giảm
while i + 1 < n and ratings[i] > ratings[i + 1]:
i += 1
# Tính toán số kẹo cho đoạn tăng và giảm
increase_len = peak - start
decrease_len = i - peak
ans += (increase_len * (increase_len - 1)) // 2 + (decrease_len * (decrease_len - 1)) // 2 + max(increase_len, decrease_len)
i += 1
return ans
140. Tách Từ II
Bài toán yêu cầu phân tích một chuỗi `s` thành một hoặc nhiều từ có nghĩa, với các từ có nghĩa được cung cấp trong một danh sách `wordDict`. Kết quả là một danh sách tất cả các cách phân tích có thể.
Giải pháp 1: DFS, Ghi nhớ, Quay lui
Sử dụng thuật toán DFS kết hợp với ghi nhớ (memoization) để tránh tính toán lại các kết quả đã có. Một mảng `memo` được sử dụng để đánh dấu các vị trí mà từ đó chuỗi con không thể phân tích được.
class Solution:
def wordBreak(self, s: str, wordDict: list[str]) -> list[str]:
results = []
memo = [True] * (len(s) + 1) # True: có thể phân tích, False: không thể
word_set = set(wordDict)
def dfs(start_index: int, current_sentence: list[str]):
if start_index == len(s):
results.append(" ".join(current_sentence))
return
# Nếu memo[start_index] là False, nghĩa là từ vị trí này không thể phân tích tiếp
if not memo[start_index]:
return
# Lưu lại số lượng kết quả trước khi gọi đệ quy để kiểm tra memo sau này
num_results_before = len(results)
for end_index in range(start_index + 1, len(s) + 1):
word = s[start_index:end_index]
if word in word_set:
current_sentence.append(word)
dfs(end_index, current_sentence)
current_sentence.pop() # Quay lui
# Nếu không có kết quả nào được thêm vào, đánh dấu là không thể phân tích từ vị trí này
if len(results) == num_results_before:
memo[start_index] = False
dfs(0, [])
return results
Giải pháp 2: DFS, Động (DP)
Sử dụng DP để xác định xem chuỗi con có thể phân tích được hay không. Mảng `dp[i]` cho biết liệu `s[0...i-1]` có thể phân tích được không. Mảng `pos[i]` lưu trữ các chỉ số bắt đầu mà từ đó `s[...i-1]` có thể phân tích được. Sau đó, sử dụng DFS để xây dựng các câu hoàn chỉnh.
class Solution:
def wordBreak(self, s: str, wordDict: list[str]) -> list[str]:
n = len(s)
max_len = 0
for word in wordDict:
max_len = max(max_len, len(word))
word_set = set(wordDict)
# dp[i] = True nếu s[0...i-1] có thể tách thành các từ trong từ điển
dp = [False] * (n + 1)
# pos[i] lưu trữ các điểm bắt đầu j sao cho s[j...i-1] là một từ và dp[j] là True
pos = [[] for _ in range(n + 1)]
dp[0] = True
for i in range(1, n + 1):
# Chỉ xem xét các từ có độ dài không quá max_len
for j in range(max(0, i - max_len), i):
if dp[j] and s[j:i] in word_set:
dp[i] = True
pos[i].append(j) # Lưu lại điểm bắt đầu
if not dp[n]:
return []
results = []
def build_sentences(end_index: int, current_path: list[str]):
if end_index == 0:
results.append(" ".join(reversed(current_path)))
return
for start_index in pos[end_index]:
current_path.append(s[start_index:end_index])
build_sentences(start_index, current_path)
current_path.pop() # Quay lui
build_sentences(n, [])
return results
Giải pháp 3: 1 dòng
Giải pháp này sử dụng một hàm lambda đệ quy và memoization để đạt được kết quả trong một dòng mã. Nó khá phức tạp và khó đọc.
class Solution:
def wordBreak(self, s: str, wordDict: list[str]) -> list[str]:
word_set = set(wordDict)
word_lengths = set(len(w) for w in wordDict)
memo = {}
def solve(index):
if index == len(s):
return [""]
if index in memo:
return memo[index]
res = []
for length in word_lengths:
end_index = index + length
if end_index <= len(s):
word = s[index:end_index]
if word in word_set:
sub_results = solve(end_index)
for sub_res in sub_results:
if sub_res:
res.append(word + " " + sub_res)
else:
res.append(word)
memo[index] = res
return res
return solve(0)
149. Điểm Tối Đa Trên Một Đường Thẳng
Bài toán yêu cầu tìm số điểm tối đa nằm trên cùng một đường thẳng trong một tập hợp các điểm cho trước trên mặt phẳng 2D.
Giải pháp 1: Hình học, Hash, Toán học
Ý tưởng là duyệt qua từng điểm và coi nó như một điểm cố định trên đường thẳng. Sau đó, tính toán độ dốc (slope) của đường thẳng nối điểm cố định này với tất cả các điểm còn lại. Sử dụng một hash map để đếm số lần xuất hiện của mỗi độ dốc. Độ dốc có tần suất cao nhất cộng với 1 (cho điểm cố định) là số điểm tối đa trên một đường thẳng đi qua điểm đó.
import math
from collections import defaultdict
class Solution:
def maxPoints(self, points: list[list[int]]) -> int:
n = len(points)
if n <= 2:
return n
max_points = 0
for i in range(n):
slopes = defaultdict(int)
x1, y1 = points[i]
current_max = 0
for j in range(i + 1, n):
x2, y2 = points[j]
dx = x2 - x1
dy = y2 - y1
if dx == 0:
slope = float('inf') # Xử lý trường hợp đường thẳng đứng
else:
slope = dy / dx
slopes[slope] += 1
current_max = max(current_max, slopes[slope])
max_points = max(max_points, current_max + 1) # Cộng 1 cho điểm đang xét (points[i])
return max_points
Giải pháp 2: Hình học, Mảng, Hash, Toán học
Có hai phương pháp chính được đề cập:
- Liệt kê đường thẳng + Liệt kê thống kê: Duyệt qua tất cả các cặp điểm để xác định một đường thẳng, sau đó duyệt qua tất cả các điểm còn lại để đếm số điểm trên đường thẳng đó.
- Liệt kê đường thẳng + Hash thống kê: Duyệt qua từng điểm, sau đó tính toán ước số chung lớn nhất (GCD) của sự thay đổi tọa độ (dx, dy) để chuẩn hóa độ dốc. Sử dụng hash map để đếm số điểm có cùng độ dốc đã chuẩn hóa.
Dưới đây là triển khai cho phương pháp thứ hai (Hash thống kê):
import math
from collections import defaultdict
class Solution:
def maxPoints(self, points: list[list[int]]) -> int:
def gcd(a, b):
while b:
a, b = b, a % b
return a
n = len(points)
if n <= 2:
return n
max_count = 0
for i in range(n):
slopes = defaultdict(int)
x1, y1 = points[i]
current_max_on_line = 0
for j in range(i + 1, n):
x2, y2 = points[j]
dx = x1 - x2
dy = y1 - y2
common_divisor = gcd(dx, dy)
# Chuẩn hóa độ dốc bằng cách chia cho ước số chung lớn nhất
key = str(dx // common_divisor) + "_" + str(dy // common_divisor)
slopes[key] += 1
current_max_on_line = max(current_max_on_line, slopes[key])
# Cộng 1 cho điểm gốc (points[i])
max_count = max(max_count, current_max_on_line + 1)
return max_count
Giải pháp 3: Hash
Giải pháp này đầu tiên loại bỏ các điểm trùng lặp và sau đó áp dụng logic tương tự như Giải pháp 1 hoặc 2. Nó sử dụng `collections.Counter` để xử lý các điểm trùng lặp hiệu quả.
from collections import Counter, defaultdict
import math
class Solution:
def maxPoints(self, points: list[list[int]]) -> int:
# Đếm số lần xuất hiện của mỗi điểm
point_counts = Counter(tuple(p) for p in points)
unique_points = list(point_counts.keys())
n = len(unique_points)
if n <= 1:
return len(points)
max_total_points = 0
def gcd(a, b):
while b:
a, b = b, a % b
return a
for i in range(n):
slopes = defaultdict(int)
x1, y1 = unique_points[i]
max_points_on_line_through_i = 0
for j in range(i + 1, n):
x2, y2 = unique_points[j]
dx = x2 - x1
dy = y2 - y1
common_divisor = gcd(dx, dy)
slope_key = f"{dy // common_divisor}/{dx // common_divisor}"
slopes[slope_key] += point_counts[unique_points[j]]
max_points_on_line_through_i = max(max_points_on_line_through_i, slopes[slope_key])
# Cộng số điểm trùng lặp của điểm đang xét (unique_points[i])
max_total_points = max(max_total_points, max_points_on_line_through_i + point_counts[unique_points[i]])
return max_total_points