LeetCode【7】-- 整数反转

• 💻 剑指Offer & LeetCode刷题仓库：https://github.com/Damaer/CodeSolution
  • 文档地址：https://damaer.github.io/CodeSolution/
  • 仓库介绍：刷题仓库：CodeSolution
• 📒 编程知识库：https://github.com/Damaer/Coding
  • 文档地址：https://damaer.github.io/Coding/#/

题目

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

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

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

示例 1：

输入：x = 123 输出：321

示例 2：

输入：x = -123 输出：-321

示例 3：

输入：x = 120 输出：21

示例 4：

输入：x = 0 输出：0

来源：力扣（LeetCode）

思路以及解答

这是一道简单题，我在某东南亚电商的面试中遇到过，看得出面试官想让我过，其实这道题考察两个点：

• 取余数和整除
• 反转溢出的处理

首先定义结果为：sum = 0

用123作为例子，对 10 整除的结果是 12 ，余数是 3 , sum = sum * 10 + 3 = 3

12 对 10 整除的结果是 1，余数是 2，sum = sum * 10 + 2 = 32

1 对 10 整除的结果是 0，余数是 1，sum = sum * 10 + 1 = 321

核心的代码无非是：

sum = sum * 10 + x % 10;
x = x / 10;

但是里面有一个坑点，那就是反转之后，可能会出现溢出，举个简单的小栗子，假设数值的范围是 -128~127, 有一个数是108，反转之后变成801了，那肯定是不符合要求的，超过数字的范围了。

针对这种情况，我们可以在加和之前判断，针对大于0的情况，如果大于最大值整除10，或者等于最大值整除10，但是个位数超过了，都直接返回0。

假设最大值是127，那么sum如果大于12，肯定会超过，如果sum ==12，但是个位数大于7，乘以10相加，也肯定会超。

if (sum > Integer.MAX_VALUE/10 || (sum == Integer.MAX_VALUE / 10 && x > 7)) return 0;

对于小于0的情况，假设最小值是-128，那么sum如果小于-12（因为是负数，所以是小于），那么就一定超出，或者sum == -12，但是个位数小于-8，乘以10，相加也会小于-128，不符合要求，所以直接返回0。

if (sum < Integer.MIN_VALUE/10 || (sum == Integer.MIN_VALUE / 10 && x < -8)) return 0;

具体的代码实现：

class Solution {
    public int reverse(int x) {
        int sum = 0;
        while (x != 0) {
            if (sum > Integer.MAX_VALUE/10 || (sum == Integer.MAX_VALUE / 10 && x > 7)) return 0;
            if (sum < Integer.MIN_VALUE/10 || (sum == Integer.MIN_VALUE / 10 && x < -8)) return 0;
            sum = sum * 10 + x % 10;
            x = x / 10;

        }
        return sum;
    }
}

C++ 代码实现：

#include<iostream>
using namespace std;
class Solution {
public:
    int reverse(int x) {
        int sum = 0;
        while (x != 0) {
            if (sum > INT_MAX/10 || (sum == INT_MAX / 10 && x > 7)) return 0;
            if (sum < INT_MIN/10 || (sum == INT_MIN / 10 && x < -8)) return 0;
            sum = sum * 10 + x % 10;
            x = x / 10;
            
        }
        return sum;
    }
};
int main(){
    Solution solution;
    cout<< solution.reverse(123)<<endl;
    return 0;
}

• 时间复杂度：O(log|x|),以10为底数的对数。
• 空间复杂度：O(1)。

【作者简介】

秦怀，公众号【秦怀杂货店】作者，技术之路不在一时，山高水长，纵使缓慢，驰而不息。个人写作方向：Java源码解析，JDBC，Mybatis，Spring，Redis，分布式，剑指Offer，LeetCode等，认真写好每一篇文章，不喜欢标题党，不喜欢花里胡哨，大多写系列文章，不能保证我写的都完全正确，但是我保证所写的均经过实践或者查找资料。遗漏或者错误之处，还望指正。

平日时间宝贵，只能使用晚上以及周末时间学习写作

- END -