[leetcode刷题笔记]有限自动机

有限自动机可分为确定的有限自动机(DFA)和不确定的有限自动机(BFA)。区别在于转移函数不同,DFA对每一个可能的输入只有一个状态的转移,BFA对每一个可能的输入可以有多个状态转移,接受到输入时从这多个状态转移中非确定地选择一个。在解答有限自动机问题时需构造状态转换图,确定起始状态和终止状态,问题便可以解决。

字符串转换整数 (atoi)

请你来实现一个 atoi 函数,使其能将字符串转换成整数。

首先,该函数会根据需要丢弃无用的开头空格字符,直到寻找到第一个非空格的字符为止。接下来的转化规则如下:

如果第一个非空字符为正或者负号时,则将该符号与之后面尽可能多的连续数字字符组合起来,形成一个有符号整数。
假如第一个非空字符是数字,则直接将其与之后连续的数字字符组合起来,形成一个整数。
该字符串在有效的整数部分之后也可能会存在多余的字符,那么这些字符可以被忽略,它们对函数不应该造成影响。
注意:假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时,则你的函数不需要进行转换,即无法进行有效转换。

在任何情况下,若函数不能进行有效的转换时,请返回 0 。

提示:

本题中的空白字符只包括空格字符 ' ' 。
假设我们的环境只能存储 32 位大小的有符号整数,那么其数值范围为 [−231, 231 − 1]。如果数值超过这个范围,请返回 INT_MAX (231 − 1) 或 INT_MIN (−231) 。

根据题构造状态转换图,其中b表示空格blank,d表示数字,c表示符号(+/-),?表示其它字符。

状态转换图

状态转换表如下:

- b c d ?
0 0 1 2 3
1 3 3 2 3
2 3 3 2 3

构造出状态转换表后,编程很简单,在本题中增加了对结果的判断,这个要注意。

class Solution:
  def myAtoi(self, s: str) -> int:
    state = [
        {'b':0,'c':1,'d':2,'?':3},# 0
        {'b':3,'c':3,'d':2,'?':3},# 1
        {'b':3,'c':3,'d':2,'?':3}# 2
    ]

    p,t = 0,''
    res,sign = 0,1
    for c in s:
        if '0'<=c<='9':t = 'd'
        elif c == ' ':t = 'b'
        elif c in '+-':t = 'c'
        else:t = '?'

        if t in state[p]:
            p = state[p][t]
            if p == 1:
                sign = 1 if c == '+' else -1
            if p == 2:
                res = res * 10 + ord(c) - ord('0')
            if p == 3:
                break 
    
    maxNumber,minNumber = 2**31 - 1,-2 ** 31
    
    res *= sign
    if res > maxNumber:res = maxNumber
    if res < minNumber:res = minNumber

    return res

表示数值的字符串

请实现一个函数用来判断字符串是否表示数值(包括整数和小数)。例如,字符串"+100"、"5e2"、"-123"、"3.1416"、"0123"都表示数值,但"12e"、"1a3.14"、"1.2.3"、"+-5"、"-1E-16"及"12e+5.4"都不是。

这一题可以看作是上一题的升级版,在于多了‘.’和‘e’两种转移方式,根据此题可以构造一个有限自动机,如图。

状态转换图

其中b表示空格blank,d表示数字,c表示符号(+/-)。根据有限自动机转移状态,判断最后是否结束。

- b d c . e
0 0 2 1 4 Φ
1 Φ 2 Φ 4 Φ
2 Φ 2 Φ Φ Φ
3 8 3 Φ Φ 5
4 Φ 3 Φ Φ Φ
5 Φ 7 6 Φ Φ
6 Φ 7 Φ Φ Φ
7 8 7 Φ Φ Φ
8 8 Φ Φ Φ Φ

如图构造状态转换表,接下来根据表编程。

class Solution:
  def isNumber(self, s: str) -> bool:

    # 有限自动机
    state = [
        {'b':0,'c':1,'d':2,'.':4},# 0
        {'d':2,'.':4},# 1
        {'d':2,'.':3,'b':8,'e':5},# 2
        {'d':3,'e':5,'b':8},# 3
        {'d':3},# 4
        {'c':6,'d':7},# 5
        {'d':7},# 6
        {'d':7,'b':8},# 7
        {'b':8}# 8
    ]

    p,t = 0,''
    for c in s:
        if '0'<=c<='9':t = 'd'
        elif c == ' ':t = 'b'
        elif c in '.e':t = c
        elif c in '+-':t = 'c'
        else:t = '?'

        if t in state[p]:p = state[p][t]
        else:return False
    
    # 判断是否终止
    return p in [2,3,7,8]

更多内容,后续补充。若有错误,欢迎指正批评。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 203,937评论 6 478
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 85,503评论 2 381
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 150,712评论 0 337
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 54,668评论 1 276
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 63,677评论 5 366
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,601评论 1 281
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 37,975评论 3 396
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,637评论 0 258
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 40,881评论 1 298
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,621评论 2 321
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,710评论 1 329
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,387评论 4 319
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 38,971评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,947评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,189评论 1 260
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 44,805评论 2 349
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,449评论 2 342