7. Reverse Integer

problem description

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

Example 1:

Input: 123
Output: 321

Example 2:

Input: -123
Output: -321

Example 3:

Input: 120
Output: 21

Note:

Assume we are dealing with an environment which 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.

algorithm thought

初次拿到这题想到的方法肯定是，首先判断正负，然后按位处理。每次取模得到个位，将得到的个位加到存储的结果中。这种想法是没有问题，但是我觉得用字符串翻转更加易懂，并且需要考虑的条件比较少。首先判断正负，然后将数字转化为字符串。之后调用翻转函数。最后将翻转过的字符串变回数字，这时候要注意的是，首先处理末尾的0，这时候会被翻转到首位，然后考虑如果现在字符串大于INT_MAX,也就是2^31-1，就直接返回0。

code

class Solution {
public:
    int reverse(int x) {
        bool bo=true;
        if(x<0){
            if(x==INT_MIN)
                return 0;
            bo=false;
            x=-x;
        }
        string s = to_string(x);
        std::reverse(s.begin(),s.end());
        int i=0;
        while(s[i]=='0')
            i++;
        s.erase(0,i);
        //cout<<s<<' '<< (s>"2147483647");
        if(s.size()>10||(s.size()==10&&s>"2147483647"))
            return 0;
        i=atol(s.c_str());
        return bo?i:-i;
    }
};

algorithm analysis

在整个算法中，to_string时间复杂度是O(n),reverse函数时间复杂度是O(n)，最后atol函数函数的时间复杂度也是O(n).算法中其他部分时间复杂度是O(1)。所以最后时间复杂度是O(n)。其实感觉直接用数学方法，每位处理可能比这个快一点，但是用字符串操作数字翻转问题还是很舒服的。