LeetCode--剑指Offer75（3）

题目描述：剑指 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"]

LeetCode做题链接：LeetCode-表示数值的字符串

示例 1：

输入：s = "0"
输出：true

示例 2：

输入：s = "e"
输出：false

示例 3：

输入：s = "."
输出：false

示例 4：

输入：s = "    .1  "
输出：true

提示：

1 <= s.length <= 20
s 仅含英文字母（大写和小写），数字（0-9），加号 '+' ，减号 '-' ，空格 ' ' 或者点 '.' 。

题目接口

class Solution {
    public boolean isNumber(String s) {

    }
}

解题思路

参考题解：表示数值的字符串（有限状态自动机，清晰图解）

什么是有限状态自动机？

有限状态自动机的是指将有限状态自动机的模型转化为可执行的计算机程序的算法。它描述了如何根据有限状态自动机的定义和规则实现状态转移、状态判断和行为执行等功能。
通常情况下，有限状态自动机的编程算法包括以下几个主要步骤：

1.状态定义：根据实际需求，定义有限状态自动机的状态集合。每个状态可以用一个唯一的标识符或符号来表示。

2.输入定义：确定输入信号的集合。输入信号是触发状态转移的触发器，可以是字符、事件、条件等。

3.状态转移规则定义：根据状态和输入信号，定义状态之间的转移规则。规则描述了在特定状态下接收到特定输入信号时，系统应该转移到哪个状态。

4.状态转移函数实现：根据状态转移规则，实现状态转移函数。该函数接收当前状态和输入信号作为参数，并根据规则确定下一个状态。

5.状态判断：在每个状态转移后，根据当前状态和其他条件判断是否满足某些特定的状态条件。这些条件可以用于触发特定的行为或其他操作。

6.行为执行：根据当前状态和其他条件，执行相应的行为或操作。这些行为可以是输出、状态更新、操作等。
根据具体的编程语言和开发环境，有限状态自动机的编程算法可能会有所差异。在实际实现时，可以使用面向对象编程、状态模式等技术来组织和管理状态转移和行为执行的逻辑。
总之，有限状态自动机的编程算法将有限状态自动机的抽象模型转化为计算机可执行的程序，使得我们可以根据预定义的规则和条件来控制系统的行为。

如何使用？

主要难点在于定义所有的状态~
先定义状态，再画出状态转移图，最后编写代码

按照字符串从左到右的顺序，定义以下 9 种状态。

1.开始的空格
2.幂符号前的正负号
3.小数点前的数字
4.小数点、小数点后的数字
5.当小数点前为空格时，小数点、小数点后的数字
6.幂符号
7.幂符号后的正负号
8.幂符号后的数字
9.结尾的空格

在这里插入图片描述

代码

//小数表示可省去0，-0.4 = -.4，0.4 = .4；2.、3. = 2、3，小数点前有数，后面可以不跟数代表原数
//注意e8即10的8次幂（8次方），也可以是e-7，但题目要求必须跟整数
//题目规定是数值前后可有空格，中间不能有，这个情况要考虑清楚。s：符号、d：数字
class Solution {
    public boolean isNumber(String s) {
        Map[] states = {
            //0：规定0是初值，字符串表示数值，有4种起始状态，开头空格、符号、数字、前面没有数的小数点
            //其中 开头空格 还是指向states[0]，上一位是 开头空格，下一位可以是 空格、符号、数字、前面没有数的小数点
            new HashMap<>() {{ put(' ', 0); put('s', 1); put('d', 2); put('.', 4); }}, 
            //1：上一位是符号，符号位后面可以是 数字、前面没有数的小数点
            new HashMap<>() {{ put('d', 2); put('.', 4); }},
            //2：上一位是数字，数字的下一位可以是 数字、前面有数的小数点、e、结尾空格
            new HashMap<>() {{ put('d', 2); put('.', 3); put('e', 5); put(' ', 8); }}, 
            //3：上一位是前面有数的小数点，下一位可以是 数字、e（8.e2 = 8e2，和2的情况一样）、结尾空格
            new HashMap<>() {{ put('d', 3); put('e', 5); put(' ', 8); }},
            //4：上一位是前面没有数的小数点，下一位只能是 数字（符号肯定不行，e得前面有数才行）              
            new HashMap<>() {{ put('d', 3); }},
            //5：上一位是e，下一位可以是 符号、数字
            new HashMap<>() {{ put('s', 6); put('d', 7); }},
            //6：：上一位是e后面的符号，下一位只能是 数字
            new HashMap<>() {{ put('d', 7); }},
            //7：上一位是e后面的数字，下一位可以是 数字、结尾空格
            new HashMap<>() {{ put('d', 7); put(' ', 8); }},
            //8：上一位是结尾空格，下一位只能是 结尾空格
            new HashMap<>() {{ put(' ', 8); }}
        };
        int p = 0;
        char t;
        //遍历字符串，每个字符匹配对应属性并用t标记，非法字符标记？
        for(char c : s.toCharArray()) {
            if(c >= '0' && c <= '9') t = 'd';
            else if(c == '+' || c == '-') t = 's';
            else if(c == 'e' || c == 'E') t = 'e';
            else if(c == '.' || c == ' ') t = c;
            else t = '?';
            //当前字符标记和任何一种当前规定格式都不匹配，直接返回false
            if(!states[p].containsKey(t)) return false;
            //更新当前字符的规定格式，进入下一个规定的Map数组
            p = (int)states[p].get(t);
        }
        //2（正、负整数）、3（正、负小数）、7（科学计数法!）、8（前三种形式的结尾加上空格）
        //只有这四种才是正确的结尾
        return p == 2 || p == 3 || p == 7 || p == 8;
    }
}