Skip to content

LeetCode: 7-Reverse Integer 解題紀錄

Last Updated on 2021-01-04 by Clay

題目

Given a 32-bit signed integer, reverse digits of an integer.

Note:
Assume we are dealing with an environment that could only store integers within the 32-bit signed integer range: [−231,  231 − 1]. For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.

Example:

Input: x = 123
Output: 321

Input: x = -123
Output: -321

本題給定一個 32-bit 的整數值，我們要將其數值前後對調，但要保證並不會發生 overflow。（若是反轉後 overflow 則回傳 0）

解題思路

這題我很直覺地使用以下步驟解題：

  • 將數值轉成字串
  • 反轉
  • 比較 INT_MAX 和 INT_MIN 少一位數的大小（若相同時，則再比較個位數）

而在解題之後參考討論區的答案，這才發現其實可以不用轉成字串，一直連除 10 即可，不僅快也相當節省記憶體。


C++ 程式碼

class Solution {
public:
    int reverse(int x) {
        // Init
        string s = std::to_string(x);
                
        if (s[0] == '-' and s.size() > 2) {
            std::reverse(s.begin(), s.end());
            s.pop_back();
            s = '-' + s;
            if (std::stoi(s.substr(0, s.size()-1)) < INT_MIN/10) return 0;
            if (std::stoi(s.substr(0, s.size()-1)) == INT_MIN/10 and std::stoi(s.substr(s.size()-1, 1)) > 8) return 0;

        }
        else if (s.size() > 1) {
            std::reverse(s.begin(), s.end());
            if (std::stoi(s.substr(0, s.size()-1)) > INT_MAX/10) return 0;
            if (std::stoi(s.substr(0, s.size()-1)) == INT_MAX/10 and std::stoi(s.substr(s.size()-1, 1)) > 7) {
                return 0;
            }
        }
        
        return std::stoi(s);
    }
};


Python 程式碼

class Solution:
    def reverse(self, x: int) -> int:
        s = str(x)
        s = s[::-1]

        if s[-1] == '-':
            s = '-' + s[:-1]

        ans = int(s)
        if ans > 2147483647 or ans < -2147483648:
            return 0
        
        return ans


這一題使用 Python 解題都快要讓我有作弊的感覺了 XDDDD

怎麼說呢，它的語言特性解題時真的太誇張了。不過反過來說，這樣可能稍嫌沒有鍛鍊到本題要考的重點，也算是某種程度上的缺點。

References

Tags:

Leave a Reply