LC 7、整数反转

题目描述

这是LeetCode 上的 7、整数反转，难度为 简单

给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。

如果反转后整数超过 32 位的有符号整数的范围 [−2^31,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：模拟， 数学