题目描述
给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。
如果反转后整数超过 32 位的有符号整数的范围 [−2^31, 2^31 − 1] ，就返回 0。
假设环境不允许存储 64 位整数（有符号或无符号）。
示例
给定一个32位的整数，你需要将这个整数中的每一对数字反转。如果反转后整数超过32位，你应当在前导数字中用0填充，以得到一个有效的32位整数。假设我们的环境只能存储32位大小的有符号整数，其数值范围是 [−2^31, 2^31 − 1]。你可以假设输入的数字不会超过这个范围。
解题思路 - 数字反转法
要反转一个整数，我们可以先将整数转换为字符串，然后反转字符串，最后将反转后的字符串转换回整数。但是这种方法可能会因为整数太大而超出32位整数的范围。因此，我们需要使用数学方法来反转数字，通过逐步构建反转后的整数，并确保每一步的结果都在32位整数的范围内。
Go语言实现 - 数字反转法
func reverse(x int) int {
var result int = 0
sign := 1
if x < 0 {
sign = -1
x = -x
}
for x > 0 {
pop := x % 10
x /= 10
if result > (1<<31-1)/10 || (result == (1<<31-1)/10 && pop > 7) {
return 0 // 反转后的数超出32位整数范围
}
if result < -1<<31 {
return 0 // 反转后的数超出32位整数范围
}
result = result*10 + pop
}
return result * sign
}
算法分析
- 时间复杂度: O(log10(n))，因为我们需要遍历整数的每一位数字。
- 空间复杂度: O(1)，我们只使用了常数级别的额外空间。
这段代码首先检查输入的整数是否为负数，如果是，我们将其转换为正数并在最后应用符号。然后，我们通过循环遍历整数的每一位，将其添加到结果中。在每一步，我们都要检查结果是否超出了32位整数的范围。如果超出，我们返回0。最后，我们将结果乘以原始整数的符号，得到最终答案。
当然，除了上述的数学方法，我们还可以采用一种更直观的位操作的方法来解决这个问题。这种方法不依赖于数字的十进制表示，而是直接在二进制层面上进行操作。以下是使用位操作的Go语言实现：
Go语言实现 - 位操作法
func reverse(x int) int {
var result int = 0
for x != 0 {
pop := x % 10 // 获取最低位
x /= 10 // 移除最低位
// 检查结果是否可能溢出
if result > (1<<31-1)/10 || (result == (1<<31-1)/10 && pop > 7) {
return 0
}
if (result * 10) > (1<<31-1) || (result * 10) + pop < -(1<<31) {
return 0
}
result = result*10 + int(pop)
}
return result
}
算法分析
- 时间复杂度: O(log10(n))，因为我们需要遍历整数的每一位数字。
- 空间复杂度: O(1)，我们只使用了常数级别的额外空间。
在这个版本中，我们使用了一个循环来逐位处理输入的整数。在每次迭代中，我们取出最低位的数字（pop），然后将其加到结果（result）上。同时，我们需要检查在每一步操作后，结果是否可能溢出32位整数的范围。如果会溢出，我们返回0。如果不溢出，我们继续处理下一位数字。
这种方法的优点是它不依赖于数字的十进制表示，因此不受数字大小的限制。它直接在二进制层面上进行操作，这使得它在处理非常大的整数时更加可靠。