Bài 7 Leetcode: Reverse Integer

Đề bài:

Cho một số nguyên có dấu 32-bit x, trả về số x sau khi đảo ngược các chữ số của nó. Nếu việc đảo ngược x làm cho giá trị vượt ngoài phạm vi số nguyên có dấu 32-bit [-2³¹, 2³¹ – 1], thì trả về 0.

Giả định rằng môi trường không cho phép bạn lưu trữ số nguyên 64-bit (có dấu hoặc không dấu).

Ví dụ 1:

Input: x = 123
Output: 321

Ví dụ 2:

Input: x = -123
Output: -321

Ví dụ 3:

Input: x = 120
Output: 21

Ràng buộc:

• -2³¹ <= x <= 2³¹ – 1

Giải thích thuật toán bằng C++

class Solution {
 public:
  int reverse(int x) {
    long ans = 0;

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

    return (ans < INT_MIN || ans > INT_MAX) ? 0 : ans;
  }
};

Đoạn mã trên triển khai thuật toán để đảo ngược các chữ số của một số nguyên x. Dưới đây là giải thích chi tiết về cách thuật toán hoạt động:

1. Khởi tạo biến `ans` kiểu `long` với giá trị ban đầu là 0. Biến `ans` được sử dụng để lưu giá trị đảo ngược của số x.
2. Sử dụng vòng lặp while để thực hiện việc đảo ngược các chữ số của số x.
3. Trong mỗi lần lặp, nhân `ans` cho 10 và cộng với phần dư của x khi chia cho 10 (`x % 10`). Điều này giúp đưa chữ số cuối cùng của x lên đầu của ans và dịch các chữ số cũ sang phải.
4. Sau đó, chia x cho 10 để xóa chữ số cuối cùng của nó (`x /= 10`).
5. Lặp lại quá trình trên cho đến khi x trở thành 0, tức là đã xử lý tất cả các chữ số của x.
6. Kiểm tra xem giá trị của `ans` có vượt quá phạm vi số nguyên có dấu 32-bit [-2³¹ , 2³¹ – 1] hay không. Nếu vượt quá, trả về 0. Ngược lại, trả về `ans` như là kết quả đảo ngược của x.
7. Lưu ý rằng vì biến `ans` được khai báo là kiểu `long`, nó có thể lưu trữ các giá trị nằm ngoài phạm vi số nguyên 32-bit.

Thuật toán này sử dụng phép toán modulo và chia để trích xuất và loại bỏ các chữ số của số x. Bằng cách cộng dồn các chữ số theo thứ tự đảo ngược, thuật toán tạo ra một số mới là kết quả của việc đảo ngược các chữ số của x. Nếu kết quả nằm ngoài phạm vi số nguyên 32-bit, thuật toán trả về 0.

Giải thích thuật toán bằng Java

class Solution {
  public int reverse(int x) {
    long ans = 0;

    while (x != 0) {
      ans = ans * 10 + x % 10;
      x /= 10;
    }

    return (ans < Integer.MIN_VALUE || ans > Integer.MAX_VALUE) ? 0 : (int) ans;
  }
}

Giải thích thuật toán bằng Python

class Solution:
  def reverse(self, x: int) -> int:
    ans = 0
    sign = -1 if x < 0 else 1
    x *= sign

    while x:
      ans = ans * 10 + x % 10
      x //= 10

    return 0 if ans < -2**31 or ans > 2**31 - 1 else sign * ans