【LeetCode题解】7_反转整数

时间:2022-02-26 08:46:23

【LeetCode题解】7_反转整数

描述

给定一个 32 位有符号整数,将整数中的数字进行反转。

示例 1:

输入: 123
输出: 321

示例 2:

输入: -123
输出: -321

示例 3:

输入: 120
输出: 21

注意:

假设我们的环境只能存储 32 位有符号整数,其数值范围是 \([-2^{31},\,2^{31} - 1]\)。根据这个假设,如果反转后的整数溢出,则返回 0。

方法一

思路

输入的整数除以 10 得到商和余数,接着将返回的结果(初始值为 0)乘以 10 加上得到的余数作为新的结果,最后判断结果是否溢出(大于 32 位整数的最大值或者小于 32 位整数的最小值),将商作为新的整数重复上述过程,如果商为 0 则程序结束。

可以将求整数逆序数的过程想象成两个栈之间的弹出和压入操作。一个整数的每一位数存放在栈的每一格中,最高位存放在栈底,最低位存放在栈顶。将栈 A 的栈顶弹出,压入栈 B 的栈底,重复上述过程直到栈 A 为空,此时就完成了求整数逆序数的功能。实际中,弹出和压入操作并不需要借助真正的栈,可以通过求余(数学运算)实现。

其实,Python 语言的整数类型的取值范围并不存在限制,因此更不存在所谓的溢出。

Java 实现

class Solution {
public int reverse(int x) {
long result = 0;
while (x != 0) {
result = result * 10 + x % 10;
x = x / 10;
if (result < Integer.MIN_VALUE || result > Integer.MAX_VALUE) {
return 0;
}
}
return (int) result;
}
}
// Runtime: 23 ms
// Your runtime beats 77.34 % of java submissions.

复杂度分析:

  • 时间复杂度:\(O(log(n))\)
  • 空间复杂度:\(O(1)\)

类似的 Java 实现


class Solution {
public int reverse(int x) {
int ret = 0;
while (x != 0) {
int pop = x % 10;
if (ret > Integer.MAX_VALUE / 10 || (ret == Integer.MAX_VALUE / 10 && pop > 7)) {
return 0;
}
if (ret < Integer.MIN_VALUE / 10 || (ret == Integer.MIN_VALUE / 10 && pop < -8)) {
return 0;
}
ret = ret * 10 + pop;
x = x / 10;
}
return ret;
}
}
// Runtime: 21 ms
// Your runtime beats 99.21 % of java submissions.

复杂度分析同上。

Python 实现

class Solution:
def reverse(self, x):
"""
Arguments:
----------
x : int, the value range is [-2147483648, 2147483647] Return:
-------
ret : int, the reverse order number
"""
rev, a = 0, abs(x)
while a:
rev = rev * 10 + a % 10
a = a // 10
if x > 0 and rev < 2**31:
return rev
elif x < 0 and rev <= 2**31:
return -rev
else:
return 0 # Runtime: 56 ms
# Your runtime beats 85.51 % of python3 submissions.

复杂度分析同上。

方法二:转化为求字符串的倒序

Java 实现

class Solution {
public int reverse(int x) {
if (x == 0) {
return 0;
} boolean isPos = x > 0; StringBuilder sb = new StringBuilder();
char[] chars = String.valueOf(x).toCharArray();
for (int i = chars.length - 1; i >= 0; --i) {
if (chars[i] == '0' && sb.length() == 0) {
continue;
}
if (chars[i] == '-') {
continue;
}
sb.append(chars[i]);
} String xStr = null;
if (isPos) {
xStr = sb.toString();
} else {
xStr = "-" + sb.toString();
} int rev;
try {
rev = Integer.valueOf(xStr);
} catch (Exception e) {
return 0;
}
return rev;
}
}

复杂度分析:

  • 时间复杂度:\(O(log(n))\)
  • 空间复杂度:\(O(1)\)

Python 实现

class Solution:
def reverse(self, x):
"""
Arguments:
----------
x : int, the value range is [-2147483648, 2147483647] Return:
-------
ret : int, the reverse order number
"""
sign = [1, -1][x < 0]
rev = sign * int(str(abs(x))[::-1])
return rev if -2**31 <= rev <= 2**31 - 1 else 0 # Runtime: 76 ms
# Your runtime beats 42.26 % of python3 submissions.

复杂度分析同上。