力扣7-整数反转&力扣8-字符串转换整数 (atoi)

原创

WuShF

发布于 2023-02-19 22:28:31

3550

发布于 2023-02-19 22:28:31

文章被收录于专栏：笔记分享

整数反转

原题链接：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
image.png

在这个代码中，可以看到，两个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
image.png

字符串转换整数 (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 。
返回整数作为最终结果。

注意：

本题中的空白字符只包括空格字符 ' ' 。
除前导空格或数字后的其余字符串外，请勿忽略任何其他字符。本人战绩

这道题有意思的地方就是限制条件非常多，看起来容易，却要提交很多遍才能通过
image.png

解题思路

一共分为以下几个部分：吃掉空格、判断正负、扔掉其他字符。

第一个部分：吃掉空格

使用循环判断当前字符是否为空格，是则向后移动。

当判断不是空格是，有四种情况：

负号
正好
数字
其他字符，如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);
    }
};