请你来实现一个myAtoi(string s)函数，使其能将字符串转换成一个 32 位有符号整数（类似 C/C++ 中的atoi函数）
https://leetcode-cn.com/problems/string-to-integer-atoi/
示例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 。
示例4：
输入：s = "words and 987"
输出：0
解释：
第 1 步："words and 987"（当前没有读入字符，因为没有前导空格）
^
第 2 步："words and 987"（当前没有读入字符，因为这里不存在 '-' 或者 '+'）
^
第 3 步："words and 987"（由于当前字符 'w' 不是一个数字，所以读入停止）
^
解析得到整数 0 ，因为没有读入任何数字。
由于 0 在范围 [-231, 231 - 1] 内，最终结果为 0 。
示例 5：
输入：s = "-91283472332"
输出：-2147483648
解释：
第 1 步："-91283472332"（当前没有读入字符，因为没有前导空格）
^
第 2 步："-91283472332"（读入 '-' 字符，所以结果应该是负数）
^
第 3 步："-91283472332"（读入 "91283472332"）
^
解析得到整数 -91283472332 。
由于 -91283472332 小于范围 [-231, 231 - 1] 的下界，最终结果被截断为 -231 = -2147483648 。
Java解法
思路：
- 先读取正确的数据出来：空格 -/+ 数字或 -/+数字 或 数字；其他情况中断
- 先读空格，读到非空格不允许再有空格，读-/+,读到后不允许再出现同时记录正负值
- char转换参考昨天 int边界判断方式进行判断，然后输出结果
package sj.shimmer.algorithm;
/**
* Created by SJ on 2021/1/30.
*/
class D6 {
public static void main(String[] args) {
System.out.println(Integer.MAX_VALUE);
System.out.println(Integer.MIN_VALUE);
System.out.println(myAtoi("42"));
System.out.println(myAtoi(" -42"));
System.out.println(myAtoi("4193 with words"));
System.out.println(myAtoi("words and 987"));
System.out.println(myAtoi("-91283472332"));
System.out.println(myAtoi("+1"));
System.out.println(myAtoi("21474836460"));
System.out.println(myAtoi("00000-42a1234"));
System.out.println(myAtoi("-2147483647"));
}
public static int myAtoi(String s) {
if (s == null || s.length() == 0) {
return 0;
}
boolean isNavi = true;
int result = 0;
boolean canBeSpace = true;
boolean canBeMinusSign = true;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (canBeSpace && c == ' ') {
continue;
}
canBeSpace = false;
if (canBeMinusSign && c == '-') {
isNavi = false;
canBeMinusSign = false;
continue;
}
if (canBeMinusSign && c == '+') {
isNavi = true;
canBeMinusSign = false;
continue;
}
canBeMinusSign = false;
if (c >= '0' && c <= '9') {
if (isNavi) {
if (result > Integer.MAX_VALUE / 10 || (result == Integer.MAX_VALUE / 10 && c > '7')) {
return Integer.MAX_VALUE;
}
result = result * 10 + Integer.parseInt(String.valueOf(c));
}else {
if (result>0) {
result = result * -1;
}
if (result < Integer.MIN_VALUE / 10 || (result == Integer.MIN_VALUE / 10 && c > '8')) {
return Integer.MIN_VALUE;
}
result = result * 10 - Integer.parseInt(String.valueOf(c));
}
} else {
break;
}
}
return result;
}
}
官方解
-
自动机
将程序的状态分别记录为，开始、已标志符号、数字输入中、结束状态
状态\当前输入 ‘’ +/- number other start start signed in_number end signed end end in_number end in_number end end in_number end end end end end end 编码按照状态转换表进行编辑即可
时间复杂度：O(n)，其中 n 为字符串的长度。我们只需要依次处理所有的字符，处理每个字符需要的时间为 O(1)。
空间复杂度：O(1)，自动机的状态只需要常数空间存储。
