Cùng giải leetcode! Bài 9. Palindrome Number

Tác giả: Lê Trung Kiên lớp java 08
Email: lekien.2803.cg@gmail.com
SĐT: 0942096947
Link bài toán: https://leetcode.com/problems/palindrome-number/

1. Mở đầu

Xin chào các bạn, mình viết ra bài viết này để chia sẻ phương pháp giải cũng như tư duy của mình về bài toán này của leetcode. Phương pháp của mình có thể không phải là tối ưu nhất, tuy nhiên mình sẽ phân tích, chia nhỏ bài toán ra thành các module nhỏ hơn để dễ giải quyết cũng như giúp các bạn hiểu được các yêu cầu mà bài toán đưa ra.

2. Đề bài

Cho một số nguyên x, trả về kết quả true nếu số x là một số đối xứng, không thì là false.

Điều kiện:

• -2^31 <= x <= 2^31 - 1.

Bài toán minh họa 1:

Input: x = 121
Output: true
Explanation: 121 reads as 121 from left to right and from right to left.

Bài toán minh họa 2:

Input: x = -121
Output: false
Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.

Bài toán minh họa 3:

Input: x = 10
Output: false
Explanation: Reads 01 from right to left. Therefore it is not a palindrome.

3. Phân tích

Ố kề. Bài này cũng không có gì quá phức tạp đâu. Trước hết chúng ta cần biết, số đối xứng là khi mà ta đảo ngược các chữ số của số đó mà nó không thay đổi thì đó là số đối xứng. Vậy thì chúng ta sẽ có hai cách để giải bài toán này.

Cách đầu tiên, khi nhắc đến sự đảo ngược, ta nghĩ ngay đến class StringBuilder vì chúng có method reverse() có thể đảo ngược toàn bộ kí tự có trong chuỗi. Nghĩa là chúng ta sẽ biến đổi số nguyên x này sang dạng chuỗi, sau đó dùng method reverse() để đảo ngược chuỗi đó, rồi đem so sánh với chuỗi ban đầu. Nếu chúng giống nhau thì số x này là số đối xứng, còn không thì ngược lại.

Tuy nhiên, với cách đầu tiên thì chúng ta sẽ phải đảo hết tất cả tất cả chữ số của số nguyên x, rồi mới có thể kiểm tra được xem nó có giống với số ban đầu không. Thay vào đó, chúng ta có cách thứ hai, ấy là chỉ kiểm tra một nửa số chữ số của x thôi.
Ví dụ: số 1221 thì chúng ta sẽ tách đôi ra thành 12 và 21, đảo ngược một nửa cuối của nó (tức 21) sẽ là 12, cũng chính bằng nửa đầu, nghĩa là số này là số đối xứng.

Vậy nếu số x có các chữ số là số lẻ thì sao? Như ở trên số 1221 có bốn chữ số thì ta bổ đôi ra mỗi bên hai chữ số, sau đó so sánh chúng. Nhưng số có số chữ số là lẻ thì bổ đôi kiểu gì? Rất đơn giản, vì số chữ số là lẻ, nên chữ số chính giữa dù có đảo ngược cũng là chính nó, ví dụ như 12321 thì số 3 nằm chính giữa khi đảo ngược lại cũng là chính nó, nên ta chỉ việc đảo 21 thành 12 rồi so sánh là xong.

Làm thế nào để chúng ta có thể đảo một nửa chữ số của x? Chúng ta sẽ dùng cách lấy từng chữ số từ cuối đến giữa của x bằng cách lấy x % 10. Với phép chia lấy dư %, ta sẽ lấy được chữ số cuối cùng của x. Ví dụ với số x = 1221:

Sau khi lấy được chữ số cuối cùng là 1, ta sẽ tiến đến lấy số 2 bằng cách chia x cho 10. Với phép chia như vậy, x bây giờ chỉ còn là 122:

Lại lấy x % 10 ta sẽ được 2, cứ như thế đến khi ta lấy được đến nửa chữ số của x. Với công việc lặp đi lặp lại như vậy, chúng ta sẽ cần dùng một vòng lặp while để xử lý.

Câu hỏi bây giờ là: Làm thế nào để biết chúng ta đã lấy được một nửa số chữ số của x? Như ví dụ trên mới chỉ là 1221, theo điều kiện bài toán thì x có thể có giá trị đến tận 2^13 -1, tức là hơn 2 tỷ. Vậy thì chúng ta cần một điều kiện dừng, ở đây vòng lặp sẽ dừng khi mà số x hiện tại (tức là sau khi làm các phép chia cho 10) nhỏ hơn cái số có chứa một nửa số chữ số kia (tạm gọi số này là rev):

Bên trong vòng lặp này, ta thực hiện việc lấy từng chữ số đứng cuối của x rồi gán vào rev với công thức rev = rev * 10 + x % 10. Tại sao lại là rev * 10? Với việc nhân rev với 10, ta có thể thêm chữ số tiếp theo vào phần đơn vị của rev, tức là ta đang đảo ngược dần dần từ cuối đến giữa số x. Ở vòng lặp đầu tiên sẽ trông như thế này:

Vòng lặp tiếp theo rev sẽ là:

Các bạn nhớ là sau khi rev thêm được một chữ số cuối của x thì ta sẽ phải lấy x / 10 để bỏ đi chữ số vừa lấy xong nhé!

Có một vấn đề cần lưu ý, ấy là ở ví dụ minh họa 2, số -121 đảo ngược thì sẽ thành 121-, nghĩa là nó không đối xứng. Vậy tức là ta xét trường hợp nếu x là số âm thì trả về false ngay lập tức, không cần phải đảo làm gì cho mất công.

Thêm nữa, nếu x là một số mà tận cùng của nó là số 0, ví dụ như 20 thì khi đảo ngược sẽ thành 02, và 02 thì có giá trị là 2, mà 2 thì không đối xứng với 20. Ta có thể kết luận ngay, nếu x là số chia hết cho 10 (tức là tận cùng của x là 0) thì sẽ trả về false luôn.

Done! Chúng ta tới bước tiếp theo.

4. Code chạy bằng cơm

4.1. Sử dụng StringBuilder

Với việc sử dụng class StringBuilder chúng ta sẽ cần tạo mới một đối tượng tên sb, đồng thời chuyển số nguyên x về dạng String với method String.valueOf():

Sau đó chúng ta gán hết tất cả chữ số có trong chuỗi strX vào sb với method append():

Sau khi sb đã có hết các chữ số rồi, ta đảo ngược nó bằng method reverse():

Rồi bây giờ chúng ta chỉ việc kiểm tra xem chuỗi sb sau khi đảo ngược có giống với chuỗi strX hay không là xong:

4.2. Sử dụng vòng lặp While

Như lưu ý ở trên, chúng ta kiểm tra ngay xem x có phải số âm hay có phải số có tận cùng là 0 hay không? Nếu có thì trả về false luôn và ngay:

Tiếp theo, chúng ta cần có một số nguyên rev để chứa các chữ số đảo ngược của x, nhưng chỉ đảo ngược đến giữa x mà thôi. Và để làm được điều này, chúng ta sẽ dùng vòng lặp while với và chừng x > rev thì ta còn tiếp tục vòng lặp:

Bên trong vòng lặp này, ta thực hiện việc lấy từng chữ số đứng cuối của x rồi gán vào rev với công thức rev = rev * 10 + x % 10. Cùng với đó ta phải lấy x / 10 để xóa chữ số cuối vừa lấy được xong:

Sau khi đến thời điểm rev >= x, ta sẽ kiểm tra xem rev có bằng x hay không? Lúc này xảy ra hai trường hợp:
Một là x có số chữ số là chẵn (ví dụ 1221), thì ta chỉ việc so sánh rev == x hay không:

Hai là x có số chữ số là lẻ (ví dụ 121). Sau khi chạy xong vòng lặp while kia lúc này x = 1 trong khi đó rev = 12:

Vậy thì làm thế nào để so sánh, trong khi nhìn vào thì ta biết 121 là một số đối xứng? Như đã nói ở trên, khi mà số x là một số lẻ chữ số, ta không cần quan tâm số chính giữa của nó, mà chỉ cần so sánh hai nửa còn lại mà thôi. Vậy nên trong trường hợp này, khi mà kết thúc vòng lặp, rev đã lấy luôn chữ số chính giữa, ta chỉ việc chia rev cho 10 để loại bỏ số chính giữa đó, và so sánh x là xong:

Khi đó trường hợp chúng ta kiểm tra sẽ là:

5. Code thôi bà con ơi

5.1. Sử dụng StringBuilder

Code của chúng ta sẽ như sau:

 public static boolean isPalindrome2(int x) {
     String strX = String.valueOf(x);
     StringBuilder sb = new StringBuilder();

     for (char c : strX.toCharArray()) {
         sb.append(c);
     }

     sb.reverse();

     return sb.toString().equals(strX);
 }

5.2. Sử dụng While

Code viết như sau:

 public static boolean isPalindrome3(int x) {
     if (x < 0 || (x % 10 == 0 && x != 0)) {
         return false;
     }

     int rev = 0;

     while (x > rev) {
         rev = rev * 10 + x % 10;
         x /= 10;
     }

     return x == rev || x == rev/10;
 }

6. Kết thúc

Qua bài viết này, mình đã chia sẻ cho các bạn cách mình tư duy khi giải bài tập trên leetcode. Hi vọng bài viết giúp ích cho các bạn trong cách tư duy để giải các bài tập khác. Xin cám ơn các bạn đã dành thời gian đọc và theo dõi. Peace!!!