整数反转
原题链接：https://leetcode.cn/problems/reverse-integer/
题目描述
给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。
如果反转后整数超过 32 位的有符号整数的范围 [−231, 231 − 1] ，就返回 0。
假设环境不允许存储 64 位整数（有符号或无符号）。
示例 1：
输入：x = 123 输出：321
示例 2：
输入：x = -123 输出：-321
示例 3：
输入：x = 120 输出：21
示例 4：
输入：x = 0 输出：0
提示：
- -231 <= x <= 231 - 1
这道题看着比较容易，做起来还是比较费劲，力扣给的难度是中等。
解题思路
注意题干：假设环境不允许存储 64 位整数（有符号或无符号）。
这句话就是本题的难点。
交换过程
这一过程比较简单
这一过程不难理解，上图只绘制这一过程的前三步。
就是已有的TMP乘10加上original取余得到的值作为新的TMP。
如果真这么简单就算不上中等题了。
判断溢出
这一步比较麻烦，但想开了之后也不难
先讨论负数这种情况
int类型的下线是-231=2147483648，这个值也在limits.h中，宏名称为INT_MIN，由于题目不允许使用64位整数，因此不能用乘法判断是否溢出，因为如果溢出，此时的表达式结果已经超过int类型的范围，已经不是32位整数。
那就只能用除法判断临界情况，在TMP最后一次运算之前，判断与临界情况的关系，也就是处理到倒数第二位的时候，此时，如果TMP<(INT_MIN/10)，因为此时是负数，可能不容易理解，我们可以运用假设的方法求解：
INT_MIN/10=-214748364，如果TMP小于该值，也就是-214748365，无论TMP乘十之后加上任何数，都比INT_MIN要小，都已经超过了int类型的数据范围，此时，返回0。- 如果处理到倒数第二位时TMP等于
INT_MIN/10，进行最后一次运算，TMP*10=-2147483640，再加上original剩余的最后一位数，应不低于INT_MIN，也就是-2147483648，也就是TMP*10+original>=-2147483648，由于此时TMP等于INT_MIN/10，所以不等式变为original>=-8。 - 如果TMP大于
INT_MIN/10，乘10之后，无论original等于几，都不会比INT_MIN还要小。
原整数为正数时
最难理解的情况：原整数为负数时已经讨论完毕，正数更符合日常习惯，相对容易，在这里，只讨论，TMP等于INT_MAX/10-1这种情况。
此时，需要满足TMP*10+original<INT_MAX-1，与负数那种情况的运算方法一样，求出original<7
敲代码
class Solution { public: int reverse(int x) { int rev = 0; while (x != 0) { int pop = x % 10; x /= 10; if (rev > INT_MAX / 10 || (rev == INT_MAX / 10 && pop > 7)) return 0; if (rev < INT_MIN / 10 || (rev == INT_MIN / 10 && pop < -8)) return 0; rev = rev * 10 + pop; } return rev; } };
运行结果
1032 / 1032 个通过测试用例
状态：通过
执行用时: 8 ms
内存消耗: 5.8 MB
在这个代码中，可以看到，两个if都被执行，而实际上x要么正数、要么负数，可以加条件分类，分别执行
加if优化
class Solution { public: int reverse(int x) { int rev = 0; while (x != 0) { int pop = x % 10; x /= 10; if (rev > 0) { if (rev > INT_MAX / 10 || (rev == INT_MAX / 10 && pop > 7)) return 0; } else { if (rev < INT_MIN / 10 || (rev == INT_MIN / 10 && pop < -8)) return 0; } rev = rev * 10 + pop; } return rev; } };
运行结果
1032 / 1032 个通过测试用例
状态：通过
执行用时: 4 ms
内存消耗: 5.8 MB
字符串转换整数 (atoi)
原题链接：https://leetcode.cn/problems/string-to-integer-atoi/
这道题也用到了上一道题中的方法：判断整形溢出，但由于这道题有特别多的限制条件，使得这道题比上一道更难
题目描述
请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数（类似 C/C++ 中的 atoi 函数）。
函数 myAtoi(string s) 的算法如下：
- 读入字符串并丢弃无用的前导空格
- 检查下一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如果有）。 确定最终结果是负数还是正数。 如果两者都不存在，则假定结果为正。
- 读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。
- 将前面步骤读入的这些数字转换为整数（即，“123” -> 123， “0032” -> 32）。如果没有读入数字，则整数为 0 。必要时更改符号（从步骤 2 开始）。
- 如果整数数超过 32 位有符号整数范围 [−231, 231 − 1] ，需要截断这个整数，使其保持在这个范围内。具体来说，小于 −231 的整数应该被固定为 −231 ，大于 231 − 1 的整数应该被固定为 231 − 1 。
- 返回整数作为最终结果。
注意：
- 本题中的空白字符只包括空格字符 ’ ’ 。
- 除前导空格或数字后的其余字符串外，请勿忽略 任何其他字符。
本人战绩
这道题有意思的地方就是限制条件非常多，看起来容易，却要提交很多遍才能通过
解题思路
一共分为以下几个部分：吃掉空格、判断正负、扔掉其他字符。
第一个部分：吃掉空格
使用循环判断当前字符是否为空格，是则向后移动。
当判断不是空格是，有四种情况：
- 负号
- 正好
- 数字
- 其他字符，如
a
二三部分：判断正负、扔掉其他字符
对于这四种情况，可以分开处理：
- 负号，指针向后移动，把后面的数字抠出来，碰到其它字符就跳出循环
- 正号，指针向后移动，把后面的数字抠出来，碰到其它字符就跳出循环
- 数字，把后面的数字抠出来，碰到其它字符就跳出循环
- 其他字符，直接跳出
通过对比可以发现，数字和其他字符这两种情况可以合并：使用一个循环，判断当前字符是否为数字，如果不是，则跳出循环；如果第一个字符就不是数字，那就是其他字符这种情况，结果就是直接跳出
也就是说，第四种情况是的三种情况的特殊情况。到了这一步，剩下的就很简单了。
对于前三种情况，很明显，有重复的步骤：把后面的数字抠出来，碰到其它字符就跳出循环，我们可以把这一部分单独封装，根据情况，分别调用。
- 当判断为负号时，吃掉负号
-，将后面的内容传入封装的函数。 - 当判断为正数时，吃掉正好
+，将后面的内容传入封装的函数。 - 当这两种情况都不是时，直接将后面的内容传入封装的函数。
对于封装内容，无非处理正数和处理负数这两种情况，我们可以设置参数为字符串和bool类型，bool用于标注正负，函数内部根据bool值分别调用具体的函数实现。
敲代码
class Solution { public: int rt(const string& s, bool zf) { int i(0), result(0), pop(0); if (zf == 0) { while (i < s.size() && s[i] <= '9' && s[i] >= '0') { pop = 48 - s[i++]; if (result < INT_MIN / 10 || (result == INT_MIN / 10 && pop < -8)) return INT_MIN; result = result * 10 + pop; } } else { while (i < s.size() && s[i] <= '9' && s[i] >= '0') { pop = s[i++] - 48; if (result > INT_MAX / 10 || (result == INT_MAX / 10 && pop > 7)) return INT_MAX; result = result * 10 + pop; } } return result; } int myAtoi(string s) { int i(0), result(0), pop(0); while (s[i] == ' ') { i++; } if (s[i] == '-') { i++; return rt(s.substr(i), 0); } if (s[i] == '+') { i++; return rt(s.substr(i), 1); } return rt(s.substr(i), 1); } };
运行效果
执行用时：0 ms, 在所有 C++ 提交中击败了100.00%的用户
内存消耗：6.8 MB, 在所有 C++ 提交中击败了67.07%的用户
通过测试用例：1084 / 1084
结束语，共勉
我就不讲大道理，不放名言警句了，看图吧
