LeetCode刷题笔记 07 Reverse Integer

作者：马志峰 链接：https://zhuanlan.zhihu.com/p/23967316 来源：知乎 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

链接

https://leetcode.com/problems/zigzag-conversion/

题目

例1：x = 123, 返回 321 例2：x = -123, 返回 -321

看上去规则很简单，但是有一些特殊的场景你想到了吗？

出题的人也是语重心长，先把提示折叠了起来，再三的提醒我们要多思考

对，思考一下有哪些特殊场景再往下看

好了，如果你确实思考过了，下面是题目给出提示：

如果后面几位是0，我们的输出应该是什么样的？比如10100？你是否意识到，反转后的整数可能溢出？如果是32位的整数，它的最大值是2147483648，那么1000000003反转后将溢出，对于这种情况，我们要求输出0

函数定义

leetcode给定的函数定义是这样的：

class Solution { public: int reverse(int x) { } };

解题思路

如果不考虑溢出的话，这道题目的思路很容易想到：

得到每一位上的数字，可以利用整数的除法和取余运算，要写个循环，第1次除以10，第2次除以100。。。对于得到的数字序列，第1位乘以1，第2位乘10，第3位乘以100。。。，然后相加得到反转数

对于溢出，简单粗暴的方法就是看看try…catch…适不适合

如果适合的话直接在catch里面return 0就好了如果不适合的话，我们还要找出整数类型的最大值

伪码

x = 123; x对10求余得到3，x除以10得到12 12对10求余得到2， x除以10得到1 1对10求余得到1，x除以10得到0

1*1 + 2*10 + 3*100 = 321

代码

class Solution { public: int reverse(int x) { if (x < 10 && x > -10) { return x; } vector<int> vecDigits; int iTemp = x; do { vecDigits.push_back(iTemp % 10); iTemp = iTemp / 10; } while (iTemp != 0); auto iSize = vecDigits.size(); int iFactor = 1; int iResult = 0; for (auto i = iSize - 1; i >= 0; --i) { iResult += iFactor * vecDigits[i]; iFactor *= 10; } return iResult; } };

代码写好之后，把x=123代入进去验算一下

嗯，看上去一切都挺好的。

但是提交上去却出现“Runtime Error” ! 为什么？！

如果想不明白可以回过头去看一下《c++ primer》第34页

是的，死循环了。悲催的。当时看书的时候觉得自己不会犯这种错误。。。

class Solution { public: int reverse(int x) { if (x < 10 && x > -10) { return x; } vector<int> vecDigits; int iTemp = x; do { vecDigits.push_back(iTemp % 10); iTemp = iTemp / 10; } while (iTemp != 0); auto i = vecDigits.size(); int iFactor = 1; int iResult = 0; while (i > 0) { --i; iResult += iFactor * vecDigits[i]; iFactor *= 10; } return iResult; } };

再提交代码来看，报的就是溢出的错误了，那是因为我们还没有处理这种情况

我们把输入改成很大的数之后，发现运行时并没有出异常。还是老老实实的用边界值来判断

这个实现在是没想到好的解决办法，就看了下讨论区

https://discuss.leetcode.com/topic/287/how-do-we-handle-the-overflow-case/12

https://discuss.leetcode.com/topic/6005/shortest-code-possible-in-c

我们参考其中的一个修改代码

class Solution { public: int reverse(int x) { if (x < 10 && x > -10) { return x; } vector<int> vecDigits; int iTemp = x; do { vecDigits.push_back(iTemp % 10); iTemp = iTemp / 10; } while (iTemp != 0); auto i = vecDigits.size(); long long iFactor = 1; long long iResult = 0; while (i > 0) { --i; iResult += iFactor * vecDigits[i]; iFactor *= 10; } if (iResult > INT_MAX || iResult < INT_MIN) { return 0; } return iResult; } };

好吧，终于Accepted了。

不过看讨论区我们就能发现两个循环是可以合并的，这个就留给大家了

另外，还可以尝试把整数转换成string来试试~