题目描述
请你来实现一个 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：
1
2
3
4
5
6
7
8
9
10
11
| 输入：s = "42"
输出：42
解释：加粗的字符串为已经读入的字符，插入符号是当前读取的字符。
第 1 步："42"（当前没有读入字符，因为没有前导空格）
^
第 2 步："42"（当前没有读入字符，因为这里不存在 '-' 或者 '+'）
^
第 3 步："42"（读入 "42"）
^
解析得到整数 42 。
由于 "42" 在范围内，最终结果为 42 。
|
示例 2：
1
2
3
4
5
6
7
8
9
10
11
| 输入：s = " -42"
输出：-42
解释：
第 1 步：" -42"（读入前导空格，但忽视掉）
^
第 2 步：" -42"（读入 '-' 字符，所以结果应该是负数）
^
第 3 步：" -42"（读入 "42"）
^
解析得到整数 -42 。
由于 "-42" 在范围内，最终结果为 -42 。
|
示例 3：
1
2
3
4
5
6
7
8
9
10
11
| 输入：s = "4193 with words"
输出：4193
解释：
第 1 步："4193 with words"（当前没有读入字符，因为没有前导空格）
^
第 2 步："4193 with words"（当前没有读入字符，因为这里不存在 '-' 或者 '+'）
^
第 3 步："4193 with words"（读入 "4193"；由于下一个字符不是一个数字，所以读入停止）
^
解析得到整数 4193 。
由于 "4193" 在范围内，最终结果为 4193 。
|
提示：
- $0 \leq s.length \leq 200$
- $s$ 由英文字母（大写和小写）、数字（$0-9$）、
' '、'+'、'-' 和 '.' 组成
模拟 - $O(N)$
算法流程
这个题目主要是模拟，需要仔细看题目描述的 Atoi 函数的算法流程。
我们总结一下题目中 函数的算法流程：
- 从字符串第一个非空字符开始处理
- 只处理 字符串第一个数字
- 合法数字只有两种情况：无符号只有数字，有一个符号
+, -，后面接一个数字 - 如果获取的数字超过
int 最大值或者最小值，则取 int 最大值或者最小值。
模拟过程
可以结合代码注释来看
- 从左往右遍历找到第一个非空字符
- 第一个非空字符只有 三种情况 才合法：
+, -, 数字 - 如果获取到
- 号，则记录符号为符号，否则为正号 - 从当前位置开始获取数字，直到获取到非数字字符为止
时间复杂度 - $O(N)$
- 只需要枚举一遍字符串，因此时间复杂度为：$O(N)$，其中 $N$ 为字符串长度
代码
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
| func myAtoi(s string) int {
var (
res int64 = 0
sign int64 = 1
)
for i := 0; i < len(s); i++ {
c := s[i]
if c == ' ' { continue }
if c == '-' || c == '+' || (c >= '0' && c <= '9') {
j := i
if c == '-' {
sign = -1
j++
} else if c == '+' {
sign = 1
j++
}
for ; j < len(s); j++ {
if s[j] >= '0' && s[j] <= '9' {
res = res * 10 + sign * int64(s[j] - '0')
if res > math.MaxInt32 {
res = math.MaxInt32
break
}
if res < math.MinInt32 {
res = math.MinInt32
break
}
} else { break }
}
break;
} else { break }
}
return int(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
| class Solution {
public:
int myAtoi(string s) {
long long res = 0;
int sign = 1;
for (int i = 0; i < s.size(); ++i) {
if (s[i] == ' ') continue;
if (s[i] == '-' || s[i] == '+' || isdigit(s[i])) {
if (s[i] == '-') sign = -1, ++i;
else if (s[i] == '+') sign = 1, ++i;
int j = i;
for (; j < s.size(); ++j) {
if (isdigit(s[j])) {
res = res * 10 + sign * (s[j] - '0');
if (res > INT_MAX) {
res = INT_MAX;
break;
}
if (res < INT_MIN) {
res = INT_MIN;
break;
}
} else break;
}
break;
} else break;
}
return res;
}
};
|