LeetCode算法题:8.字符串转换整数 (atoi)

请你来实现一个 myAtoi(string s) 函数,使其能将字符串转换成一个 32 位有符号整数(类似 C/C++ 中的 atoi 函数)。

函数 myAtoi(string s) 的算法如下:

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

注意:

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

示例 1:

输入:s = "42"
输出:42
解释:加粗的字符串为已经读入的字符,插入符号是当前读取的字符。
第 1 步:"42"(当前没有读入字符,因为没有前导空格)^
第 2 步:"42"(当前没有读入字符,因为这里不存在 '-' 或者 '+')^
第 3 步:"42"(读入 "42")^
解析得到整数 42 。
由于 "42" 在范围 [-2^31, 2^31 - 1] 内,最终结果为 42 。

示例 2:

输入:s = "   -42"
输出:-42
解释:
第 1 步:"   -42"(读入前导空格,但忽视掉)^
第 2 步:"   -42"(读入 '-' 字符,所以结果应该是负数)^
第 3 步:"   -42"(读入 "42")^
解析得到整数 -42 。
由于 "-42" 在范围 [-2^31, 2^31 - 1] 内,最终结果为 -42 。

示例 3:

输入:s = "4193 with words"
输出:4193
解释:
第 1 步:"4193 with words"(当前没有读入字符,因为没有前导空格)^
第 2 步:"4193 with words"(当前没有读入字符,因为这里不存在 '-' 或者 '+')^
第 3 步:"4193 with words"(读入 "4193";由于下一个字符不是一个数字,所以读入停止)^
解析得到整数 4193 。
由于 "4193" 在范围 [-2^31, 2^31 - 1] 内,最终结果为 4193 。

提示:

  • 0 <= s.length <= 200
  • s 由英文字母(大写和小写)、数字(0-9)、' ''+''-''.' 组成

我的解题思路:
正常按逻辑处理就行,先跳过前面的空格和‘0’,然后检查是否有‘-’,没有的话则按正数处理,有的话则最后返回时添加去相反数。然后逐个遍历计算相加,直到不是数字停止。检查数值是否越界,做越界处理。最后返回值

代码:

class Solution {public int myAtoi(String s) {char[] cs = s.toCharArray();int len = s.length();int i;boolean isNegative = false;long result = 0;for ( i = 0; i < len && cs[i]==' '; i++) {// 跳过空格}if(cs[i]=='-'){// 有负号isNegative = true;i++;}while (i<len){if(cs[i] >= '0'&& cs[i]<='9'){// 是数字result = result*10 + (cs[i]-'0');//}else{// 不是数字结束break;}i++;}if(result<Integer.MIN_VALUE){result = Integer.MIN_VALUE;}if (isNegative) result = -result;return (int)result;}
}

出现错误:
在这里插入图片描述
错误原因:最后判断越界的逻辑写错了,应该是判断是否大于int的最大值,因为之前都没有进行负数处理,所以result一直是正数。

class Solution {public int myAtoi(String s) {char[] cs = s.toCharArray();int len = s.length();int i;boolean isNegative = false;long result = 0;for ( i = 0; i < len && cs[i]==' '; i++) {// 跳过空格}if(cs[i]=='-'){// 有负号isNegative = true;i++;}while (i<len){if(cs[i] >= '0'&& cs[i]<='9'){// 是数字result = result*10 + (cs[i]-'0');//}else{// 不是数字结束break;}i++;}if (isNegative) result = -result;if(result>=Integer.MAX_VALUE){result = Integer.MAX_VALUE;}if (result<=Integer.MIN_VALUE){result = Integer.MIN_VALUE;}return (int)result;}
}

再次出现错误:
在这里插入图片描述
错误原因:当字符串为空时造成数组下标越界。因此需要在一开始对空数组直接返回0处理。
再次出现错误:
在这里插入图片描述
错误原因,之前修改只是简单的对字符串判空,但是存在跳过空格之后为空字符的情况,因此,可以将判空放在跳过空字符之后。
继续出错:
在这里插入图片描述
错误原因:数值太大,造成long类型都越界且变成负数,因此上述判断是否大于int类型最大值的逻辑不太合理。

整理完上述错误逻辑之后重新梳理解题逻辑:
先将前面的空格全部跳过,然后判断字符串是否遍历完,遍历完则直接返回0,没遍历完则判断下一个字符是否是’+'或者‘-’,然后再对剩余字符遍历。停止条件有三个:

  1. 数值越界,即负数小于-231,或者正数大于231-1
  2. 遇到非数字字符。
  3. 正常遍历完了结束。

对正数和负数分别处理。最终正确题解:

class Solution {public int myAtoi(String s) {char[] cs = s.toCharArray();int len = s.length();int i;boolean isNegative = false;int result = 0;for ( i = 0; i < len && cs[i]==' '; i++) {// 跳过空格}if (i==len){// 字符串已经遍历完了return 0;}if (cs[i]=='-'||cs[i]=='+'){// 有正负号if (cs[i]=='-')isNegative = true;i++;}if(isNegative){// 负数处理逻辑while (i<len){if (cs[i]>='0'&& cs[i]<='9'){//是数字if (result<Integer.MIN_VALUE/10){// 小于最小值了,直接返回最小值result = Integer.MIN_VALUE;return result;}result = result*10 - (cs[i]-'0');if(result>0 ){// 小于最小值了,直接返回最小值result = Integer.MIN_VALUE;return result;}}else{// 不是数字,直接结束遍历break;}i++;}}else{// 正数处理逻辑while (i<len){if (cs[i]>='0'&& cs[i]<='9'){//是数字if (result>Integer.MAX_VALUE/10){result = Integer.MAX_VALUE;return result;}result = result*10 + (cs[i]-'0');if(result<0 ){// 大于最小值了,直接返回最大值result = Integer.MAX_VALUE;return result;}}else{// 不是数字,直接结束遍历break;}i++;}}// 正常返回return result;}
}

在这里插入图片描述
自己题解总结:
1.对于数值越界处理,对正数和负数分开处理,正数时计算之前判断是否大于最大值/10,计算之后判断是否为负数发生越界。负数时计算之前判断是否小于最小值/10,计算之后判断是否为正数发生越界。
2.对于前一步有两个逻辑判断的步骤,下一步必须得考虑清楚每一个逻辑,不落下没处理的逻辑。例如在这里插入图片描述
这里跳过空格有两个逻辑判断都可能结束遍历,则下一步得区分是哪一个条件导致的遍历结束。

官方题解:

class Solution {public int myAtoi(String str) {Automaton automaton = new Automaton();int length = str.length();for (int i = 0; i < length; ++i) {automaton.get(str.charAt(i));}return (int) (automaton.sign * automaton.ans);}
}class Automaton {public int sign = 1;public long ans = 0;private String state = "start";private Map<String, String[]> table = new HashMap<String, String[]>() {{put("start", new String[]{"start", "signed", "in_number", "end"});put("signed", new String[]{"end", "end", "in_number", "end"});put("in_number", new String[]{"end", "end", "in_number", "end"});put("end", new String[]{"end", "end", "end", "end"});}};public void get(char c) {state = table.get(state)[get_col(c)];if ("in_number".equals(state)) {ans = ans * 10 + c - '0';ans = sign == 1 ? Math.min(ans, (long) Integer.MAX_VALUE) : Math.min(ans, -(long) Integer.MIN_VALUE);} else if ("signed".equals(state)) {sign = c == '+' ? 1 : -1;}}private int get_col(char c) {if (c == ' ') {return 0;}if (c == '+' || c == '-') {return 1;}if (Character.isDigit(c)) {return 2;}return 3;}
}作者:力扣官方题解
链接:https://leetcode.cn/problems/string-to-integer-atoi/solutions/183164/zi-fu-chuan-zhuan-huan-zheng-shu-atoi-by-leetcode-/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

思路

字符串处理的题目往往涉及复杂的流程以及条件情况,如果直接上手写程序,一不小心就会写出极其臃肿的代码。

因此,为了有条理地分析每个输入字符的处理方法,我们可以使用自动机这个概念:

我们的程序在每个时刻有一个状态 s,每次从序列中输入一个字符 c,并根据字符 c 转移到下一个状态 s’。这样,我们只需要建立一个覆盖所有情况的从 s 与 c 映射到 s’ 的表格即可解决题目中的问题。
作者:力扣官方题解
链接:https://leetcode.cn/problems/string-to-integer-atoi/solutions/183164/zi-fu-chuan-zhuan-huan-zheng-shu-atoi-by-leetcode-/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
在这里插入图片描述
说实话,一开始拿到这一题想到过可能可以用这方面去写,但是关于原理完全忘了,也就不敢去写,结果自己一个一个逻辑判断却总是存在漏洞,官方题解太优雅了,对于大多数人应该也都是看一看。这一题对于我更多的启发是在于如何判断int数据溢出。
官方使用了,其中ans为long类型,这就不会造成ans在计算时溢出,然后去区分正负数的情况,正数与int的最大值比较取小,负数与int的最小值的相反数比较取小

ans = sign == 1 ? Math.min(ans, (long) Integer.MAX_VALUE) : Math.min(ans, -(long) Integer.MIN_VALUE);

如果限制了为int类型,则可以使用我上述的方式计算前判断是否将会溢出,以及计算后的值是否溢出。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://xiahunao.cn/news/3016151.html

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

Java:内存模型

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 目录 一、Java内存模型出现的背景 二、什么是Java内存模型 三、Java内存模型的底层实现 总结 提示&#xff1a;以下是本篇文章正文内容&#xff0c;下面案例可供参考 一…

linux系统 虚拟机的安装详细步骤

window&#xff1a; (1) 个人&#xff1a;win7 win10 win11 winxp (2)服务器&#xff1a;windows server2003 2008 2013 linux&#xff1a; (1)centos7 5 6 8 (2)redhat (3)ubuntu (4)kali 什么是linux: 主要是基于命令来完成各种操作&#xff0c;类似于DO…

【黑客不回去做的三件事情】

作为黑客不会去做的三件事 黑客在认知上和普通人有什么区别&#xff1f;什么行为是自己觉得很正常&#xff0c; 但是大部分黑客并不会这么做的。今天来聊聊作为黑客&#xff0c;有哪些日常生活中不会去做的事&#xff0c; 第一&#xff0c;黑客不会用同一个密码&#xff0c;并…

开源模型应用落地-CodeQwen模型小试-探索更多使用场景(三)

一、前言 代码专家模型是基于人工智能的先进技术&#xff0c;它能够自动分析和理解大量的代码库&#xff0c;并从中学习常见的编码模式和最佳实践。这种模型可以提供准确而高效的代码建议&#xff0c;帮助开发人员在编写代码时避免常见的错误和陷阱。 通过学习代码专家模型&…

vivado Zynq UltraScale+ MPSoC 比特流设置

Zynq UltraScale MPSoC 比特流设置 下表所示 Zynq UltraScale MPSoC 器件的器件配置设置可搭配 set_property <Setting> <Value> [current_design] Vivado 工具 Tcl 命令一起使用。

KDTree空间搜索算法学习

目录 KDTree&#xff08;K-Dimensional Tree&#xff09;原理步骤空间索引建立例子[^1]回溯搜索例子[^2] 相关包案例[^3]数据KDTree 识别轨道衔接出行轨道衔接单车骑行范围分析结果保存 KDTree&#xff08;K-Dimensional Tree&#xff09;原理 将需要匹配的 K 维空间点建立 K …

java10基础(this super关键字 重写 final关键字 多态 抽象类)

目录 一. this和super关键字 1. this关键字 2. super关键字 二. 重写 三. final关键字 四. 多态 五. 抽象类 1. 抽象方法 2. 抽象类 3. 面向抽象设计 一. this和super关键字 1. this关键字 this 当前对象的引用 this.属性 this.方法名() this() -- 调用构造函数 …

VALSE 2024 Workshop报告分享┆Open-Sora Plan视频生成开源计划——进展与不足

2024年视觉与学习青年学者研讨会&#xff08;VALSE 2024&#xff09;于5月5日到7日在重庆悦来国际会议中心举行。本公众号将全方位地对会议的热点进行报道&#xff0c;方便广大读者跟踪和了解人工智能的前沿理论和技术。欢迎广大读者对文章进行关注、阅读和转发。文章是对报告人…

页面嵌套,界面套娃,除了用iframe,还有其他方式吗?

UIOTOS可以了解下&#xff0c;uiotos.net&#xff0c;通过连线来代替脚本逻辑开发&#xff0c;复杂的交互界面&#xff0c;通过页面嵌套轻松解决&#xff0c;是个很新颖的思路&#xff0c;前端零代码&#xff01; 蓝图连线尤其是独创的页面嵌套和属性继承技术&#xff0c;好家…

为什么现在散户在加密市场赚不到钱了?

为什么总有人说这个周期已经结束了&#xff1f;为什么每个人都感到痛苦&#xff1f;我们可以将所有问题归结为&#xff1a;在当前的市场结构下&#xff0c;散户再也赚不到真正的钱了。 关于回归本源、摆脱当前周期的一些杂谈 为什么本轮行情中没有散户的身影&#xff0c;答案…

2024智能电网与能源系统国际学术会议(ICSGES2024)

2024智能电网与能源系统国际学术会议&#xff08;ICSGES2024) 会议简介 我们诚挚邀请您参加将在南京隆重举行的2024年智能电网与能源系统国际学术会议&#xff08;ICSGES2024&#xff09;。南京&#xff0c;一座历史与现代交织的城市&#xff0c;将为这场盛会提供独特的学术…

Java IO类之FilterOutputStream的研究与应用

哈喽&#xff0c;各位小伙伴们&#xff0c;你们好呀&#xff0c;我是喵手。运营社区&#xff1a;C站/掘金/腾讯云&#xff1b;欢迎大家常来逛逛 今天我要给大家分享一些自己日常学习到的一些知识点&#xff0c;并以文字的形式跟大家一起交流&#xff0c;互相学习&#xff0c;一…

Ansible自动化工具模块调用与playbook编写

目录 一、Ansible工作机制与特点 &#xff08;一&#xff09;Ansible工作机制 1. 初始化与配置 2. 编写Playbook 3. 调用模块 4. 加密敏感数据 5. 执行Playbook 6. 收集执行结果 7. 错误处理与回滚 8. 反馈与报告 &#xff08;二&#xff09;Ansible 的主要特点包括…

文献速递:深度学习医学影像心脏疾病检测与诊断--CT中的深度学习用于自动钙评分:使用多个心脏CT和胸部CT协议的验证

Title 题目 Deep Learning for Automatic Calcium Scoring in CT: Validation Using Multiple Cardiac CT and Chest CT Protocols CT中的深度学习用于自动钙评分&#xff1a;使用多个心脏CT和胸部CT协议的验证 Background 背景 Although several deep learning (DL) calc…

智能实训-wheeltec小车-抓取(源代码)

语言 :C 源代码&#xff1a; #include <ros/ros.h> #include <image_transport/image_transport.h> #include <cv_bridge/cv_bridge.h> #include <sensor_msgs/image_encodings.h> #include <sensor_msgs/JointState.h> #include <geometry…

yolo-world:”目标检测届大模型“

AI应用开发相关目录 本专栏包括AI应用开发相关内容分享&#xff0c;包括不限于AI算法部署实施细节、AI应用后端分析服务相关概念及开发技巧、AI应用后端应用服务相关概念及开发技巧、AI应用前端实现路径及开发技巧 适用于具备一定算法及Python使用基础的人群 AI应用开发流程概…

全新拼团模式 你一定没见过 白拿产品还有收益!

在七星拼团模式中&#xff0c;奖励制度是其核心吸引力之一。今天&#xff0c;我们将深入探讨这一模式的三种奖励&#xff1a;直推奖、滑落奖和出局奖&#xff0c;以及它们背后的互助机制。 奖励规则概述 首先&#xff0c;让我们了解一下奖励的具体规则。假设商品售价为499元&a…

Python面向对象编程思想的深入学习

魔术方法的使用 案例体验 class Student:def __init__(self, name, age):self.name nameself.age age# __str__魔术方法, 如果不去写这个方法&#xff0c;那么print输出的则是信息存储的内存地址。def __str__(self):return fStudent类对象&#xff0c;name:{self.name}, ag…

【Java 刷题记录】前缀和

前缀和 25. 一维前缀和 示例1&#xff1a; 输入&#xff1a; 3 2 1 2 4 1 2 2 3输出&#xff1a; 3 6import java.util.Scanner;// 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main {public static void main(String[] args) {Scanner in new Scanner(S…

基于FPGA的数字锁控制电路VHDL代码Quartus仿真

名称&#xff1a;基于FPGA的数字锁控制电路VHDL代码Quartus仿真&#xff08;文末获取) 软件&#xff1a;Quartus 语言&#xff1a;VHDL 代码功能&#xff1a; 任务及要求 硬件描述语言VHDL是一种用形式化方法描述数字电路和系统的语言。利用这种语 ,数字电路系统的设计可…