力扣挑战赛第2天-No.8字符串转换整数

题目描述

请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数（类似 C/C++ 中的 atoi 函数）。

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

1. 读入字符串并丢弃无用的前导空格
2. 检查下一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如果有）。 确定最终结果是负数还是正数。如果两者都不存在，则假定结果为正。
3. 读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。
   将前面步骤读入的这些数字转换为整数（即，”123” -> 123， “0032” -> 32）。如果没有读入数字，则整数为 0 。必要时更改符号（从步骤 2 开始）。
4. 如果整数数超过 32 位有符号整数范围 [−2 ** 31,  2 ** 31 − 1] ，需要截断这个整数，使其保持在这个范围内。具体来说，小于 −2 ** 31 的整数应该被固定为 −2 ** 31 ，大于 2 ** 31 − 1 的整数应该被固定为 2 ** 31 − 1 。
5. 返回整数作为最终结果。

示例：

输入：s = "4193 with words"
输出：4193
输入：s = "words and 987"
输出：0
输入：s = "   -42"
输出：-42
输入：s = "-91283472332"
输出：-2147483648（-2 ** 31）

注意：

本题中的空白字符只包括空格字符 ' ' 。
除前导空格或数字后的其余字符串外，请勿忽略任何其他字符。
0 <= s.length <= 200
s 由英文字母（大写和小写）、数字（0-9）、' '、'+'、'-' 和 '.' 组成

解法

这里只介绍有限状态机（DFA），类似于编译原理：

状态转换表：

状态转换图：

如遇图片无法显示请访问 力扣-字符串转整数

/**
 * @param {string} s
 * @return {number}
 */
const myAtoi = function (s) {
  class Automation {
    constructor() {
      this.state = 'start'; // 开始状态
      this.sign = 1; // 1代表正，0代表负
      this.res = 0; // 初始数值为0
      /* 定义状态转换表 */
      this.map = new Map([
        //状态，遇到 => [空格，正负号，字符型数值，其他字符]，会跳到对应的状态
        ['start', ['start', 'signed', 'in_number', 'end']],
        ['signed', ['end', 'end', 'in_number', 'end']],
        ['in_number', ['end', 'end', 'in_number', 'end']],
        ['end', ['end', 'end', 'end', 'end']]
      ]);
    }
    /* 获取每种字符对应的即将转换到的状态索引 */
    getStateIndex(char) {
      if (char === ' ') { // 空格
        return 0;
      } else if (char === '+' || char === '-') { //正负号
        return 1;
      } else if (parseInt(char) >= 0) { // 字符型数值
        return 2;
      } else { // 其他字符
        return 3;
      }
    }
    /* 对输入的字符进行状态转换 并处理数据 */
    turnAndHandle(char) {
      this.state = this.map.get(this.state)[this.getStateIndex(char)];
      if (this.state === 'in_number') {
        this.res = this.res * 10 + (char - 0); // 计算数值
        this.res = this.sign === 1 ? Math.min(this.res, Math.pow(2, 31) - 1) : Math.min(this.res, -Math.pow(-2, 31)); // 判断是否溢出
      } else if (this.state === 'signed') {
        this.sign = char === '+' ? 1 : -1; // 设置正负号
      }
    }
  }
  let automaton = new Automation();
  for (let char of s) { // 遍历字符串的每一个字符
    automaton.turnAndHandle(char);
  }
  return automaton.sign * automaton.res;
}

Donate