Giới thiệu
Hẳn bạn đã từng nghe đến số Palindrome, tức là những số có tính đối xứng khi đọc từ trái qua phải và ngược lại. Nhưng liệu bạn đã bao giờ tự hỏi: làm thế nào để tìm số Palindrome gần nhất với một số bất kỳ? Trong bài viết này, chúng ta sẽ cùng nhau khám phá cách giải quyết bài toán "Tìm Số Palindrome Gần Nhất" bằng cách sử dụng kỹ thuật Binary Search – một phương pháp đầy mạnh mẽ và hiệu quả.
Bài Toán Đặt Ra
Cho một chuỗi số nguyên n, nhiệm vụ của bạn là tìm số Palindrome gần nhất với n, nhưng không phải là chính n. Nếu có hai số Palindrome có cùng khoảng cách tới n, bạn cần trả về số nhỏ hơn trong hai số đó.
Ví Dụ Minh Họa
Input: n = "123"
Output: 121
Input: n = "1"
Output: 0
Tư Duy Giải Quyết
Để giải quyết bài toán này, ta cần tìm ra hai số Palindrome:
Số Palindrome nhỏ hơn gần nhất với n.
Số Palindrome lớn hơn gần nhất với n.
Sau đó, chúng ta sẽ so sánh khoảng cách giữa n và hai số này để tìm ra số gần nhất.
Kỹ Thuật Binary Search
Binary Search (tìm kiếm nhị phân) là một phương pháp giúp thu hẹp phạm vi tìm kiếm một cách nhanh chóng, đặc biệt hữu ích khi chúng ta làm việc với các tập hợp số lớn.
Các Bước Thực Hiện
Tìm Số Palindrome Tiếp Theo:
Khởi tạo khoảng tìm kiếm với biên trái là n + 1 và biên phải là một giá trị cực lớn.
Sử dụng Binary Search để tìm số Palindrome lớn hơn gần nhất với n.
Tìm Số Palindrome Trước Đó:
Khởi tạo khoảng tìm kiếm với biên trái là 0 và biên phải là n - 1.
Sử dụng Binary Search để tìm số Palindrome nhỏ hơn gần nhất với n.
Giải Thuật Chi Tiết
Dưới đây là mô tả chi tiết về các hàm cần thiết để triển khai giải thuật:
-
convert(num): Hàm này nhận đầu vào là một số nguyên num và tạo ra số Palindrome bằng cách đối xứng hóa nửa đầu của chuỗi số. -
next_palindrome(num): Sử dụng Binary Search để tìm số Palindrome lớn hơn gần nhất với num. -
prev_palindrome(num): Sử dụng Binary Search để tìm số Palindrome nhỏ hơn gần nhất với num. -
nearestPalindromic(n): Hàm chính của bài toán, trả về số Palindrome gần nhất với n.
Implementation
Dưới đây là đoạn mã Python hiện thực toàn bộ giải thuật:
class Solution:
def convert(self, num: int) -> int:
s = str(num)
n = len(s)
l, r = (n-1) // 2, n // 2
s_list = list(s)
while l>=0:
s_list[r] = s_list[l]
r += 1
l -= 1
return int("".join(s_list))
def next_palindrome(self, num: int) -> int:
left, right = 0, num
ans = float('inf')
while left <= right:
mid = (right-left) // 2 + left
palin = self.convert(mid)
if palin < num:
ans = palin
left = mid + 1
else:
right = mid - 1
return ans
def prev_palindrome(self, num: int) -> int:
left, right = num, int(1e18)
ans = float('-inf')
while left <= right:
mid = (right-left) // 2 + left
palin = self.convert(mid)
if palin > num:
ans = palin
right = mid - 1
else:
left = mid + 1
return ans
def nearestPalindromic(self, n: str) -> str:
num = int(n)
a = self.next_palindrome(num)
b = self.prev_palindrome(num)
if abs(a-num) <= abs(b-num):
return str(a)
return str(b)
Lời Khuyên Cuối Cùng
Bài toán này không chỉ giúp bạn luyện tập kỹ năng lập trình mà còn nâng cao khả năng tư duy thuật toán. Việc hiểu rõ cách hoạt động của Binary Search và cách ứng dụng nó trong bài toán này sẽ mở ra cho bạn nhiều hướng giải quyết khác nhau trong các bài toán phức tạp khác.
Hãy tiếp tục luyện tập, viết lại các giải pháp dưới dạng blog hoặc ghi chép, và chia sẻ kiến thức của mình. Đó chính là cách tốt nhất để tiến bộ và trở thành một developer giỏi hơn mỗi ngày.
Top comments (0)