题目大意:反转一个整数,比如123反转后为321,-123反转后为-321.你需要注意的情况有:如果整数末尾有0该如何处理,如果溢出该怎么处理.
#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 */
这里主要的困难点是如何尽可能的想到所有的溢出情况.我的处理方式,比较简单粗暴,就是先取绝对值,用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).