7. Reverse Integer

題目網址：https://leetcode.cn/problems/reverse-integer/

題意：給一 32-bit 的有號整數 x, 返回將 x 中的數字部分反轉後的結果。

如果反轉後的整數超過 32-bit 的有號整數的範圍 [−$2^{31}$,  $2^{31}$ − 1], 則返回 0。

假設不允許儲存 64-bit 整數（有號 or 無號）, 也就是說結果只能用 int 來儲存, 不允許用 long 之類的 data type。

Solution：

想法：int 的範圍是 [-2147483648, 2147483647], 因此在執行 res = (10 * res) + (x % 10) 前, 要先判斷這樣做是否會 overflow

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

        while (x) {
            // 避免下面 (10 * res) + (x % 10) 時, 正整數會 overflow
            if (res > INT_MAX / 10 || (res == INT_MAX / 10 && x % 10 > 7)) {
                return 0;
            }

            // 避免下面 (10 * res) + (x % 10) 時, 負整數會 overflow
            if (res < INT_MIN / 10 || (res == INT_MIN / 10 && x % 10 < -8)) {
                return 0;
            }

            res = (10 * res) + (x % 10);
            x /= 10;
        }

        return res;
    }
};

• time：$O(log(x))$ ➔ $\dfrac{x}{10^k} = 1$, 得 $k = log(x)$
• space：$O(1)$ ➔ 只需常數空間