字符串转换整数，处理大数越界问题
写一个函数 StrToInt，实现把字符串转换成整数这个功能。不能使用 atoi 或者其他类似的库函数。
首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。
当我们寻找到的第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字组合起来，作为该整数的正负号；假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数。
该字符串除了有效的整数部分之后也可能会存在多余的字符，这些字符可以被忽略，它们对于函数不应该造成影响。
注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换。
在任何情况下，若函数不能进行有效的转换时，请返回 0。
说明：
假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−231, 231 − 1]。如果数值超过这个范围，请返回 INT_MAX (231 − 1) 或 INT_MIN (−231) 。
示例 1:
输入: “42”
输出: 42
思路：
这题用自动机有点杀鸡用牛刀的味道。但无论如何，自动机都可以作为此类问题的最终手段来使用。
- 首先出现的是前导空格，去除字符串中前导（和末尾）空格可以使用 String 的 trim() 函数来去除。考虑效率的话，可以用一个循环语句去除。
- 数字处理阶段，首先判断符号位，可以用一个变量 sign 记录之，待返回结果时再处理。然后是数字主体部分，我们先按绝对值考虑之，这部分数字处理主要考虑大数越界问题。每次加入新的位都要考虑溢出问题，我们比较当前结果与 214748364 （即 MAX_VALUE / 10）的大小关系，若大于，则必定溢出；若小于，则绝对不溢出；相等，则进一步判断：当新的位小于等于 7，不会溢出，否则溢出，我们简单地以一个溢出标志标记它，过后再处理。
本阶段遇见任何非法字符（数字以外的字符）都要立即停止处理，按停止时的结果处理返回值。
- 最后，对于输出结果，如果存在溢出情况，根据 sign 为正或者负，直接返回 MAX_VALUE 或 MIN_VALUE。否则，将结果乘以 sign 后返回。
时间复杂度：O(n)
空间复杂度：O(1)
实现：
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
| class Solution {
public int strToInt(String str) {
int sign = 1, res = 0;
boolean overflow = false;
int len = str.length();
if (len == 0) {
return 0;
}
int i = 0;
while (str.charAt(i) == ' ') {
if (++i == len) {
return 0;
}
}
char c = str.charAt(i);
if (c == '-' || c == '+') {
if (c == '-') {
sign = -1;
}
i++;
}
for (; i < len; i++) {
c = str.charAt(i);
if (c < '0' || c > '9') {
break;
}
if (res > 214748364) {
overflow = true;
break;
} else if (res == 214748364 && c > '7') {
overflow = true;
break;
}
res *= 10;
res += c - '0';
}
if (overflow) {
return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
} else {
return sign * res;
}
}
}
|
另附自动机实现：
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
| class Solution {
class Automaton {
private Map<String, String[]> map = new HashMap<>(){{
put("start", new String[] {"start", "sign", "num", "end"});
put("sign", new String[] {"end", "end", "num", "end"});
put("num", new String[] {"end", "end", "num", "end"});
put("end", new String[] {"end", "end", "end", "end"});
}};
private String stat = "start";
private String input;
private int sign = 1;
private void process() {
int res = 0;
int len = input.length();
for (int i = 0;i < len; i++) {
char c = input.charAt(i);
stat = map.get(stat)[getCol(c)];
if (stat == "num") {
if (res > 214748364 || (res == 214748364 && c - '0' > 7)) {
output = Integer.MAX_VALUE;
return;
} else if (res < -214748364 || (res == -214748364 && c - '0' > 8 )) {
output = Integer.MIN_VALUE;
return;
}
res *= 10;
res += (c - '0') * sign;
} else if (stat == "sign") {
if (c == '-') {
sign = -1;
} else if (stat == "end") {
output = res;
return;
}
}
}
output = res;
}
private int getCol(char c) {
if (c == ' ') {
return 0;
} else if (c == '+' || c == '-') {
return 1;
} else if (c >= '0' && c <= '9') {
return 2;
} else {
return 3;
}
}
public Automaton(String s) {
input = s;
output = 0;
process();
}
public int output;
}
public int strToInt(String str) {
Automaton auto = new Automaton(str);
return auto.output;
}
}
|
