leetcode_rust/problems_cn/p000_0xx/p000_008.rs
1//! # 问题描述
2//!
3//! 请你来实现一个 `myAtoi(string s)` 函数,使其能将字符串转换成一个 32 位有符号整数(类似 C/C++ 中的 `atoi` 函数)。
4//!
5//! 函数 `myAtoi(string s)` 的算法如下:
6//!
7//! 读入字符串并丢弃无用的前导空格
8//!
9//! 检查下一个字符(假设还未到字符末尾)为正还是负号,读取该字符(如果有)。 确定最终结果是
10//! 负数还是正数。 如果两者都不存在,则假定结果为正。
11//!
12//! 读入下一个字符,直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。
13//!
14//! 将前面步骤读入的这些数字转换为整数(即,"123" -> 123, "0032" -> 32)。如果没有读入
15//! 数字,则整数为 `0` 。必要时更改符号(从步骤 2 开始)。
16//!
17//! 如果整数数超过 32 位有符号整数范围 $[−2^{31}, 2^{31} − 1]$ ,需要截断这个整数,使其
18//! 保持在这个范围内。具体来说,小于 $−2^{31}$ 的整数应该被固定为 $−2^{31}$ ,大于
19//! $2^{31} -1$ 的整数应该被固定为 $2^{31} -1$。
20//!
21//! 返回整数作为最终结果。
22//!
23//! 注意:
24//!
25//! - 本题中的空白字符只包括空格字符 '` `' 。
26//! - 除前导空格或数字后的其余字符串外,请勿忽略 任何其他字符。
27//!
28//! 示例 1:
29//! ```plain
30//! 输入:s = "42"
31//! 输出:42
32//! 解释:加粗的字符串为已经读入的字符,插入符号是当前读取的字符。
33//! 第 1 步:"42"(当前没有读入字符,因为没有前导空格)
34//! ^
35//! 第 2 步:"42"(当前没有读入字符,因为这里不存在 '-' 或者 '+')
36//! ^
37//! 第 3 步:"42"(读入 "42")
38//! ^
39//! 解析得到整数 42 。
40//! 由于 "42" 在范围 $[−2^{31}, 2^{31} − 1]$ 内,最终结果为 42。
41//! ```
42//!
43//! 示例 2:
44//!
45//! ```plain
46//! 输入:s = " -42"
47//! 输出:-42
48//! 解释:
49//! 第 1 步:" -42"(读入前导空格,但忽视掉)
50//! ^
51//! 第 2 步:" -42"(读入 '-' 字符,所以结果应该是负数)
52//! ^
53//! 第 3 步:" -42"(读入 "42")
54//! ^
55//! 解析得到整数 -42 。
56//! 由于 "-42" 在范围 $[−2^{31}, 2^{31} − 1]$ 内,最终结果为 -42。
57//! ```
58//!
59//! 示例 3:
60//!
61//! ```plain
62//! 输入:s = "4193 with words"
63//! 输出:4193
64//! 解释:
65//! 第 1 步:"4193 with words"(当前没有读入字符,因为没有前导空格)
66//! ^
67//! 第 2 步:"4193 with words"(当前没有读入字符,因为这里不存在 '-' 或者 '+')
68//! ^
69//! 第 3 步:"4193 with words"(读入 "4193";由于下一个字符不是一个数字,所以读入停止)
70//! ^
71//! 解析得到整数 4193。
72//! 由于 "4193" 在范围 $[−2^{31}, 2^{31} − 1]$ 内,最终结果为 `4193`。
73//! ```
74//!
75//! 提示:
76//!
77//! - `0 $\leqslant$ s.length $\leqslant$ 200`
78//! - `s` 由英文字母(大写和小写)、数字(`0-9`)、'` `'、'`+`'、'`-`' 和 '`.`' 组成
79//!
80//! 来源:<https://leetcode.cn/problems/string-to-integer-atoi>
81
82////////////////////////////////////////////////////////////////////////////////
83
84/// 字符串转换为 32 位整型数
85///
86/// # 参数
87/// * `s` - 待转换字符串
88///
89/// # 示例
90/// ```
91/// use leetcode_rust::problems_cn::p000_0xx::p000_008::my_atoi;
92///
93/// assert!(my_atoi(String::from("-12.5")) == -12);
94/// ```
95pub fn my_atoi(s: String) -> i32 {
96 // 用于检测溢出的 i32 类型阈值,当检测到为负数时,需要修改最后一位的值。注意这个阈值
97 // 是绝对值形式,不包含符号
98 let mut threshold_val: [u8; 10] = [50, 49, 52, 55, 52, 56, 51, 54, 52, 55];
99
100 // 标记传入字符串是否对应了一个负数
101 let mut is_negative = false;
102
103 // 标记是否再扫描字符串过程中已经出现过数字
104 let mut has_digits = false;
105
106 // 传入字符串中当前正在被扫描的字节位置索引
107 let mut curr_idx: usize = 0;
108
109 // 标记当前已经扫描的内容可以判定为数字形式
110 let mut is_started = false;
111
112 // 用于记录扫描过程中的已解析值和作为返回值的变量
113 let mut val: i32 = 0;
114
115 // 传入字符串的字节 slice 形式,方便迭代计算
116 let s_bytes = s.as_bytes();
117
118 // 标记已经解析的部分是否已经造成 i32 类型溢出
119 let mut is_overflow = false;
120
121 // 在某些情况下,我们需要跳过对于溢出的逐位检查(比如已经解析部分的起始部分数字小于阈值),
122 // 此时仍然需要进行长度检查
123 let mut is_overflow_ignored = false;
124
125 // 标记是否当前已经扫描的部分和对应的阈值前面的数位完全一致
126 let mut is_full_match = true;
127
128 // 包含了所有已经解析的数字位的向量
129 let mut val_vec: Vec<u8> = vec![];
130
131 // 无限循环的部分
132 // 循环的终结条件由字符终止和其他标志位结合判定
133 loop {
134 if curr_idx == s_bytes.len() {
135 // 防止循环无法终结
136 break;
137 }
138
139 if s_bytes[curr_idx] == 32 {
140 // 扫描到空白符,需要根据其上下文判定
141 if !is_started {
142 // 位于字符串前部的某个空白符,可以忽略
143 curr_idx += 1;
144 continue;
145 } else {
146 // 位于字符串中间穿插在其他字符之后的空白符,不合法,标志着扫描结束
147 break;
148 }
149 }
150
151 if [43u8, 45u8].contains(&s_bytes[curr_idx]) {
152 // 判定结果的正负号
153 if has_digits {
154 // 若干数位之后出现符号位,不合法,结束扫描
155 // 如:`12-222`, `0+123`
156 break;
157 }
158 if !is_started {
159 // 此时对数值的判定尚未开始,因此可以作为符号位解析。
160 if s_bytes[curr_idx] == 45 {
161 // 负数,调整符号位并更新溢出判定的阈值
162 is_negative = true;
163 threshold_val = [50, 49, 52, 55, 52, 56, 51, 54, 52, 56];
164 }
165 // 设置扫描状态以避免出现 `-+` 等连续符号的序列
166 // 因为符号位之后必须跟数字
167 is_started = true;
168 curr_idx += 1;
169 continue;
170 }
171 }
172
173 // 遇到数字,需要结合上下文解析
174 if 48 <= s_bytes[curr_idx] && s_bytes[curr_idx] <= 57 {
175 // 遇到数字,立即设置对应标志位以避免出现不合法的数字序列:
176 // 如:`0 123`、`123-6`.
177 has_digits = true;
178 is_started = true;
179
180 if val == 0 && s_bytes[curr_idx] == 48 {
181 // 跳过所有的前导 0
182 curr_idx += 1;
183 continue;
184 }
185
186 // 处理非前导 0 的数字位
187 if val_vec.len() >= threshold_val.len() - 1 {
188 // 处理的第一个步骤就是判断是否溢出,而为了节省计算时间,只有当已经识别的
189 // 数字位数量和溢出值相同或少于溢出位 1 个字节时才进行溢出检查。并且提前执
190 // 行溢出检查是没有意义的,会造成逐字节比对时的误判。
191
192 // 接下来的遍历将执行以下两项检查:
193 // 1. 是否已经解析的部分中存在与溢出阈值完全相同的连续数位;
194 // 2. 是否已经解析的部分不需要在后续迭代中再次遍历检查
195 for idx in 0..val_vec.len() {
196 if !is_overflow {
197 // 只要判断溢出,就不必要再浪费计算周期了
198 if !is_overflow_ignored && val_vec[idx] > threshold_val[idx] {
199 // 没有跳过逐项检查标记,而当前检查的数位又比阈值的对应数位值
200 // 大,说明已经溢出了,不必要再检查。
201 is_overflow = true;
202 is_full_match = false;
203 break;
204 } else if val_vec[idx] < threshold_val[idx] {
205 // 从头开始的某一个数位比阈值的数位要小,说明只要长度不超
206 // 那么这个已经解析的数字就不会发生溢出,因此可以跳过本轮
207 // 后续的逐字节检查。
208 // 至于长度是否会超,由后续代码判断。
209 is_full_match = false;
210 is_overflow_ignored = true;
211 }
212 }
213 }
214
215 if !is_overflow {
216 // 当前面的逐字节检查未能判断溢出时,需要检查即将写入的数位是否为造成:
217 // 1. 数字长度超过阈值造成溢出;
218 // 2. 数字值(通常是最后一个数位)超过阈值造成溢出。
219 if val_vec.len() == threshold_val.len() - 1 {
220 // 检查新增后值是否超过阈值
221 // 检查的前提是,已经解析的数值的所有数位与阈值完全相同
222 if is_full_match
223 && s_bytes[curr_idx] > threshold_val[threshold_val.len() - 1]
224 {
225 is_overflow = true;
226 break;
227 }
228 } else if val_vec.len() == threshold_val.len() {
229 // 检查新增后长度是否超过阈值
230 is_overflow = true;
231 break;
232 }
233 }
234 }
235 if is_overflow {
236 // 由于已经判定溢出,所以不必操作当前数位,直接结束循环
237 break;
238 }
239 val = val * 10 + (s_bytes[curr_idx] - 48) as i32;
240 val_vec.push(s_bytes[curr_idx]);
241 curr_idx += 1;
242 continue;
243 }
244
245 break;
246 }
247 // 下面的步骤用于根据是否溢出、正负号,结合已经解析的数值返回最终结果
248 if is_overflow {
249 if is_negative {
250 -2147483648
251 } else {
252 2147483647
253 }
254 } else {
255 if is_negative {
256 -val
257 } else {
258 val
259 }
260 }
261}