leetcode-in-rust 0.2.10

//! # 问题描述
//!
//! 请你来实现一个 `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：
//! ```plain
//! 输入：s = "42"
//! 输出：42
//! 解释：加粗的字符串为已经读入的字符，插入符号是当前读取的字符。
//! 第 1 步："42"（当前没有读入字符，因为没有前导空格）
//!          ^
//! 第 2 步："42"（当前没有读入字符，因为这里不存在 '-' 或者 '+'）
//!          ^
//! 第 3 步："42"（读入 "42"）
//!            ^
//! 解析得到整数 42 。
//! 由于 "42" 在范围 $[−2^{31},  2^{31} − 1]$ 内，最终结果为 42。
//! ```
//!
//! 示例 2：
//!
//! ```plain
//! 输入：s = "   -42"
//! 输出：-42
//! 解释：
//! 第 1 步："   -42"（读入前导空格，但忽视掉）
//!             ^
//! 第 2 步："   -42"（读入 '-' 字符，所以结果应该是负数）
//!              ^
//! 第 3 步："   -42"（读入 "42"）
//!                ^
//! 解析得到整数 -42 。
//! 由于 "-42" 在范围 $[−2^{31},  2^{31} − 1]$ 内，最终结果为 -42。
//! ```
//!
//! 示例 3：
//!
//! ```plain
//! 输入：s = "4193 with words"
//! 输出：4193
//! 解释：
//! 第 1 步："4193 with words"（当前没有读入字符，因为没有前导空格）
//!          ^
//! 第 2 步："4193 with words"（当前没有读入字符，因为这里不存在 '-' 或者 '+'）
//!          ^
//! 第 3 步："4193 with words"（读入 "4193"；由于下一个字符不是一个数字，所以读入停止）
//!              ^
//! 解析得到整数 4193。
//! 由于 "4193" 在范围 $[−2^{31},  2^{31} − 1]$ 内，最终结果为 `4193`。
//! ```
//!
//! 提示：
//!
//! - `0 $\leqslant$ s.length $\leqslant$ 200`
//! - `s` 由英文字母（大写和小写）、数字（`0-9`）、'` `'、'`+`'、'`-`' 和 '`.`' 组成
//!
//! 来源：<https://leetcode.cn/problems/string-to-integer-atoi>

////////////////////////////////////////////////////////////////////////////////

/// 字符串转换为 32 位整型数
///
/// # 参数
/// * `s` - 待转换字符串
///
/// # 示例
/// ```
/// use leetcode_rust::problems_cn::p000_0xx::p000_008::my_atoi;
///
/// assert!(my_atoi(String::from("-12.5")) == -12);
/// ```
pub fn my_atoi(s: String) -> i32 {
    // 用于检测溢出的 i32 类型阈值，当检测到为负数时，需要修改最后一位的值。注意这个阈值
    // 是绝对值形式，不包含符号
    let mut threshold_val: [u8; 10] = [50, 49, 52, 55, 52, 56, 51, 54, 52, 55];

    // 标记传入字符串是否对应了一个负数
    let mut is_negative = false;

    // 标记是否再扫描字符串过程中已经出现过数字
    let mut has_digits = false;

    // 传入字符串中当前正在被扫描的字节位置索引
    let mut curr_idx: usize = 0;

    // 标记当前已经扫描的内容可以判定为数字形式
    let mut is_started = false;

    // 用于记录扫描过程中的已解析值和作为返回值的变量
    let mut val: i32 = 0;

    // 传入字符串的字节 slice 形式，方便迭代计算
    let s_bytes = s.as_bytes();

    // 标记已经解析的部分是否已经造成 i32 类型溢出
    let mut is_overflow = false;

    // 在某些情况下，我们需要跳过对于溢出的逐位检查（比如已经解析部分的起始部分数字小于阈值），
    // 此时仍然需要进行长度检查
    let mut is_overflow_ignored = false;

    // 标记是否当前已经扫描的部分和对应的阈值前面的数位完全一致
    let mut is_full_match = true;

    // 包含了所有已经解析的数字位的向量
    let mut val_vec: Vec<u8> = vec![];

    // 无限循环的部分
    // 循环的终结条件由字符终止和其他标志位结合判定
    loop {
        if curr_idx == s_bytes.len() {
            // 防止循环无法终结
            break;
        }

        if s_bytes[curr_idx] == 32 {
            // 扫描到空白符，需要根据其上下文判定
            if !is_started {
                // 位于字符串前部的某个空白符，可以忽略
                curr_idx += 1;
                continue;
            } else {
                // 位于字符串中间穿插在其他字符之后的空白符，不合法，标志着扫描结束
                break;
            }
        }

        if [43u8, 45u8].contains(&s_bytes[curr_idx]) {
            // 判定结果的正负号
            if has_digits {
                // 若干数位之后出现符号位，不合法，结束扫描
                // 如：`12-222`, `0+123`
                break;
            }
            if !is_started {
                // 此时对数值的判定尚未开始，因此可以作为符号位解析。
                if s_bytes[curr_idx] == 45 {
                    // 负数，调整符号位并更新溢出判定的阈值
                    is_negative = true;
                    threshold_val = [50, 49, 52, 55, 52, 56, 51, 54, 52, 56];
                }
                // 设置扫描状态以避免出现 `-+` 等连续符号的序列
                // 因为符号位之后必须跟数字
                is_started = true;
                curr_idx += 1;
                continue;
            }
        }

        // 遇到数字，需要结合上下文解析
        if 48 <= s_bytes[curr_idx] && s_bytes[curr_idx] <= 57 {
            // 遇到数字，立即设置对应标志位以避免出现不合法的数字序列：
            // 如：`0 123`、`123-6`.
            has_digits = true;
            is_started = true;

            if val == 0 && s_bytes[curr_idx] == 48 {
                // 跳过所有的前导 0
                curr_idx += 1;
                continue;
            }

            // 处理非前导 0 的数字位
            if val_vec.len() >= threshold_val.len() - 1 {
                // 处理的第一个步骤就是判断是否溢出，而为了节省计算时间，只有当已经识别的
                // 数字位数量和溢出值相同或少于溢出位 1 个字节时才进行溢出检查。并且提前执
                // 行溢出检查是没有意义的，会造成逐字节比对时的误判。

                // 接下来的遍历将执行以下两项检查：
                // 1. 是否已经解析的部分中存在与溢出阈值完全相同的连续数位；
                // 2. 是否已经解析的部分不需要在后续迭代中再次遍历检查
                for idx in 0..val_vec.len() {
                    if !is_overflow {
                        // 只要判断溢出，就不必要再浪费计算周期了
                        if !is_overflow_ignored && val_vec[idx] > threshold_val[idx] {
                            // 没有跳过逐项检查标记，而当前检查的数位又比阈值的对应数位值
                            // 大，说明已经溢出了，不必要再检查。
                            is_overflow = true;
                            is_full_match = false;
                            break;
                        } else if val_vec[idx] < threshold_val[idx] {
                            // 从头开始的某一个数位比阈值的数位要小，说明只要长度不超
                            // 那么这个已经解析的数字就不会发生溢出，因此可以跳过本轮
                            // 后续的逐字节检查。
                            // 至于长度是否会超，由后续代码判断。
                            is_full_match = false;
                            is_overflow_ignored = true;
                        }
                    }
                }

                if !is_overflow {
                    // 当前面的逐字节检查未能判断溢出时，需要检查即将写入的数位是否为造成：
                    // 1. 数字长度超过阈值造成溢出；
                    // 2. 数字值（通常是最后一个数位）超过阈值造成溢出。
                    if val_vec.len() == threshold_val.len() - 1 {
                        // 检查新增后值是否超过阈值
                        // 检查的前提是，已经解析的数值的所有数位与阈值完全相同
                        if is_full_match
                            && s_bytes[curr_idx] > threshold_val[threshold_val.len() - 1]
                        {
                            is_overflow = true;
                            break;
                        }
                    } else if val_vec.len() == threshold_val.len() {
                        // 检查新增后长度是否超过阈值
                        is_overflow = true;
                        break;
                    }
                }
            }
            if is_overflow {
                // 由于已经判定溢出，所以不必操作当前数位，直接结束循环
                break;
            }
            val = val * 10 + (s_bytes[curr_idx] - 48) as i32;
            val_vec.push(s_bytes[curr_idx]);
            curr_idx += 1;
            continue;
        }

        break;
    }
    // 下面的步骤用于根据是否溢出、正负号，结合已经解析的数值返回最终结果
    if is_overflow {
        if is_negative {
            -2147483648
        } else {
            2147483647
        }
    } else {
        if is_negative {
            -val
        } else {
            val
        }
    }
}