您现在的位置是：首页 > Python

当前栏目

[Leetcode][python]Valid Number

输入状态

2023-03-02 11:13:04 时间

## 题目大意 ##

判断一个字符串是否是数值类型

## 解题思路 ##

该题差评无数，但绝对是一个好题目。最优雅的解法是**有限状态机**，我的脑海中浮现了以前上课时候学的有限状态机知识，所以这题其实思路一目了然！  
参考：  
[http://www.cnblogs.com/zuoyuan/p/3703075.html][http_www.cnblogs.com_zuoyuan_p_3703075.html]

首先这个题有9种状态：

0初始无输入或者只有space的状态  
1输入了数字之后的状态  
2前面无数字，只输入了dot的状态  
3输入了符号状态  
4前面有数字和有dot的状态  
5’e’ or ‘E’输入后的状态  
6输入e之后输入Sign的状态  
7输入e后输入数字的状态  
8前面有有效数输入之后，输入space的状态

共9种状态了，难设计的是6,7,8状态。

分好之后就好办了，设计出根据输入进行状态转换就OK了。

这里的输入可以分：

INVALID=0;\#无效输入包括: Alphas, ‘(‘, ‘&’ ans so on  
SPACE=1  
SIGN=2 \# ‘+’ or ‘-’  
DIGIT=3 \# numbers  
DOT=4 \# ‘.’  
EXPONENT=5 \# ‘e’ or ‘E’

行代表了9种状态，列代表了6种输入方式也就是6种跳转方式。举个例子：A\[0\]\[2\]=3，这有什么含义呢？意思是：第0种状态为【0初始无输入或者只有space的状态】，在输入第2种输入【SIGN=2 \# ‘+’ or ‘-‘】后，会跳转到第3种状态【3输入了符号状态】。A\[1\]\[1\]=8是什么意思呢？意思是：第1种状态为【1输入了数字之后的状态】，在输入第1种输入【SPACE=1】后，跳转到了第8种状态【8前面有有效数输入之后，输入space的状态】。

![这里写图片描述][012016243309923.png]

## 代码 ##

class Solution(object):
        def isNumber(self, s):
            """
            :type s: str
            :rtype: bool
            """
            INVALID=0; SPACE=1; SIGN=2; DIGIT=3; DOT=4; EXPONENT=5;
            #0invalid,1space,2sign,3digit,4dot,5exponent,6num_inputs
            transitionTable=[[-1,  0,  3,  1,  2, -1],    #0 no input or just spaces 
                             [-1,  8, -1,  1,  4,  5],    #1 input is digits 
                             [-1, -1, -1,  4, -1, -1],    #2 no digits in front just Dot 
                             [-1, -1, -1,  1,  2, -1],    #3 sign 
                             [-1,  8, -1,  4, -1,  5],    #4 digits and dot in front 
                             [-1, -1,  6,  7, -1, -1],    #5 input 'e' or 'E' 
                             [-1, -1, -1,  7, -1, -1],    #6 after 'e' input sign 
                             [-1,  8, -1,  7, -1, -1],    #7 after 'e' input digits 
                             [-1,  8, -1, -1, -1, -1]]    #8 after valid input input space
            state=0; i=0
            while i<len(s):
                inputtype = INVALID
                if s[i]==' ': inputtype=SPACE
                elif s[i]=='-' or s[i]=='+': inputtype=SIGN
                elif s[i] in '0123456789': inputtype=DIGIT
                elif s[i]=='.': inputtype=DOT
                elif s[i]=='e' or s[i]=='E': inputtype=EXPONENT
    
                state=transitionTable[state][inputtype]
                if state==-1: return False
                else: i+=1
            return state == 1 or state == 4 or state == 7 or state == 8

## 总结 ##

感慨下，我认为公司笔试题很有可能会有这种有限状态机知识的题目，毕竟可以考察好几门学科知识～

[http_www.cnblogs.com_zuoyuan_p_3703075.html]: http://www.cnblogs.com/zuoyuan/p/3703075.html
[012016243309923.png]: /images/20220607/4423969c9ac34256ae61c2d8989f8677.png

猜你喜欢

最长无重复子串
写技术博客的一些心得分享
Java 多线程（七）：线程池
Java 多线程（五）：锁（三）
Java 多线程（四）：锁（二）
Java 多线程（三）：锁（一）
Java 多线程（二）：并发编程的三大特性
线性时间非比较类排序
Java 多线程（一）：基础
合并k个已排序的链表
HDFS 高可用分布式环境搭建
合并两个有序数组
连续子数组的最大和
HDFS 分布式环境搭建
容器盛水问题
大数加法
HDFS 伪分布式环境搭建
设计LRU缓存结构
两数之和
使用单调栈来解决的一些问题

zl程序教程

当前栏目

[Leetcode][python]Valid Number

相关文章