0065.有效数字.md

解题关键点

• 这题关键点就在于后面的测试用例，覆盖到所有的特殊情况就赢了，难度主要在边界情况的考虑方面
• O(n) 的时间复杂度，没什么好说的

代码

impl Solution {
    pub fn is_number(s: String) -> bool {
        let chars: Vec<char> = s.chars().collect();
        let len = chars.len();
        // 是否存在整数部分
        let mut has_int = false;
        // 是否存在小数部分
        let mut has_float = false;
        // 符号出现的位置
        let mut sign = 0;
        // 小数点出现的位置
        let mut float = 0;
        // 科学计数法标识符出现的位置
        let mut exp = 0;
        for i in 0..len {
            if "0123456789".contains(chars[i]) {
                if float == 0 {
                    has_int = true;
                } else {
                    has_float = true;
                }
                continue;
            }
            if chars[i] == '.' {
                if float == 0 && exp == 0 && (has_int || i < len - 1) {
                    float = i + 1;
                    continue;
                }
                return false;
            }
            if i == len - 1 {
                return false;
            }
            if "+-".contains(chars[i]) {
                if i == 0 || i == exp {
                    sign = 1;
                    continue;
                }
                return false;
            }
            if "eE".contains(chars[i]) {
                if exp == 0 && i > sign && (has_int || has_float) {
                    exp = i + 1;
                    continue;
                }
                return false;
            }
            return false;
        }
        true
    }
}

又学习了一个使用状态机来实现的方式

// 枚举所有状态
enum NumberState {
    StateStart, // 开始位置
    StateSign, // 以符号开始
    StateInt, // 整数部分
    StatePoint, // 小数点
    StatePointWithoutInt, // 无整数的小数点
    StateFloat, // 小数部分
    StateExp, // 科学计数法标识符
    StateExpSign, // 科学计数法符号
    StateExpInt, // 科学计数法整数部分
    StateError, // 错误状态
    StateEnd, // 正确结束才会走到这里
}

// 枚举字符类型
enum CharType {
    CharNumber, // 数值
    CharPoint, // 小数点
    CharSign, // 符号
    CharExp, // 科学计数法标识符
    CharEnd, // 结束位置
    CharOther, // 其它
}

use crate::NumberState::*;
use crate::CharType::*;

// 更新状态，接受一个输入状态和一个当前字符类型，返回更新后的状态
// 如果字符类型和输入状态不匹配，就返回 StateError
// CharEnd 只有符合某些特定的输入状态，才会返回 StateEnd
fn upd_state(c: CharType, input: NumberState) -> NumberState {
    match input {
        StateStart =>
            match c {
                CharSign => StateSign,
                CharNumber => StateInt,
                CharPoint => StatePointWithoutInt,
                _ => StateError,
            },
        StateSign =>
            match c {
                CharNumber => StateInt,
                CharPoint => StatePointWithoutInt,
                _ => StateError,
            },
        StateInt =>
            match c {
                CharNumber => StateInt,
                CharPoint => StatePoint,
                CharExp => StateExp,
                CharEnd => StateEnd,
                _ => StateError,
            },
        StatePoint =>
            match c {
                CharNumber => StateFloat,
                CharExp => StateExp,
                CharEnd => StateEnd,
                _ => StateError,
            },
        StatePointWithoutInt =>
            match c {
                CharNumber => StateFloat,
                _ => StateError,
            },
        StateFloat =>
            match c {
                CharNumber => StateFloat,
                CharExp => StateExp,
                CharEnd => StateEnd,
                _ => StateError,
            },
        StateExp =>
            match c {
                CharSign => StateExpSign,
                CharNumber => StateExpInt,
                _ => StateError,
            },
        StateExpSign =>
            match c {
                CharNumber => StateExpInt,
                _ => StateError,
            },
        StateExpInt =>
            match c {
                CharNumber => StateExpInt,
                CharEnd => StateEnd,
                _ => StateError,
            },
        _ => StateError,
    }
}

impl Solution {
    pub fn is_number(s: String) -> bool {
        // 初始化状态
        let mut state = StateStart;
        // 直接遍历字符即可
        for c in s.chars() {
            let c_type = match c {
                // match guard 的语法
                _c if _c >= '0' && _c <= '9' => CharNumber,
                // match 联合类型
                '+' | '-' => CharSign,
                '.' => CharPoint,
                'e' | 'E' => CharExp,
                _ => CharOther,
            };
            // 更新状态
            state = upd_state(c_type, state);
            // 遇到 StateError 就直接中断（这个判断可写可不写，取决于测试用例的倾向性，如果正确的 case 较多，那么不写反而效率更高）
            if match state {
                StateError => true,
                _ => false
            } {
                return false;
            }
        }
        // 最后传入 CharEnd 拿结果，直接返回
        match upd_state(CharEnd, state) {
            StateEnd => true,
            _ => false,
        }
    }
}

测试用例

assert_eq!(is_number("+".to_string()), false);
assert_eq!(is_number(".".to_string()), false);
assert_eq!(is_number("+.".to_string()), false);
assert_eq!(is_number("e".to_string()), false);
assert_eq!(is_number("x".to_string()), false);
assert_eq!(is_number("1".to_string()), true);
assert_eq!(is_number(".1".to_string()), true);
assert_eq!(is_number("1.".to_string()), true);
assert_eq!(is_number("1.1".to_string()), true);
assert_eq!(is_number("-1.1".to_string()), true);
assert_eq!(is_number("+1.1".to_string()), true);
assert_eq!(is_number("+1.1E".to_string()), false);
assert_eq!(is_number("+1.1e1".to_string()), true);
assert_eq!(is_number("+.1e1".to_string()), true);
assert_eq!(is_number("+.E1".to_string()), false);
assert_eq!(is_number("+.1e1.1".to_string()), false);
assert_eq!(is_number("+.1e-1".to_string()), true);
assert_eq!(is_number("+1.e-1".to_string()), true);
assert_eq!(is_number("+1.e-1.".to_string()), false);
assert_eq!(is_number("+1e-1.".to_string()), false);