7. Reverse Integer

  • Hardness: \(\color{orange}\textsf{Medium}\)
  • Ralated Topics: Math

一、題目

Given a signed 32-bit integer x, return x with its digits reversed. If reversing x causes the value to go outside the signed 32-bit integer range [-2^31, 2^31-1], then return 0.
Assume the environment does not allow you to store 64-bit integers (signed or unsigned).

Example 1:

  • Input: x = 123
  • Output: 321

Example 2:

  • Input: x = -123
  • Output: -321

Example 3:

  • Input: 120
  • Output: 21

Constraints:

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

二、分析

  • 考慮最簡單的翻轉數字為：
int reverse(int x) {
    int res = 0;
    while (x) {
        res = res * 10 + x % 10;
        x /= 10;
    }
    return res;
}
  • 此題的難點在於邊界條件：
    • 若答案超出 [-2^31, 2^31-1] 的範圍，則回傳 0。
    • 不可用 64-bit integer(long)。
  • 我們可以考慮幾個 testcases 來測試邊界條件，如：
    • 2147483647(INT_MAX) \(\rightarrow\) 回傳 0
      • 當 x > 0時，在 res * 10 之前，若 x >= 8，則超出範圍。
    • -2147483648(INT_MIN) \(\rightarrow\) 回傳 0
      • 當 x < 0時，在 res * 10 之前，若 x == -9，則超出範圍。
  • 時間複雜度 \(O(n)\)，\(n\) 為 10 的冪次的絕對值，故 \(O(n)=O(31)=O(1)\)。

三、解題

1. Math

  • Time complexity: \(O(1)\)
  • Space complexity: \(O(1)\)
int reverse(int x) {
    int res = 0;
    while (x) {
        // 考慮邊界條件
        if (res < INT_MIN/10 || (res == INT_MIN/10 && x == -9)) 
            return 0;
        else if (res > INT_MAX/10 || (res == INT_MAX/10 && x >= 8 ))
            return 0;
        // 一般的數字翻轉
        res = res * 10 + x % 10;
        x /= 10;
    }
    return res;
}

回目錄 Catalog