LC 7、整数反转
题目描述
这是LeetCode 上的 7、整数反转，难度为 简单
给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。
如果反转后整数超过 32 位的有符号整数的范围 [−231,231−1] ，就返回 0。
假设环境不允许存储 64 位整数（有符号或无符号）。
示例：
输入：x = 123
输出：321
本题解法参考宫水三叶的刷题日记。
不完美解法
在机试或者周赛这种需要快速AC的场景中，遇到这种文字上进行显示的题目，可以选择性的忽略限制。
对于本题，题目从文字上限制我们只能使用32位的数据结构（int）
但由于数据范围过大，使用 int会有溢出的风险，所以我们使用 long来进行计算，再返回转换为int
class Solution{
int reverse(int x){
long long ans = 0;
while(x != 0){
ans += ans * 10 + x % 10;
x /= 10;
}
return int(ans) == ans ? int(ans) : 0;
}
}
- 时间复杂度：数字x的位数，数字大概有logx位， 复杂度为O(log x)
- 空间复杂度：O(1)
完美解法
再 【不完美解法】中，我们使用了不符合文字限制的 long 数据结构，接下来我们来看看，不适用 long该如何求解。
从上述解法看，我们再循环的 ans = ans * 10 + x % 10这一步会有以处的风险，因此我们需要边遍历边判断是否以处;
- 对于正数而言，溢出意味着
ans * 10 + x % 10 > Integaer.MAX_VALUE，对等式进行变化后可得ans > (Integer.MAX_VALUE - x % 10) / 10所以我们可以进行预判 - 对于负数而言，溢出意味着
ans * 10 + x % 10 < Integer.MIN_VALUE，对等式进行变化后有ans < (Integer.MIN_VALUE - x % 10) / 10.
#define INT_MAX 2147483647
#define INT_MIN (-INT_MAX - 1)
class Solution {
public:
int reverse(int x) {
long long ans = 0;
while(x != 0){
if(x > 0 && ans > ((INT_MAX - x % 10) / 10)) return 0;
if(x < 0 && ans < ((INT_MIN - x % 10) / 10)) return 0;
ans = ans * 10 + x % 10;
x /= 10;
}
return ans;
}
};
- 时间复杂度：数字x的位数，数字大概有logx位， 复杂度为O(log x)
- 空间复杂度：O(1)
Label：模拟， 数学