-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathStringToInteger.java
More file actions
154 lines (149 loc) · 6.38 KB
/
Copy pathStringToInteger.java
File metadata and controls
154 lines (149 loc) · 6.38 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
package com.leetcode.string;
import java.util.HashMap;
import java.util.Map;
public class StringToInteger {
/**
* 请你来实现一个myAtoi(string s)函数，使其能将字符串转换成一个 32 位有符号整数（类似 C/C++ 中的 atoi 函数）。
*
* 函数myAtoi(string s) 的算法如下：
*
* 读入字符串并丢弃无用的前导空格
* 检查下一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如果有）。 确定最终结果是负数还是正数。 如果两者都不存在，则假定结果为正。
* 读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。
* 将前面步骤读入的这些数字转换为整数（即，"123" -> 123， "0032" -> 32）。如果没有读入数字，则整数为 0 。必要时更改符号（从步骤 2 开始）。
* 如果整数数超过 32 位有符号整数范围 [−2^31, 2^31− 1] ，需要截断这个整数，使其保持在这个范围内。具体来说，小于 −2^31 的整数应该被固定为 −2^31 ，
* 大于 2^31− 1 的整数应该被固定为 2^31− 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" 在范围 [-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" 在范围 [-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 。
*
*
* 提示：
*
* 0 <= s.length <= 200
* s 由英文字母（大写和小写）、数字（0-9）、' '、'+'、'-' 和 '.' 组成
*
* 链接：https://leetcode-cn.com/problems/string-to-integer-atoi
*/
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);
}
/**
* ' ' +/- 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
*
* 作者：LeetCode-Solution
* 链接：https://leetcode-cn.com/problems/string-to-integer-atoi/solution/zi-fu-chuan-zhuan-huan-zheng-shu-atoi-by-leetcode-/
* 来源：力扣（LeetCode）
* 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
*/
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;
}
}
}