[Leetcode] 7. Reverse Integer

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