LeetCode第七题：整数反转

admin
学习
2023-09-14
196热度
0评论

题目来源：LeetCode第七题

1.题目描述

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

如果反转后整数超过 32 位的有符号整数的范围 [−2³¹, 2³¹− 1] ，就返回 0。

假设环境不允许存储 64 位整数（有符号或无符号）。

示例 1：

输入：x = 123

输出：321

提示：

-2³¹ <= x <= 2³¹ - 1

2.解题思路

解法一：字符串反转法

描述：判断整数是不是负数，是就取其绝对值，将整数转化为字符串，然后反转字符串，将反转过的字符串转回整数，原来是负数就加上负号，检查反转后的整数是否溢出。
时间复杂度：O(n)。其中n是数字的位数。因为我们遍历了整数的每一位。
空间复杂度：O(n)。我们使用了额外的空间来存储转换后的字符串。
参考代码：

java版：

class Solution {
    public int reverse(int x) {
        // 判断整数是不是负数
        boolean isNegative = false;
        // 如果是负数，设置为ture，并且取绝对值
        if (x < 0) {
            isNegative = true;
            x = -x;
        }
        // 将整数转化为字符串
        String s = Integer.toString(x);
        // 用StringBuilder来反转字符串
        String reversed = new StringBuilder(s).reverse().toString();
        int result;
        // 用try catch来捕获字符串是否可以正确转化为一个有效整数
        // 可以捕获无效格式如123a，12.34 空字符串，超出范围，数字中存在空白如“12 34”，前后空白允许如“ 123 ”
        // 这里主要是判断是否超出范围，超过就返回0
        try {
            result = Integer.parseInt(reversed);
        } catch (NumberFormatException e) {
            return 0;
        }

        // 如果是负数，加上负号
        if (isNegative) {
            result = -result;
        }
        return result;
    }
}

C++版：

class Solution
{
public:
	int reverse(int x)
	{
		// 将整数转为字符串
		string s = to_string(x);
		// 利用C++标准库来反转字符串
		std::reverse(s.begin(), s.end());
		// 判断是否是负数，如果是，我们需要将反转后的字符串中的'-'字符移到字符串的开头
		if(x<0)
		{
			s.erase(s.find('-'));
			s = '-' + s;
		}
		// 使用long long是为了避免中间溢出,因为提示是int的范围
		//stoll是将字符串转为longlong 类似的还有stol stoi
		long long result = stoll(s);
		// 检查结果是否在整数范围内
		if(result>INT_MAX || result<INT_MIN)
		{
			return 0;
		}
		//返回int类型的整数，用强制类型转化static_cast
		return static_cast<int>(result);
	}
};

C版：

int reverse(int x) {
    char str[12]; // 用于存放整数x的字符串形式。考虑到最大的32位整数是10位，再加上可能的负号和末尾的'\0'，总共需要12个字符
    snprintf(str, sizeof(str), "%d", x);// 将整数x转为字符串形式
    

    // 检查是否是负数
    bool isNegative = false;
    if (str[0] == '-') {
        isNegative = true;
    }

    // 开始反转字符串
    int start = isNegative ? 1 : 0; // 如果是负数，从索引1开始反转，否则从索引0开始
    int end = strlen(str) - 1;
    while (start < end) {
        char temp = str[start];
        str[start] = str[end];
        str[end] = temp;
        start++;
        end--;

解法二：数学方法

描述：数学方法的核心思想是利用取余 % 和除法 / 运算来逐位取出整数的每一位，并累加到新的整数中，实现反转效果。
时间复杂度：O(n)。n是整数x的位数。
空间复杂度：O(1)。只是定义了几个变量。
参考代码：

java版：

class Solution {
    public int reverse(int x) {
        int result = 0;

        while (x != 0) {

            if (result > Integer.MAX_VALUE / 10 || result < Integer.MIN_VALUE / 10) {
                return 0;
            }
            int digit = x % 10;
            x /= 10;
            result = result * 10 + digit;
        }
        return result;
    }
}

C++版：

class Solution {
public:
    int reverse(int x) {
        int rev = 0;
        while (x != 0) {
            if (rev < INT_MIN / 10 || rev > INT_MAX / 10) {
                return 0;
            }
            int digit = x % 10;
            x /= 10;
            rev = rev * 10 + digit;
        }
        return rev;
    }
};

C版：

int reverse(int x) {
    int rev = 0;
    while (x != 0) {
        if (rev < INT_MIN / 10 || rev > INT_MAX / 10) {
            return 0;
        }
        int digit = x % 10;
        x /= 10;
        rev = rev * 10 + digit;
    }
    return rev;
}