在 leetcode 刷题过程中，刷到字符串转整形的算法，记录一下解决的方法和后续的一些优化。
字符串转整形是开发中经常遇到的，每个语言标准库基本都有实现。
算法题的描述可以看 这里。
在第一次做这道题时，我按照描述，依次实现代码。第一个是想到将字符串转为 byte，
并按照规则识别每个字节。该实现过于冗长并复杂，调试几次后，终于通过了 leetcode 的测试。
提交如下，执行了 8ms
代码如下:
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
|
func myAtoi(str string) int {
i := 0
sign := 0 // 0 无符号 / 1 + / 2 -
hasNum := false
a := []byte(str)
for _, value := range a {
// 排除字母
if value < 48 || value > 57 {
if sign > 0 || hasNum {
break
}
if value != 45 && value != 43 && value != 32 {
break
}
}
// 记录符号
if i == 0 {
if value == 43 {
sign = 1
continue
}
if value == 45 {
sign = 2
continue
}
}
if b := isNumber(value); b != -1 {
hasNum = true
i = i*10 + b
if i > math.MaxInt32 {
break
}
}
}
if i > math.MaxInt32 {
if sign == 2 {
return math.MinInt32
} else {
return math.MaxInt32
}
}
if sign == 2 {
i = i - 2*i
}
return i
}
func isNumber(b byte) int {
if b >= 48 && b <= 57 {
return int(b) - 48
}
return -1
}
|
该实现虽然通过了，但执行效率只击败了 25% 的提交，而且代码结构自己看了也比较蛋疼。
今天分析了一下，决定重新实现一遍。
从描述中，我提取了四个关键点：
- 检测空白符，允许在符号和数字前出现
- 排除字母，一旦出现字符，即停止解析转化
- 记录符号，允许在数字之前出现一次符号，即
- 与 +
- 避免整形溢出
优化过的代码如下:
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
|
func myAtoi(str string) int {
num := 0
sign := ""
start := false // 一旦解析到数字或符号则为 true
for key := range str {
// 校验空白符
if str[key:key+1] == " " && !start {
continue
}
// 校验符号
if (str[key:key+1] == "+" || str[key:key+1] == "-") && !start {
start = true
sign = str[key : key+1]
continue
}
// 校验数字
if str[key:key+1] >= "0" && str[key:key+1] <= "9" {
// 检测溢出
if num > math.MaxInt32/10 || (num == math.MaxInt32/10 && str[key:key+1] > "7") {
if sign == "-" {
return math.MinInt32
}
return math.MaxInt32
}
start = true
num = num*10 + int(str[key]) - 48
continue
}
// 不符合上述规则的直接结束
break
}
if sign == "-" {
num = -num
}
return num
}
|
优化过后的代码提交到 leetcode，整个测试用例执行时间缩短了一半，并击败了 100% 的 go 实现提交，
并且代码结构也得到简化。
该实现遍历规则有所改变，符合规则就继续遍历，不符合则直接 break，这将减少大量计算时间。
这和在平常编程中函数提前返回是相同的想法，能够简化逻辑，减少代码行数和嵌套次数。