数据结构与算法之字符串: LeetCode 8. 字符串转换整数 (atoi) (Ts版)

字符串转换整数 (atoi)

• https://leetcode.cn/problems/string-to-integer-atoi/description/

描述

• 请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数。

• 函数 myAtoi(string s) 的算法如下：

  • 空格：读入字符串并丢弃无用的前导空格（" "）
  • 符号：检查下一个字符（假设还未到字符末尾）为 '-' 还是 '+'。如果两者都不存在，则假定结果为正
  • 转换：通过跳过前置零来读取该整数，直到遇到非数字字符或到达字符串的结尾。如果没有读取数字，则结果为0
  • 舍入：如果整数数超过 32 位有符号整数范围 [−$2^{31}$, $2^{31}$ − 1] ，需要截断这个整数，使其保持在这个范围内。具体来说，小于 −$2^{31}$ 的整数应该被舍入为 −$2^{31}$ ，大于 $2^{31}$ − 1 的整数应该被舍入为 $2^{31}$ − 1

• 返回整数作为最终结果

示例 1

输入：s = "42"
输出：42

示例 2

输入：s = " -042"
输出：-42

示例 3

输入：s = "1337c0d3"
输出：1337

示例 4

输入：s = "0-1"
输出：0

示例 5

输入：s = "words and 987"
输出：0

解释：读取在第一个非数字字符“w”处停止

提示

• 0 <= s.length <= 200
• s 由英文字母（大写和小写）、数字（0-9）、' '、'+'、'-' 和 '.' 组成

Typescript 版算法实现

1 ) 方案1：自动机

class Automaton {
    private state: string = "start";
    private table: { [key: string]: string[] } = {
        "start": ["start", "signed", "in_number", "end"],
        "signed": ["end", "end", "in_number", "end"],
        "in_number": ["end", "end", "in_number", "end"],
        "end": ["end", "end", "end", "end"]
    };

    public sign: number = 1;
    public ans: number = 0;

    private get_col(c: string): number {
        if (c === ' ') return 0;
        if (c === '+' || c === '-') return 1;
        if (!isNaN(parseInt(c, 10))) return 2;
        return 3;
    }

    public get(c: string): void {
        this.state = this.table[this.state][this.get_col(c)];
        if (this.state === "in_number") {
            this.ans = this.ans * 10 + parseInt(c, 10);
            // 检查是否超出32位有符号整数范围
            if (this.sign === 1) {
                this.ans = Math.min(this.ans, 2147483647); // INT_MAX
            } else {
                this.ans = Math.min(this.ans, 2147483648); // -INT_MIN
            }
        } else if (this.state === "signed") {
            this.sign = c === '+' ? 1 : -1;
        }
    }
}

function myAtoi(str: string): number {
    const automaton = new Automaton();
    for (const c of str) {
        automaton.get(c);
    }
    return automaton.sign * automaton.ans;
}

2 ) 方案2：基于特殊符号特殊处理

function myAtoi(s: string): number {
    let res = 0;
    const bndry = Math.floor(Number.MAX_SAFE_INTEGER / 10);
    let i = 0;
    let sign = 1;
    const length = s.length;

    if (length === 0) return 0;

    // Skip leading whitespace
    while (s.charCodeAt(i) === 32) {
        if (++i === length) return 0;
    }

    // Handle sign
    if (s.charCodeAt(i) === 45) {
        sign = -1;
    } else if (s.charCodeAt(i) === 43) {
        // Do nothing for positive sign
    }
    if (s.charCodeAt(i) === 45 || s.charCodeAt(i) === 43) {
        i++;
    }

    // Process digits
    for (let j = i; j < length; j++) {
        const charCode = s.charCodeAt(j);
        if (charCode < 48 || charCode > 57) {
            break;
        }
        const digit = charCode - 48;

        if (res > bndry || (res === bndry && digit > 7)) {
            return sign === 1 ? Number.MAX_SAFE_INTEGER : Number.MIN_SAFE_INTEGER;
        }

        res = res * 10 + digit;
    }

    return sign * res;
}

• 这个方案有精度问题
• 对大部分case都可以通过