专栏首页蛮三刀的后端开发专栏[Leetcode][python]Valid Number

[Leetcode][python]Valid Number

题目大意

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

解题思路

该题差评无数,但绝对是一个好题目。最优雅的解法是有限状态机,我的脑海中浮现了以前上课时候学的有限状态机知识,所以这题其实思路一目了然! 参考: 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的状态】。

代码

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

总结

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Python学习笔记(五)——函数式编程

    成功!说明变量f现在已经指向了abs函数本身。直接调用abs()函数和调用变量f()完全相同。

    后端技术漫谈
  • [Leetcode][python]Insertion Sort List/对链表进行插入排序

    参考:http://www.cnblogs.com/zuoyuan/p/3700105.html

    后端技术漫谈
  • 【设计模式自习室】开篇:为什么要有设计模式?

    文章会逐步更新于我的各个博客上(见文章尾部介绍),也希望各位观众老爷能够关注我的个人公众号:后端技术漫谈,所有文章都会在上面发布,不会错过精彩好看的文章。

    后端技术漫谈
  • webstom设置和monokia配色方案

    首先,最后配色结果如下: ? 本次配色参考几个文档: http://frontenddev.org/article/webstorm-portal-1-subj...

    Ryan-Miao
  • 展开计算图与循环神经网络

    计算图是形式化一组计算结构的方式,如那些涉及将输入和参数映射到输出和损失计算。我们对展开(unfolding) 递归或循环计算得到的重复结构进行解释,这些重复结...

    企鹅号小编
  • Python-数据解析-职位信息-上

    爬取腾讯社会招聘网站的招聘信息,包括职位名称、职位类别、招聘人数、工作地点、发布时间、以及每个职位详情的链接。

    小团子
  • PyQt5--QSplitter

    py3study
  • <select>标签

    Html5知典
  • OAuth2.0与OAuth1.0你了解了吗?

    OAuth 协议简单的来说就是第三方应用在不知道我方用户账号密码的情况下,通过我们的授权,进行登录操作。它减少了用户注册的次数,方便用户快捷登录,提升用户体验度...

    小闫同学啊
  • H5新增的块级的语义元素

    figure元素表示一段独立的流内容,一般表示文档主体流内容的一个独立单元。使用<figcaption>元素为figure元素组添加标题。

    week

扫码关注云+社区

领取腾讯云代金券