【每日力扣13】整数反转

【每日力扣13】整数反转 一、题目[LeetCode-7]

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

二、思路

本题可以声明一个新的数x_reverse，将输入数x沿逆序加到x_reverse中。具体流程如下：

先通过一个while循环求得x的位数n。（这里将x拷贝到x1，我们处理x1，防止x发生改变）

然后再循环n次。通过与10求余得出x的最低位，加入到x_reverse中，每次循环x除以10迭代，x_reverse乘以10迭代。

本题最麻烦的地方在于特殊情况的讨论。由题目总结出3种特殊情况

1. x为0
2. x为负数
3. x翻转之后会溢出——超出区间[-2^31,2^31 - 1]

class Solution {
public:
    int reverse(int x) {
        const int UPPERLIMITOF32BIT = 2147483647;
    if (x == 0)//【特殊情况1】考虑x等于0的情况
        return 0;
    bool negative = false;
    if (x < 0)//【特殊情况2】考虑x为负数的情况
	{//将负数取绝对值
		if (x == UPPERLIMITOF32BIT * (-1) - 1)//但是要单独讨论一下x == -2147483648的情况，因为正数的上限是2147483647，这时候会溢出。
			return 0;//正好-2147483648转置后是溢出值，所以这种情况直接返回0即可
		x = x * -1;
		negative = true;
	}
    int x1 = x, n = 0;//先拷贝x，用while循环获取位数n
    while (x1 > 0)
    {
        x1 /= 10;
        n++;
    }
    int x_reverse = (x % 10);//从最低位开始将x的数值逆序拷贝入x_reverse中
    x /= 10;
    for (int i = 1; i < n; i++)
    {
        x_reverse *= 10;
        x_reverse += (x % 10);
        x /= 10;
        if (i == 8 && n==10)//【特殊情况3】对于输入x为10位数的情况，为了防止溢出，当拷贝到倒数第二位时先作个判断
            if (x_reverse > UPPERLIMITOF32BIT / 10)//如果到目前为止翻转过来的数已经大于214748364X，则会发生溢出
                return 0;//立即返回0
    }
    if (negative)
        x_reverse *= -1;
    return x_reverse;
    }
};

三、官方解法

 

方法：数学

记 rev 为翻转后的数字，为完成翻转，我们可以重复「d出」xx 的末尾数字，将其「推入」rev 的末尾，直至 x 为 0。

要在没有辅助栈或数组的帮助下「d出」和「推入」数字，我们可以使用如下数学方法：

// d出 x 的末尾数字 digit
digit = x % 10
x /= 10

// 将数字 digit 推入 rev 末尾
rev = rev * 10 + digit

 

题目需要判断反转后的数字是否超过 32 位有符号整数的范围 ，例如整数x=2123456789 反转后的 rev=9876543212>-1=2147483647，超过了 32 位有符号整数的范围。

因此我们需要在「推入」数字之前，判断是否满足

若该不等式不成立则返回 00。

但是题目要求不允许使用 64 位整数，即运算过程中的数字必须在 32 位有符号整数的范围内，因此我们不能直接按照上述式子计算，需要另寻他路。

考虑 x>0 的情况，记，由于

                        

则不等式

等价于

移项得

讨论该不等式成立的条件：

若 left lfloor INT_MAX/10 right rfloor" src="https://latex.codecogs.com/gif.latex?rev%3E%20%5Cleft%20%5Clfloor%20INT%5C_MAX/10%20%5Cright%20%5Crfloor" />，由于 digit≥0，不等式不成立。

若，当且仅当 digit≤7 时，不等式成立。

若，由于digit≤9，不等式成立。

注意到当时若还能推入数字，则说明 x 的位数与INT_MAX的位数相同，且要推入的数字 digit 为 x 的最高位。由于 x 不超过 INT_MAX，因此 digit 不会超过 INT_MAX 的最高位，即 digit≤2。所以实际上当时不等式必定成立。

因此判定条件可简化为：当且仅当时，不等式成立。x<0 的情况类似。

综上所述，判断不等式

是否成立，可改为判断不等式

是否成立，若不成立则返回 0。 

class Solution {
public:
    int reverse(int x) {
        int rev = 0;
        while (x != 0) {
            if (rev < INT_MIN / 10 || rev > INT_MAX / 10) {
                return 0;
            }
            int digit = x % 10;
            x /= 10;
            rev = rev * 10 + digit;
        }
        return rev;
    }
};

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/reverse-integer/solution/zheng-shu-fan-zhuan-by-leetcode-solution-bccn/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

复杂度分析

• 时间复杂度：O(log |x|)。翻转的次数即 x 十进制的位数。

• 空间复杂度：O(1)。

四、学习心得

对于复杂特殊情况的讨论——32位整数溢出区间。