第1.2篇·整数反转

算法是求职的敲门砖，大厂面试一面几乎都会问算法题，以此来考察候选人的思维逻辑及编码能力。

今天要AC的题目叫做「整数反转」，在 leetcode 上的原题链接为：https://leetcode-cn.com/problems/reverse-integer/。

1. 题目

给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。

如果反转后整数超过 32 位的有符号整数的范围 [−2^31, 2^31 − 1] ，就返回 0。

假设环境不允许存储 64 位整数（有符号或无符号）。

示例 1： 输入：x = 123 输出：321 示例 2： 输入：x = -123 输出：-321 示例 3： 输入：x = 120 输出：21 示例 4： 输入：x = 0 输出：0

提示：-2^31 <= x <= 2^31 - 1

2. 解题思路

题目意思非常简单，输入一个32位的有符号整数，倒序输出这个整数，如输入123，就输出321；输入-123就输出-321；输入120就输出21。

题目已经限定了输入整数的范围是[−2^31, 2^31 − 1]，即[-2147483648, 2147483647]。

正常整数的反转十分简单，只需要对入参进行循环，每次对入参进行10的取模，将结果累加到返回值中并乘以10，这样最终得到的数字就是反转后的整数。

举个例子，对于123进行循环：

1. 第一次循环
   1. 对123进行10的取模，得到结果3，
   2. 返回值 = 返回值乘以10再加上3，即 0*10+3=3；
   3. 入参变更为12
2. 第二次循环
   1. 对12进行10的取模，得到结果2，
   2. 返回值 = 返回值乘以10再加上2，即 3*10+2=32；
   3. 入参变更为1
3. 第三次循环
   1. 对1进行10的取模，得到结果1，
   2. 返回值 = 返回值乘以10再加上2，即 32*10+1=321；
   3. 入参变更为0
4. 循环至此结束，返回值=321，实现了整数反转

这样做的前提是入参是正常整数，既然题目已经提到限定了输入整数的范围，同时提到“如果反转后整数超过 32 位的有符号整数的范围，就返回0”，那么我们就不得不考虑整数溢出的情况。

以下参考的是 LFool 同学的题解思路：https://leetcode-cn.com/problems/reverse-integer/solution/by-lfool-1x23/

所以问题就来到了如何判断溢出？

事实上，在我用数组承载入参，使用暴力解法来解题的过程中，进行过提交，其中有一次就是用例溢出了，入参是1534236469，它的反转结果理论上是9646324351，但是它超过了 32 位的有符号整数的范围（大于2147483647），所以根据题意返回的结果应该是0。而我提交的代码返回的结果却是2147483647。

在 debug 时发现，进行数字9的运算时发生了溢出，导致最终结果异常。

如果考虑到溢出问题，那么入参的每一位在反转的时候都可能发生溢出。结合我们在反转时使用到的运算：返回值 = 返回值乘以10再加上取模结果，正常情况下，若未发生溢出，那么在每次循环中这一步运算后再除以10，则返回值不会发生变化。

即（返回值 * 10 + 取模结果）/ 10 = 返回值，我们可以通过这个等式来判断是否发生溢出。

用 Java 实现上述的思路就是：

上述示例代码在 leetcode 上的执行结果是：

最后，本文收录于个人语雀知识库: 我所理解的后端技术，欢迎来访。