无锡 做网站,动漫制作专业专升本考什么,wordpress 白色主题,哈尔滨个人优化排名8. 字符串转换整数 (atoi)
题目#xff1a;8. 字符串转换整数 (atoi)
请你来实现一个 myAtoi(string s) 函数#xff0c;使其能将字符串转换成一个 32 位有符号整数#xff08;类似 C/C 中的 atoi 函数#xff09;。
函数 myAtoi(string s) 的算法如下#xff1a;
读入…8. 字符串转换整数 (atoi)
题目8. 字符串转换整数 (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 。返回整数作为最终结果。
注意
本题中的空白字符只包括空格字符 。除前导空格或数字后的其余字符串外请勿忽略 任何其他字符。
示例 1
输入s 42
输出42
解释加粗的字符串为已经读入的字符插入符号是当前读取的字符。
第 1 步42当前没有读入字符因为没有前导空格^
第 2 步42当前没有读入字符因为这里不存在 - 或者 ^
第 3 步42读入 42^
解析得到整数 42 。
由于 42 在范围 [-231, 231 - 1] 内最终结果为 42 。
示例 2
输入s -42
输出-42
解释
第 1 步 -42读入前导空格但忽视掉^
第 2 步 -42读入 - 字符所以结果应该是负数^
第 3 步 -42读入 42^
解析得到整数 -42 。
由于 -42 在范围 [-231, 231 - 1] 内最终结果为 -42 。示例 3
输入s 4193 with words
输出4193
解释
第 1 步4193 with words当前没有读入字符因为没有前导空格^
第 2 步4193 with words当前没有读入字符因为这里不存在 - 或者 ^
第 3 步4193 with words读入 4193由于下一个字符不是一个数字所以读入停止^
解析得到整数 4193 。
由于 4193 在范围 [-231, 231 - 1] 内最终结果为 4193 。提示
0 s.length 200s 由英文字母大写和小写、数字0-9、 、、- 和 . 组成
方法一 直接写
1.思路
一般情况下我们判断转换数字“-123”是符号和数字一起判断的。但是这个题目的示例中会出现“-1”这种情况。所以需要将符合和数字分开判定假如已获取符号则判断后续是否为数字即可。
2.代码
class Solution {public int myAtoi(String s) {int x 0;int p 1;int i 0;char[] str s.toCharArray();while (i str.length str[i] ) i;if (i str.length) return 0;if (str[i] -) {p -1;i;} else if (str[i] ) {p 1;i;}while (i str.length Character.isDigit(str[i])) {int r str[i] - 0;if (p 1 (Integer.MAX_VALUE - r) / 10 x) return Integer.MAX_VALUE;if (p -1 (Integer.MIN_VALUE r) / 10 -x) return Integer.MIN_VALUE;x x * 10 r;i;}return x * p;}
}
方法二自动机
1.思路
自动机:
我们的程序在每个时刻有一个状态 s每次从序列中输入一个字符 c并根据字符 c 转移到下一个状态 s。这样我们只需要建立一个覆盖所有情况的从 s 与 c 映射到 s 的表格即可解决题目中的问题。 也可以用下面的表格来表示这个自动机 自动机也需要记录当前已经输入的数字只要在 s 为 in_number 时更新我们输入的数字即可最终得到输入的数字。
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 MapString, String[] table new HashMapString, 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;}
}
时间复杂度O(n)
空间复杂度O(1)
