LCR 138. 有效数字

力扣题目：https://leetcode.cn/problems/biao-shi-shu-zhi-de-zi-fu-chuan-lcof/description/?envType=study-plan-v2&envId=coding-interviews

这个题目要求给定一个字符串，然后判断是否符合对应的规则要求，其实如果能够手搓正则表达式的话的确可以很快地进行完成。但是由于这是一道算法题，需要我们进行手动的实现，那么就不得不了解正则表达式的底层原理—有限状态机了。

前置知识简述

关于有限状态机 有限状态机的详细概念请见：https://oi-wiki.org/misc/fsm/，这里我们只做简单的理解，应用场景仅和正则表达式一致。

简单理解就是，对于给定的一系列输入，我们有一套定义好的状态和对应的操作可以进行变化。 比如，我们定义初始状态是s0，当输入为1时候，状态还是s0，而当输入为0时候，状态变成s1。 双圈表示，如果所有输入结束的时候，当前的状态是我们接受的（想要的目的状态）。除此之外，如果出现了不能让状态有效变化的输入（比如5就不发生变化）和结果为不接受的状态，那么就都认为是不符合我们想要的结果。

这个有限状态机的功能就可以用来判断一个数字是不是以10的倍数。

因此，关键在于我们想要定义的状态 和 状态的变化条件 是怎样的，这也就决定了我们的有限状态机可以用来判断是什么样的序列。

定义状态

这道题目判断给定字符串是否为一个有效数字，我们实际上就是从左到右输入多个字符，然后根据输入的字符是否符合给定有效数字的定义来返回结果。 已知的字符输入类型只有5种，其他的类型都试做不符合有效数字。 这里有效数字的定义也刚好是从左到右的顺序，所以我们可以按照有效数字的定义，整理出来一个有效数字字符串从左到右都是什么类型的字符，见图中的表格所示。 这里我们给定的表格是一个最长的有效数字，而我们需要定义在输入这个有效数字过程中，可能存在的中间状态。这更方便我们进行定义状态。 定义状态的原则就是一个条件判断过程，比如 从开始的空格开始，如果输入了一个符号的话就是" + “，那么这就代表其中的一个状态（下图的状态1）。如果下一个输入是数字，那么就会变成“+1”，这实际上代表一个整数。

题目中开始和结尾都是若干个空格，意思是如果没有也可以，如果连续输入都是空格也可以。同理，整数或者小数的数字位数也是可以连续输入的，所以要有从当前节点出发到当前节点的箭头。

下面的图是完整的状态以及对应遇到输入后转移的状态。

需要注意的是，在3这个状态下，实际上是因为原题对于小数的定义比较宽松，输入数字后输入小数点 / 输入小数点后输入数字/前两个再输入数字 这三个操作其实都对应了小数的状态，所以这里实际上我们是进行了一次状态的合并的操作。

当我们画完了这个有限状态图后，我们这个题目基本就做完了一大半了，剩下就是将其转换为代码。

定义状态数组

这里我们使用java举例，我们定义一个状态数组states，每个元素都是一个Hashmap对象，每个对象表示某个状态。我们使用这样的语句来定义状态的转移。我们预设好map的键值对为<输入的操作，转移的下一个状态>。

 new HashMap<>(Map.of('n',2,'.',4)),//状态1的 转移条件(key) 和 转移结果(value)

这里使用的是java 9+的map的of方法，其中连续地写k1,v1, k2,v2, k3,v3….。这里的<n,2>就表示输入为‘n’(我们用n表示输入字符为数字），那么就会转移到状态2。

因此我们维护的states数组就是这样的：

 Map[] states = {
                new HashMap<>(Map.of(' ',0,'s',1,'n',2,'.',4)),//0
                new HashMap<>(Map.of('n',2,'.',4)),//1
                new HashMap<>(Map.of('.',3,'e',5,'n',2,' ',8)),//2
                new HashMap<>(Map.of('n',3,' ',8,'e',5)),//3
                new HashMap<>(Map.of('n',3)),//4
                new HashMap<>(Map.of('s',6,'n',7)),//5
                new HashMap<>(Map.of('n',7)),//6
                new HashMap<>(Map.of(' ',8,'n',7)),//7
                new HashMap<>(Map.of(' ',8)),//8
        };

这个状态数组定义出来后，即便后面发现状态定义有问题也可以很方便地进行更改，比ifelse不知道方便了多少倍！

有限状态机的完整实现

一句话说就是：我们只需要定义一个全局变量p，p的初始状态就是状态0，然后使用for循环依次读取字符串中的字符，然后根据字符来进行状态的转移操作,也就是更新p的值，直到最终判断最终状态p是否是我们想要的状态（接受状态是双圈状态2/3/7/8）。

前面我们已经定义了状态数组和对应每个状态的转移操作，我们只需要在输入字符符合key的时候，获取对应key的value然后更新p值，就相当于完成了一次根据输入转移状态的操作。

public boolean validNumber(String s) {
//        空格 b 符号 s 数字 n  点 .  幂函数 e
        Map[] states = {
                new HashMap<>(Map.of(' ',0,'s',1,'n',2,'.',4)),//0
                new HashMap<>(Map.of('n',2,'.',4)),//1
                new HashMap<>(Map.of('.',3,'e',5,'n',2,' ',8)),//2
                new HashMap<>(Map.of('n',3,' ',8,'e',5)),//3
                new HashMap<>(Map.of('n',3)),//4
                new HashMap<>(Map.of('s',6,'n',7)),//5
                new HashMap<>(Map.of('n',7)),//6
                new HashMap<>(Map.of(' ',8,'n',7)),//7
                new HashMap<>(Map.of(' ',8)),//8
        };

        char[] chars = s.toCharArray();
        char t;
        int p =0;//初始状态
        for (int i = 0; i < chars.length; i++) {
            char ch = chars[i];
            if (ch=='+'||ch=='-') t = 's';//符号
            else if ((ch >= '0') && (ch <= '9')) t = 'n';//数字
            else if (ch=='E'||ch=='e') t = 'e'; //幂函数
            else if(ch==' '||ch=='.') t=ch;//直接用的符号
            else{ return false;}//非法字符输入
            //开始转移状态
            if (states[p].containsKey(t)){
                p = (int) states[p].get(t);
            }else {
                return false;
            }
        }
        if (p==2||p==3||p==7||p==8){
            return true;//接受的状态
        }
        return false;
    }