「有限状态自动机」相关题目

前言

在计算理论中，确定有限状态自动机或确定有限自动机（英语：deterministic finite automaton, DFA）是一个能实现状态转移的自动机。对于一个给定的属于该自动机的状态和一个属于该自动机字母表Σ的字符，它都能根据事先给定的转移函数转移到下一个状态（这个状态可以是先前那个状态)。

@wiki

题目

剑指 Offer 20. 表示数值的字符串

题目描述

请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。

数值（按顺序）可以分成以下几个部分：

1. 若干空格

2. 一个 小数 或者 整数

3. （可选）一个 ‘e’ 或 ‘E’ ，后面跟着一个 整数

4. 若干空格

小数（按顺序）可以分成以下几个部分：

1. （可选）一个符号字符（‘+’ 或 ‘-’）

2. 下述格式之一：

   1. 至少一位数字，后面跟着一个点 ‘.’

   2. 至少一位数字，后面跟着一个点 ‘.’ ，后面再跟着至少一位数字

   3. 一个点 ‘.’ ，后面跟着至少一位数字

整数（按顺序）可以分成以下几个部分：

1. （可选）一个符号字符（‘+’ 或 ‘-’）
2. 至少一位数字

示例

部分数值列举如下：

[“+100”, “5e2”, “-123”, “3.1416”, “-1E-16”, “0123”]
部分非数值列举如下：

[“12e”, “1a3.14”, “1.2.3”, “±5”, “12e+5.4”]

算法思路

合法的数值表达式由以下四部分组成

定义好0-8九种状态，然后根据合法的数值结构，画出状态转移图，接下来对照编写代码即可

注意只有状态2、3、7、8是合法的结尾状态。

代码

class Solution {
public:
    bool isNumber(string s) {
        vector<unordered_map<char, int>> state = {
            {{' ', 0}, {'s', 1}, {'.', 4}, {'d', 2}},
            {{'d', 2}, {'.', 4}},
            {{'d', 2}, {'.', 3}, {'e', 5}, {' ', 8}},
            {{'d', 3}, {' ', 8}, {'e', 5}},
            {{'d', 3}},
            {{'s', 6}, {'d', 7}},
            {{'d', 7}},
            {{'d', 7}, {' ', 8}},
            {{' ', 8}}
        };
        // 默认起始状态为 0
        int p = 0;
        for (auto ch : s) {
            // 处理字符代表的转移条件
            if (ch == 'e' || ch == 'E') ch = 'e'; // 幂符号用'e'表示
            else if (ch >= '0' && ch <= '9') ch = 'd'; // 数字用'd'表示
            else if (ch == '-' || ch == '+') ch = 's'; // 正负号用's'表示
            // '.' ' ' dot 和space 用自身表示即可
            
            // 判断当前状态下，转移条件是否合法
            if (!state[p].count(ch)) return false;
            // 进行状态转移
            p = state[p][ch];
        }
        // 到字符串末尾，只有状态2、3、7、8是合法的出口状态
        return p == 2 || p == 3 || p == 7 || p == 8;
    }
};

8. 字符串转换整数 (atoi)

问题描述

请你来实现一个 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$ 。
  返回整数作为最终结果。

注意：

本题中的空白字符只包括空格字符 ’ ’ 。
除前导空格或数字后的其余字符串外，请勿忽略 任何其他字符。

示例

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

输入：s = "-91283472332"
输出：-2147483648（INT_MIN）

输入：s = "4193 with words"
输出：4193

算法思路

代码

class Solution {
public:
    int myAtoi(string s) {
        // DFA
        vector<unordered_map<char, int>> state = {
            {{' ', 0}, {'s', 1}, {'d', 2}, {'?', 3}},
            {{'s', 3}, {'d', 2}, {' ', 3}, {'?', 3}},
            {{'d', 2}, {'s', 3}, {' ', 3}, {'?', 3}}
        };
        
        //
        char ch;
        bool isNeg = false;
        int pos = 0;
        int ans = 0;
        long tmp;
        for (int i = 0; i < s.size(); ++ i) {
            if (isdigit(s[i])) ch = 'd';
            else if (s[i] == '-' || s[i] == '+') ch = 's'; 
            else if (s[i] == ' ') ch = ' ';
            else ch = '?';

            pos = state[pos][ch];
            if (pos == 3) break;
            if (pos == 1) { // 到状态1，判断正负
                isNeg = s[i] == '-' ? true : false;
            } 
            if (pos == 2) {
                // 到状态2，计算数值
                // 以下是避免使用long型变量的 溢出判断语句
                if ((INT_MAX - (s[i] - '0')) / 10 < ans) {
                    if (isNeg) return INT_MIN;
                    else return INT_MAX;
                }
                ans = ans * 10 + (s[i] - '0'); // 推荐使用此种方式进行计算
            }
        }
      
        return isNeg ? -ans : ans;
    }
};

附一次遍历方案（此题复杂度不够，没必要用DFA）

class Solution {
public:
    int myAtoi(string s) {
        int sign = 1;
        int i = 0;
        // 丢弃无用的空格
        for (; i < s.size(); ++ i) {
            if (s[i] != ' ') break;
        }
        if (s[i] == '-') sign = -1; 
        // 用来判断类似"  .123"这样的case，首有效字符非正负号也非数字，直接返回0
        if (!isdigit(s[i]) && s[i] != '-' && s[i] != '+') return 0;
        int ans = 0;
        int start = i;
        for (int i = start; i < s.size(); ++ i) {
            if (i > start && !isdigit(s[i])) break; // 数字字符部分结束
            if (i == start && !isdigit(s[i])) continue; // 跳过正负符号位
            if ((INT_MAX - (s[i] - '0')) / 10 < ans) { // 判断加上当前数位后,是否会超出INT_MAX
                // 若超出，直接返回INT_MAX 或者INT_MIN
                if (sign == 1) return INT_MAX;
                else return INT_MIN;
            }
            ans = ans * 10 + (s[i] - '0');
        }
        return ans * sign;
    }
};