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}