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

简介: 介绍两道力扣题的解题思路,两道题都包含了判断整型是否溢出的问题,两道题都很有意思:看着很简单,实际上并不容易通过,当然,也可能是我自己能力不到位,要敢于正视自己的问题,勤于总结,不断进步。

整数反转

原题链接: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) 的算法如下:

  1. 读入字符串并丢弃无用的前导空格
  2. 检查下一个字符(假设还未到字符末尾)为正还是负号,读取该字符(如果有)。 确定最终结果是负数还是正数。 如果两者都不存在,则假定结果为正。
  3. 读入下一个字符,直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。
  4. 将前面步骤读入的这些数字转换为整数(即,"123" -> 123, "0032" -> 32)。如果没有读入数字,则整数为 0 。必要时更改符号(从步骤 2 开始)。
  5. 如果整数数超过 32 位有符号整数范围 [−231,  231 − 1] ,需要截断这个整数,使其保持在这个范围内。具体来说,小于 −231 的整数应该被固定为 −231 ,大于 231 − 1 的整数应该被固定为 231 − 1 。
  6. 返回整数作为最终结果。

注意:

  • 本题中的空白字符只包括空格字符 ' ' 。
  • 除前导空格或数字后的其余字符串外,请勿忽略 任何其他字符。
本人战绩
这道题有意思的地方就是限制条件非常多,看起来容易,却要提交很多遍才能通过
image.png

解题思路

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

第一个部分:吃掉空格

使用循环判断当前字符是否为空格,是则向后移动。
当判断不是空格是,有四种情况:

  1. 负号
  2. 正好
  3. 数字
  4. 其他字符,如a
二三部分:判断正负、扔掉其他字符

对于这四种情况,可以分开处理:

  1. 负号,指针向后移动,把后面的数字抠出来,碰到其它字符就跳出循环
  2. 正号,指针向后移动,把后面的数字抠出来,碰到其它字符就跳出循环
  3. 数字,把后面的数字抠出来,碰到其它字符就跳出循环
  4. 其他字符,直接跳出

通过对比可以发现,数字其他字符这两种情况可以合并:使用一个循环,判断当前字符是否为数字,如果不是,则跳出循环;如果第一个字符就不是数字,那就是其他字符这种情况,结果就是直接跳出
也就是说,第四种情况是的三种情况的特殊情况。到了这一步,剩下的就很简单了。
对于前三种情况,很明显,有重复的步骤:把后面的数字抠出来,碰到其它字符就跳出循环,我们可以把这一部分单独封装,根据情况,分别调用。

  • 当判断为负号时,吃掉负号-,将后面的内容传入封装的函数。
  • 当判断为正数时,吃掉正好+,将后面的内容传入封装的函数。
  • 当这两种情况都不是时,直接将后面的内容传入封装的函数。

对于封装内容,无非处理正数和处理负数这两种情况,我们可以设置参数为字符串和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
image.png

结束语,共勉

我就不讲大道理,不放名言警句了,看图吧
image.png

目录
相关文章
|
2月前
|
存储
LeetCode整数反转
解决LeetCode上的整数反转问题的几种方法,包括错误的方法和优化后的解决方案,以及如何避免反转后的整数超出32位有符号整数范围的问题。
35 1
|
2月前
|
JavaScript
力扣3333.找到初始输入字符串Ⅱ
【10月更文挑战第9天】力扣3333.找到初始输入字符串Ⅱ
34 1
|
2月前
|
C++
Leetcode第43题(字符串相乘)
本篇介绍了一种用C++实现的字符串表示的非负整数相乘的方法,通过逆向编号字符串,将乘法运算转化为二维数组的累加过程,最后处理进位并转换为字符串结果,解决了两个大数相乘的问题。
25 9
|
2月前
|
存储 C++
Leetcode第十二题(整数转罗马数字)
LeetCode第12题“整数转罗马数字”的解题方法,包括罗马数字的基本规则和特殊规则,以及如何使用C++实现整数到罗马数字的转换。
16 0
|
2月前
|
C++
Leetcode第十三题(罗马数字转整数)
这篇文章介绍了LeetCode第13题“罗马数字转整数”的解题方法,通过一个C++的类`Solution`中的`romanToInt`函数来实现,该函数使用哈希表和遍历字符串的方法,根据罗马数字的规则将输入的罗马数字字符串转换为对应的整数值。
52 0
|
2月前
|
算法 C++
Leetcode第八题(字符串转换整数(atoi))
这篇文章介绍了LeetCode上第8题“字符串转换整数(atoi)”的解题思路和C++的实现方法,包括处理前导空格、正负号、连续数字字符以及整数溢出的情况。
19 0
|
3月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
4月前
|
Python
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
58 6
|
4月前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
120 2
|
1月前
|
机器学习/深度学习 人工智能 自然语言处理
280页PDF,全方位评估OpenAI o1,Leetcode刷题准确率竟这么高
【10月更文挑战第24天】近年来,OpenAI的o1模型在大型语言模型(LLMs)中脱颖而出,展现出卓越的推理能力和知识整合能力。基于Transformer架构,o1模型采用了链式思维和强化学习等先进技术,显著提升了其在编程竞赛、医学影像报告生成、数学问题解决、自然语言推理和芯片设计等领域的表现。本文将全面评估o1模型的性能及其对AI研究和应用的潜在影响。
28 1