当前位置：首页 > news >正文

【力扣】整数反转，判断是否溢出的数学解法

news 2025/9/11 19:04:48

整数反转原题地址

方法一：数学

反转整数

如何反转一个整数呢？考虑整数操作的3个技巧：

xmod10 可以取出 x 的最低位，如 x=123 ， xmod10=3 。
x/=10 可以去掉 x 的最低位，如 x=123 ， x/=10 ， x=12 。
x=x*10+y 可以在 x 后面续上 y ，其中 y 是一位数，如 x=123 ， y=4 ， x=x*10+y ， x=1234 。

假设要反转的整数为 x ，反转后的整数存储在变量 rev 中， rev 一开始初始化为 0 ，那么反复执行以下操作：

digit=xmod10 ，取出 x 的最低位数。
x/=10 ，去掉 x 的最低位数。
rev=rev*10+digit ，在 rev 后面续上 digit 。

直到 x 为 0 为止，此时 rev 存储的数据符合题目要求。

判断溢出

问题在于，如何判断插入后的数据是否超出 [INT_MIN,INT_MAX] 的范围，导致溢出？

我们来探索不等式 $INT\_MIN\leqslant n\leqslant INT\_MAX$ 成立的充分必要条件。

先看右半边，即 $n\leqslant INT\_MAX$ 。

对于任意整数 i ，我们有 $i=\left \lfloor \frac{i}{10} \right \rfloor\times 10+i mod 10$ ，如对于 123 ， 123/10=12 ， 123mod10=3 ， 123=12*10+3 。

不等式化为： $\left \lfloor \frac{n}{10} \right \rfloor\times 10+n mod 10=\left \lfloor \frac{INT\_MAX}{10} \right \rfloor\times 10+INT\_MAX mod 10$ ，带入 $INT\_MAXmod10=7$ ， $\left \lfloor \frac{n}{10} \right \rfloor=rev$ ， $nmod10=digit$ ， $0\leqslant digit\leqslant 9$

移项化简得： $(rev-\left \lfloor \frac{INT\_MAX}{10} \right \rfloor)\times 10\leqslant 7-digit$ ，记 $\left \lfloor \frac{INT\_MAX}{10} \right \rfloor=m$ ，

当 rev=m 时，如果还要推入数字，那么 digit≤2 ，因为 INT_MAX 的最高位为 2 ，此时不等式左边等于 0 ，右边为正数，不等式恒成立。
当 rev>m 时，不等式左边至少是 10 ，右边至多是 7 ，不等式恒不成立。
当 rev<m 时，不等式左边至多是 -10 ，右边至少是 7-9=-2 ，不等式恒成立。

所以原不等式右半边成立的充分必要条件是 $rev\leqslant m$ ，即 $rev\leqslant\left \lfloor \frac{INT\_MAX}{10} \right \rfloor$ 。同理左半边成立的充分必要条件是 $rev\geqslant \left \lceil \frac{INT\_MIN}{10} \right \rceil$ 。

原不等式成立的充分必要条件是 $\left \lceil \frac{INT\_MIN}{10} \right \rceil\leqslant rev\leqslant\left \lfloor \frac{INT\_MAX}{10} \right \rfloor$ 。

// 方法一：数学
class Solution
{
public:int reverse(int x){int rev = 0;while (x){if (rev < INT_MIN / 10 || rev > INT_MAX / 10){return 0;}// rev 后面续上 x 的最低位rev = rev * 10 + x % 10;// 去掉 x 的最低位x /= 10;}return rev;}
};

查看全文

http://www.lryc.cn/news/307084.html