本文主要是介绍第七题:整数反转(Reverse Integer),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目描述:
给定一个 32 位有符号整数 x
,返回其反转后的整数。反转后的整数可能会超出 32 位整数的范围,因此需要注意处理溢出情况。
示例:
-
输入:
x = 123
输出:321
-
输入:
x = -123
输出:-321
-
输入:
x = 120
输出:21
-
输入:
x = 0
输出:0
要求: 需要考虑反转后的整数是否会超出 32 位整数的范围。32 位有符号整数的范围是 ([-2^{31}, 2^{31} - 1]),即 ([-2147483648, 2147483647])。
解题思路
-
处理符号:
- 记录整数的符号(正或负),然后将整数转为正数来进行处理。
-
反转整数:
- 通过逐位提取整数的末尾数字,并将其添加到新整数的末尾,从而反转整数。
-
检查溢出:
- 在每次更新反转结果时,检查是否会发生溢出。如果结果超出了32位整数的范围,则返回0。
C 语言实现
#include <limits.h>int reverse(int x) {int reversed = 0;while (x != 0) {int digit = x % 10;// Check for overflow/underflowif (reversed > (INT_MAX - digit) / 10 || reversed < (INT_MIN - digit) / 10) {return 0;}reversed = reversed * 10 + digit;x /= 10;}return reversed;
}
Java 实现
public class Solution {public int reverse(int x) {int reversed = 0;while (x != 0) {int digit = x % 10;// Check for overflow/underflowif (reversed > Integer.MAX_VALUE / 10 || (reversed == Integer.MAX_VALUE / 10 && digit > 7)) {return 0;}if (reversed < Integer.MIN_VALUE / 10 || (reversed == Integer.MIN_VALUE / 10 && digit < -8)) {return 0;}reversed = reversed * 10 + digit;x /= 10;}return reversed;}
}
Python 实现
def reverse(x: int) -> int:reversed_x = 0sign = -1 if x < 0 else 1x *= signwhile x != 0:digit = x % 10# Check for overflow/underflowif reversed_x > (2**31 - 1 - digit) // 10:return 0reversed_x = reversed_x * 10 + digitx //= 10return reversed_x * sign
时间复杂度
时间复杂度: (O(\log_{10} n)),其中 (n) 是输入整数的绝对值。因为我们处理的每一位数字需要一次操作,整数的位数与其值的对数成正比。
空间复杂度: (O(1))。我们只使用了常数级别的额外空间来存储反转后的结果和处理过程中的变量。
这篇关于第七题:整数反转(Reverse Integer)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!