有效数字—状态机
不得不说,上海这几天的天气是真的有毒,时不时超级冷,还时不时下几滴雨,烦得很。最近临近期末,还有好多大作业啦,项目啦,小作业啦,各种实验啦,烦得不要不要的,整的我连看番的时间都快没了(⁎⁍̴̛ᴗ⁍̴̛⁎)~
今天呢,本科母校竟然又因为这种奇葩原因久居热搜,真的是服了网友们的“奇思妙想”,这迫击炮逮谁轰谁啊?又是烦心事 》**《
不说烦心事了,说点开心的,额,,今天刚打完一天工,又有小钱可以拿了,算嘛?不算的话,今天把部分作业搞完了?错!今天我又一次在不知觉中将自己的闹钟给关了(绝对定了的)!!这才是大事(本来是7.25的闹钟,8.30开工,结果,一觉睡醒8.30了,呵呵~)
今天呢,要讲的是昨天做的一道题,蛮有意思的,竟然和我本科学的编译原理扯上关系了,害我还去看了会本科知识(因为我本科编译原理学的贼差)
题目介绍
有效数字(按顺序)可以分成以下几个部分:
- 一个 小数 或者 整数
- (可选)一个 ‘e’ 或 ‘E’ ,后面跟着一个 整数
小数(按顺序)可以分成以下几个部分:
(可选)一个符号字符(’+’ 或 ‘-‘)
下述格式之一:
至少一位数字,后面跟着一个点 ‘.’
至少一位数字,后面跟着一个点 ‘.’ ,后面再跟着至少一位数字
一个点 ‘.’ ,后面跟着至少一位数字
整数(按顺序)可以分成以下几个部分:
- (可选)一个符号字符(’+’ 或 ‘-‘)
- 至少一位数字
我的思路
其实我的思路比较直接,相信我一说大家也都能懂
这道题无非就是给定有效数字的模式,需要我们自己去比对,因此我们可以按照以下几个步骤对给定的字符串s作出判断
首先判断s中是否包含非法字符,合法字符包括:0-9,+-号,小数点,E与e,其余的字符都可被认定为非法字符
接着判断s中是否包含E或者e,如果E或e的数量超过1,直接false,否则,借助E或e,将s划分,如果划分后,只有一个字符串,则只可能是E或e在结尾,返回false
划分后,判断前一个字符串是否为小数或者整数,判断后一个字符串是否为整数,如果都是,则true,反之,false
如果没有E或者e,则直接判断s是否为整数或者小数
相信明眼人已经看清重点在哪了,没错,关键在于如何判断一个字符串是否为整数或者小数呢?
整数判断:
首先判断开头是否为+或-,是的话,直接从第二位判断,不是的话直接从第一位判断,判断方式很直接,只要每一位字符都是0-9就可以。当然开始需要对s的length做出判断,如果长度为0肯定就直接false啦,如果只有一个+或-号自然也是false,代码如下,其中map是一个key为0-9,value为0的哈希表
1 | private Boolean isInteger(String s, Map<Character,Integer> map){ |
小数判断:
小数判断相对而言较为麻烦点,因为存在可能性会稍微有点多,相信大家对小数都很熟悉,我们以小数点为界,将字符串分为两部分,一般而言,只要前后两部分都是整数就是一个小数,不过这里需要做出一些额外的判断
小数点个数大于1直接false
分割后如果没有字符串,直接false(表示原本就一个小数点)
分割后如果只有一个字符串,表示小数点只能在结尾,这时,只需要判断分割后的那个字符串是否为整数即可(原因是split时,如果分割符在开头,则第一个分割出来的字符串是空串””)
如果是正常的两个字符串,也有多种情况:
第一个字符串:
第一个字符串是空串
第一个字符串是整数
第一个字符串是+或-
第二个字符串:
- 第二个字符串是整数,并且第一个字符不是+或-号
满足上述情况的两个字符串即可返回true,其余直接false
具体代码如下:
1 | private Boolean isFloat(String s, Map<Character,Integer> map){ |
好思路
利用有限状态自动机来进行解题,这是一种比较好的思路,具体的实现如下:
首先,我们需要根据题目的含义,将有效数字的所有可能性,以状态转换图的形式画出来,便于得到后续的状态转换表:
我相信各位大佬的理解能力应该都很强,关于这个图我就不细讲了,毕竟确实很容易理解(就是自己来画,蛮难的,编译原理没学好~)
额,要真的需要解释下的话,其实也没啥解释的,不就是一开始是个空的串,可以加入0-9数字,也可以一开始加入+或-号,其实就是构造一个有效数字的路径图
根据状态转换图可以得出下表:
state | blank | +/- | 0-9 | . | e/E | other |
---|---|---|---|---|---|---|
0 | 0 | 1 | 6 | 2 | -1 | -1 |
1 | -1 | -1 | 6 | 2 | -1 | -1 |
2 | -1 | -1 | 3 | -1 | -1 | -1 |
3 | -1 | -1 | 3 | -1 | 4 | -1 |
4 | -1 | 7 | 5 | -1 | -1 | -1 |
5 | -1 | -1 | 5 | -1 | -1 | -1 |
6 | -1 | -1 | 6 | 3 | 4 | -1 |
7 | -1 | -1 | 5 | -1 | -1 | -1 |
8 | 8 | -1 | -1 | -1 | -1 | -1 |
其中,状态8是用来处理字符串s结尾多余的的空格,因此所有终止态都必须跟上一个状态8,部分值为-1表示遇到一些不合法的字符(就是前面说的那些),直接返回false
具体代码如下:
1 | class Solution { |
注意:final的取值是有意义的,在上面的状态转换图中,我们可以得知:状态3,5,6,8可以作为正常的终止态,因此可以通过位操作来判断最终的状态是否在这几个选择中。具体上来说:final的值与1左移3位,1左移5位,1左移6位,1左移8位得到的是3,5,6,8;而其他的状态值与操作后都是0
结束
以上便是这道题的全部内容啦!给我留下印象最深的就是有限状态机在算法中竟然还可以这么使用,学到了~