Reverse Integer

题目大意:反转一个整数,比如123反转后为321,-123反转后为-321.你需要注意的情况有:如果整数末尾有0该如何处理,如果溢出该怎么处理.

Solution

#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <climits>
using namespace std;
class Solution
{
public:
   int reverse(int x)
   {
       /* INT_MAX=2147483647    INT_MIN=-2147483648 */
       //x在使用log10时不能为0
       if(x == 0) return 0;
       //符号位
       int sign = x < 0 ? -1 : 1;
       //取x的绝对值:可能溢出
       if(x * 1.0 * sign > INT_MAX) return 0;
       x = x * sign;
       //求位数:p进制整数k的位数为:floor(log_p(k))+1
       //可用用换底公式求:log_p(k)=log10(k)/log10(p)
       int k = log10(x * 1.0) + 1;
       double rx = 0 ;
       for(int i = k - 1;i >= 0; --i)
       {
           //溢出判断
           if(rx > INT_MAX) return 0;
           int d = x % 10;
           x = (x - d) / 10;
           rx += d * pow(10,i);
       }
       return sign * (int)(rx);
   }
};
//=======================Driver===========================
int main()
{
    Solution sol;
    //cout<<INT_MAX<<"\t"<<INT_MIN<<endl;
    //cout<<sol.reverse(0)<<endl;
    cout<<sol.reverse(-2147483648)<<endl;
    return 0;
}


/*
===========complexity==============
Time Complexity:O(1) 
Space Complexity:O(1)
===========makefile=================
all:
    @g++  solve.cpp -o   solve
    @./solve
clean:
    rm -f solve
    reset
===========leetcode accepted========
1032 / 1032 test cases passed.
Status: Accepted
Runtime: 9 ms
Submitted: 0 minutes ago
===========submission date=========
2017-01-15 Sun 11:25 PM
*/

Analysis

正如你所想的,这道题在思维上而言,是相当简单的.但是这题容易做对么,不那么容易.

这里主要的困难点是如何尽可能的想到所有的溢出情况.我的处理方式,比较简单粗暴,就是先取绝对值,用double类型来处理, 然后看看是否超过了INT_MAX,如果溢出了,则返回零.返回的反转数也是用double存储,在没有溢出的情况下强制转化为int型,我提交了三次代码才AC掉, 主要是可能溢出的地方考虑不周到.

在使用C/C++提供的数学函数时,应注意边界条件,比如log10(x)这个函数,在数学上要求x>0,那么编码的时候,理应考虑到这种"天然"限制条件的情况.

这里我用了一个小技巧,就是用数学知识来快速求得一个整数的位数,对于进制为p,数值为k的整数,其包含的数位d可以用下面的式子计算: $$ d = \lfloor log_pk \rfloor + 1$$ 这个函数我在学习组合数学的时候做了笔记,所以记得很清楚, Wikipedia上也有,我在此就简要的证明一下: $\forall n \in Z$,如389,共3位,我们知道,3位数的范围是100~999,若n为一个三位数,则$100\leq n \leq 999$,也即$10^2 \leq n < 10^3,\therefore 10^2-1 < n \leq 10^3-1$, 类似地,对于数n,若为d位,则有$10^{d-1} - 1 < n \leq 10^d-1$,因此$10^{d-1} < n+1 \leq 10^d$,以10为底数,则$d-1 < log_{10}(n+1) \leq d$,于是$d=\lceil log_{10}(n+1) \rceil = \lfloor log_{10}(n) \rfloor +1$

代码应该是很好理解了,不再赘述.时间复杂度,由于整形最大不超过INT_MAX的数位,所以可以认为是O(1),空间复杂度O(1).