给你一个 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

提示：

  • -231 <= x <= 231 - 1

思路

先不考虑溢出的情况，基本思路是，只需每次取出x的个位，将其添加到翻转数字的个位上即可。

class Solution {
public:
    int reverse(int x) {
        int res = 0;
        while (x != 0) {
         		// 将x的个位添加到result的个位上
            res *= 10;
            res += x % 10;
            x /= 10;
        }
        return res;
    }
};

这个思路对于正数来说显然是没问题的，但是对于负数，我们需要简单证明一下这个算法的正确性。

对于负数的情况，我们需要首先回忆负数是如何取模的（此处仅说明C++/Java）中的情况。计算余数的过程是，首先算出商，然后用被除数减去商乘以除数，因此，余数仅由商决定（在除数确定的情况下）。

举个例子，计算10%3时，首先计算10/3，得到商为3，然后计算余数：10-3*3=1，就得到了余数。对于负数的运算也是一样的，比如10%-3，由于C++和Java中除法是向零舍入，所以商是-3，余数就是10-(-3*-3)=1。

总结一下，除法的取整分为三类：向上取整、向下取整、向零取整。

  1. 向上取整：向+∞方向取最接近精确值的整数。在这种取整方式下，7/4=2，7/(-4)=-1，6/3=2，6/(-3)=-2。
  2. 向下取整：向-∞方向取最接近精确值的整数。在这种取整方式下，7/4=1，7/(-4)=-2，6/3=2，6/(-3)=-2。
  3. 向零取整：向0方向取最接近精确值的整数，换言之就是舍去小数部分，因此又称截断取整。C++/Java的原则即是向零舍入。

因此，计算-123的翻转整数时，计算出来的余数分别是-3，-2，-1，最终结果就是-3*100-2*10-1，该算法是正确的。

在上述算法的情况下，我们考虑如何处理翻转整数溢出的问题。不难发现，每次计算result时，都是先将result乘10，然后将x的个位加到result 上。因此在保证不溢出的情况下，得到一个不等式： 即 只要result满足此不等式，即可保证结果不溢出。最终版本的算法如下：

class Solution {
public:
    int reverse(int x) {
        int res = 0;
        while (x != 0) {
            // 0x7fffffff > res * 10 + x % 10 > 0x80000000
            if (res > (int)0x7FFFFFFF / 10 || res < (int)0x80000000 / 10) return 0;
            res *= 10;
            res += x % 10;
            x /= 10;
        }
        return res;
    }
};

算法复杂度

  • 时间复杂度：。
  • 空间复杂度：