代码训练LeetCode(14)整数反转

代码训练(14)LeetCode之整数反转

Author: Once Day Date: 2024年4月9日

漫漫长路，才刚刚开始…

全系列文章可参考专栏: 十年代码训练_Once-Day的博客-CSDN博客

参考文章:

190. 颠倒二进制位 - 力扣（LeetCode）
7. 整数反转 - 力扣（LeetCode）
力扣 (LeetCode) 全球极客挚爱的技术成长平台

文章目录

- - 代码训练(14)LeetCode之整数反转
  - - 1. 原题
    - 2. 分析
    - 3. 代码实现
    - 4. 总结

1. 原题

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

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

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

这个任务是一个数字处理问题，我们要把一个32位有符号整数中的数字翻转过来，并且要注意处理溢出的情况。如果翻转后的整数超过了给定的32位有符号整数范围，就返回0。

2. 分析

题目要求我们实现一个函数，输入一个32位有符号整数x，输出一个整数，它是x的数字部分翻转后的结果。如果翻转后的结果超出了[-2^31, 2^31 - 1]的范围，就返回0。

翻转一个整数的数字可以通过取模和除法操作来完成。我们可以循环地从x中提取每一位数字，然后将它添加到结果变量中，同时考虑到符号和溢出的问题。

分析步骤：

初始化一个变量来存储翻转后的整数。
处理整数x的符号，并在处理过程中使用绝对值。
使用循环结构，每次循环：
- 通过取模操作获取x的最低位数字。
- 通过除法操作将x的最低位移除。
- 将结果变量乘以10，并加上提取的数字，实现翻转。
- 在每次操作后检查是否有溢出情况发生。
根据原始整数的符号，返回翻转后的结果，如果有溢出则返回0。

假设输入整数为123，我们希望得到翻转后的整数321。

初始化结果变量为0。
第一次循环：
- 取模：123 % 10 = 3
- 除法：123 / 10 = 12
- 翻转：0 * 10 + 3 = 3
第二次循环：
- 取模：12 % 10 = 2
- 除法：12 / 10 = 1
- 翻转：3 * 10 + 2 = 32
第三次循环：
- 取模：1 % 10 = 1
- 除法：1 / 10 = 0
- 翻转：32 * 10 + 1 = 321
结束循环，输出翻转后的整数321。

主要操作是循环中的基本算术运算，这里除法可以进行一些优化，比如同时返回商和除数，不过这个属于指令优化范畴。

此外，还可以优化一下边界值判断和循环过程，比如对于32位整数，范围是[-2147483648, 2147483647]，可以排除0值和-2147483648这两种情况，然后取绝对值进行反转操作。

同时要注意到，如果数字不超过9位，是不需要进行过多判断的，因为不管怎么反转，9位数是不会超过32位有符号整数的表示范围。只需要对10位数进行判断，如果低9位数反转后超过了214748364大小，这个10位数必然超过了范围，直接返回零值即可。

3. 代码实现

int reverse(int x){
    int i, temp;
    int abs_x, result;

    if (x == 0x80000000) {
        return 0;
    }

    if (x == 0) {
        return 0;
    }

    abs_x = x < 0 ? -x : x;
    result = 0;
    for (i = 0; i < 9; i++) {
        temp = abs_x % 10;
        abs_x = abs_x / 10;
        result = result * 10 + temp;
        if (abs_x == 0) {
            goto end;
        }
    }

    if (result > 214748364) {
        return 0;
    }
    result = result * 10 + abs_x;

end:
    return x < 0 ? -result:result;
}

这个函数的作用是反转一个有符号整数，并返回反转后的结果：

首先判断输入的整数 x 是否为 0x80000000（即 -2^31，INT_MIN）或 0，如果是则直接返回 0，因为这两个数反转后会溢出。
将 x 的绝对值赋给变量 abs_x，用于后续计算。
初始化结果变量 result 为 0。
使用循环进行反转操作，最多循环 9 次：
- 取出 abs_x 的最低位数字，即 abs_x % 10，赋给变量 temp。
- 将 abs_x 除以 10，去掉最低位数字。
- 将 result 乘以 10，再加上 temp，即将当前位数字添加到结果的末尾。
- 如果 abs_x 已经为 0，说明所有位都处理完毕，跳转到 end 标签处。
在循环结束后，判断 result 是否大于 214748364（即 INT_MAX / 10），如果是，说明反转后的数字溢出了，返回 0。
如果 result 未溢出，将 abs_x 的最后一位数字添加到 result 的末尾。
在 end 标签处，根据原始输入 x 的正负性，决定返回 result 的正负形式。