做网站要用到哪些架包,网站定制怎么收费,免费模板的软件,做外贸客户要求看网站一、题目描述
给你一个 32 位的有符号整数 x #xff0c;返回将 x 中的数字部分反转后的结果。
如果反转后整数超过 32 位的有符号整数的范围 [−231, 231 − 1] #xff0c;就返回 0。
假设环境不允许存储 64 位整数#xff08;有符号或无符号#xff09;。
示例 1返回将 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
二、题解
记 r e v rev rev 为翻转后的数字为完成翻转我们可以重复「弹出」 x x x 的末尾数字将其「推入」 r e v rev rev 的末尾直至 x x x 为 0。
要在没有辅助栈或数组的帮助下「弹出」和「推入」数字我们可以使用如下数学方法
// 弹出 x 的末尾数字 digit
digit x % 10
x / 10// 将数字 digit 推入 rev 末尾
rev rev * 10 digit题目需要判断反转后的数字是否超过 32 位有符号整数的范围 [ − 2 31 , 2 31 − 1 ] [-2^{31},2^{31}-1] [−231,231−1]例如 x 2123456789 x2123456789 x2123456789 反转后的 r e v 9876543212 2 31 − 1 2147483647 rev98765432122^{31}−12147483647 rev9876543212231−12147483647超过了 32 位有符号整数的范围。
因此我们需要在「推入」数字之前判断是否满足 − 2 31 ≤ r e v ⋅ 10 d i g i t ≤ 2 31 − 1 −2^{31}≤rev⋅10digit≤2^{31}−1 −231≤rev⋅10digit≤231−1 若该不等式不成立则返回 000。
但是题目要求不允许使用 64 位整数即运算过程中的数字必须在 32 位有符号整数的范围内因此我们不能直接按照上述式子计算需要另寻他路。
考虑 x 0 x0 x0 的情况记 I N T M A X 2 31 − 1 2147483647 INT_MAX2^{31}−12147483647 INTMAX231−12147483647由于 INT_MAX ⌊ INT_MAX 10 ⌋ ⋅ 10 ( INT_MAX m o d 10 ) ⌊ INT_MAX 10 ⌋ ⋅ 10 7 \begin{aligned} \textit{INT\_MAX}\lfloor\dfrac{\textit{INT\_MAX}}{10}\rfloor\cdot10(\textit{INT\_MAX}\bmod10)\\ \lfloor\dfrac{\textit{INT\_MAX}}{10}\rfloor\cdot107 \end{aligned} INT_MAX⌊10INT_MAX⌋⋅10(INT_MAXmod10)⌊10INT_MAX⌋⋅107
则不等式 rev ⋅ 10 digit ≤ INT_MAX \textit{rev}\cdot10\textit{digit}\le\textit{INT\_MAX} rev⋅10digit≤INT_MAX
等价于 r e v ⋅ 10 d i g i t ≤ ⌊ I N T _ M A X 10 ⌋ ⋅ 10 7 rev⋅10digit≤⌊INT\_MAX10⌋⋅107 rev⋅10digit≤⌊INT_MAX10⌋⋅107
移项得 ( r e v − ⌊ I N T _ M A X 10 ⌋ ) ⋅ 10 ≤ 7 − d i g i t (rev−⌊INT\_MAX10⌋)⋅10≤7−digit (rev−⌊INT_MAX10⌋)⋅10≤7−digit
讨论该不等式成立的条件
若 r e v ⌊ I N T _ M A X 10 ⌋ rev⌊INT\_MAX10⌋ rev⌊INT_MAX10⌋由于 d i g i t ≥ 0 digit≥0 digit≥0不等式不成立。 若 r e v ⌊ I N T _ M A X 10 ⌋ rev⌊INT\_MAX10⌋ rev⌊INT_MAX10⌋当且仅当 d i g i t ≤ 7 digit≤7 digit≤7 时不等式成立。 若 r e v ⌊ I N T _ M A X 10 ⌋ rev⌊INT\_MAX10⌋ rev⌊INT_MAX10⌋由于 d i g i t ≤ 9 digit≤9 digit≤9不等式成立。
注意到当 r e v ⌊ I N T _ M A X 10 ⌋ rev⌊INT\_MAX10⌋ rev⌊INT_MAX10⌋ 时若还能推入数字则说明 x x x 的位数与 I N T _ M A X INT\_MAX INT_MAX 的位数相同且要推入的数字 d i g i t digit digit 为 x x x 的最高位。由于 x x x 不超过 I N T _ M A X INT\_MAX INT_MAX因此 d i g i t digit digit 不会超过 I N T _ M A X INT\_MAX INT_MAX 的最高位即 d i g i t ≤ 2 digit≤2 digit≤2。所以实际上当 r e v ⌊ I N T _ M A X 10 ⌋ rev⌊INT\_MAX10⌋ rev⌊INT_MAX10⌋ 时不等式必定成立。
因此判定条件可简化为当且仅当 r e v ≤ ⌊ I N T _ M A X 10 ⌋ rev≤⌊INT\_MAX10⌋ rev≤⌊INT_MAX10⌋ 时不等式成立。 x 0 x0 x0 的情况类似留给读者自证此处不再赘述。
综上所述判断不等式 − 2 31 ≤ r e v ⋅ 10 d i g i t ≤ 2 31 − 1 −2^{31}≤rev⋅10digit≤2^{31}−1 −231≤rev⋅10digit≤231−1 是否成立可改为判断不等式 ⌈ − 2 3 1 10 ⌉ ≤ r e v ≤ ⌊ 2 31 − 1 10 ⌋ ⌈\frac{−2^31}{10}⌉≤ rev ≤⌊\frac{2^{31}−1}{10}⌋ ⌈10−231⌉≤rev≤⌊10231−1⌋ 是否成立若不成立则返回 0。
Python def reverse(self, x: int) - int:INT_MIN, INT_MAX -2**31, 2**31 - 1rev 0while x ! 0:# INT_MIN 也是一个负数不能写成 rev INT_MIN // 10if rev INT_MIN // 10 1 or rev INT_MAX // 10:return 0digit x % 10# Python3 的取模运算在 x 为负数时也会返回 [0, 9) 以内的结果因此这里需要进行特殊判断if x 0 and digit 0:digit - 10# 同理Python3 的整数除法在 x 为负数时会向下更小的负数取整因此不能写成 x // 10x (x - digit) // 10rev rev * 10 digitreturn revC
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;
}复杂度分析
时间复杂度 O ( l o g ∣ x ∣ ) O(log∣x∣) O(log∣x∣)。翻转的次数即 x x x 十进制的位数。空间复杂度 O ( 1 ) O(1) O(1)。