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

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

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

漫漫长路，才刚刚开始…

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

参考文章:

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

1. 原题

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

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

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

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

2. 分析

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

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

分析步骤：

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

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

1. 初始化结果变量为0。
2. 第一次循环：
   • 取模：123 % 10 = 3
   • 除法：123 / 10 = 12
   • 翻转：0 * 10 + 3 = 3
3. 第二次循环：
   • 取模：12 % 10 = 2
   • 除法：12 / 10 = 1
   • 翻转：3 * 10 + 2 = 32
4. 第三次循环：
   • 取模：1 % 10 = 1
   • 除法：1 / 10 = 0
   • 翻转：32 * 10 + 1 = 321
5. 结束循环，输出翻转后的整数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;
}

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

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

这个函数通过循环取出整数的每一位数字，并将其反转拼接到结果中，最后根据原始整数的正负性返回相应的结果。函数还考虑了整数溢出的情况，如果反转后的整数超出了 32 位有符号整数的范围，则返回 0。

运行结果如下所示(仅供参考):

4. 总结

这个编程题测试了对基本算术运算的理解，以及对整数溢出问题的处理。重点应该放在熟练掌握基本的运算和逻辑控制，以及增强对边界情况处理的意识。在解决类似问题时，编写清晰且易于理解的代码是非常重要的。