打开上次浏览的网站模板,十大室内设计案例,山东网站开发网络公司,电子商务网站设计成功的要素文章目录一、问题来源二、题目描述三、题解中的自动机四、自动机学习五、有限状态机的使用场景一、问题来源 今天做力克题目的时候看到了字符串转换整数的一道算法题#xff0c;其中又看到了题解中有自动机的概念#xff0c;所以在这里对自动机做个笔记。题目链接 二、题目描…
文章目录一、问题来源二、题目描述三、题解中的自动机四、自动机学习五、有限状态机的使用场景一、问题来源 今天做力克题目的时候看到了字符串转换整数的一道算法题其中又看到了题解中有自动机的概念所以在这里对自动机做个笔记。题目链接 二、题目描述
请你来实现一个 myAtoi(string s) 函数使其能将字符串转换成一个 32 位有符号整数类似 C/C 中的 atoi 函数。函数 myAtoi(string s) 的算法如下
读入字符串并丢弃无用的前导空格检查下一个字符假设还未到字符末尾为正还是负号读取该字符如果有。 确定最终结果是负数还是正数。 如果两者都不存在则假定结果为正。读入下一个字符直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。将前面步骤读入的这些数字转换为整数即“123” - 123 “0032” - 32。如果没有读入数字则整数为 0 。必要时更改符号从步骤 2 开始。如果整数数超过 32 位有符号整数范围 [−231, 231 − 1] 需要截断这个整数使其保持在这个范围内。具体来说小于 −231 的整数应该被固定为 −231 大于 231 − 1 的整数应该被固定为 231 − 1 。返回整数作为最终结果。
注意
本题中的空白字符只包括空格字符 ’ ’ 。除前导空格或数字后的其余字符串外请勿忽略 任何其他字符。
示例 1 输入s “42” 输出42 解释加粗的字符串为已经读入的字符插入符号是当前读取的字符。 第 1 步“42”当前没有读入字符因为没有前导空格 第 2 步“42”当前没有读入字符因为这里不存在 ‘-’ 或者 ‘’ 第 3 步“42”读入 “42” 解析得到整数 42 。 由于 “42” 在范围 [-231, 231 - 1] 内最终结果为 42 。
示例 2 输入s -42 输出-42 解释 第 1 步 -42读入前导空格但忽视掉 第 2 步 -42读入 ‘-’ 字符所以结果应该是负数 第 3 步 -42读入 “42” 解析得到整数 -42 。 由于 “-42” 在范围 [-231, 231 - 1] 内最终结果为 -42 。
示例 3 输入s “4193 with words” 输出4193 解释 第 1 步“4193 with words”当前没有读入字符因为没有前导空格 第 2 步“4193 with words”当前没有读入字符因为这里不存在 ‘-’ 或者 ‘’ 解析得到整数 4193 。 由于 “4193” 在范围 [-231, 231 - 1] 内最终结果为 4193 。
三、题解中的自动机
思路
字符串处理的题目往往涉及复杂的流程以及条件情况如果直接上手写程序一不小心就会写出极其臃肿的代码。
因此为了有条理地分析每个输入字符的处理方法我们可以使用自动机这个概念
我们的程序在每个时刻有一个状态 s每次从序列中输入一个字符 c并根据字符 c 转移到下一个状态 s’。这样我们只需要建立一个覆盖所有情况的从 s 与 c 映射到 s’ 的表格即可解决题目中的问题。
算法 本题可以建立如下图所示的自动机 接下来编程部分就非常简单了我们只需要把上面这个状态转换表抄进代码即可
四、自动机学习
根据上述我们大概对自动机有一个初步的了解接下来就详细地学习一下自动机 自动机是有限状态机(FSM)的数学模型。
FSM 是给定符号输入依据(可表达为一个表格的)转移函数“跳转”过一系列状态的一种机器。在常见的 FSM 的“Mealy”变体中这个转移函数告诉自动机给定当前状态和当前字符的时候下一个状态是什么。
逐个读取输入中的符号直到被完全耗尽(把它当作有一个字写在其上的磁带通过自动机的读磁头来读取它磁头在磁带上前行移动一次读一个符号)。一旦输入被耗尽自动机被称为“停止”了。
依赖自动机停止时的状态称呼这个自动机要么是“接受”要么“拒绝”这个输入。如果停止于“接受状态”则自动机“接受”了这个字。在另一方面如果它停止于“拒绝状态”则这个字被“拒绝”。自动机接受的所有字的集合被称为“这个自动机接受的语言”。
自动机 automaton 原来是模仿人和动物的行动而做成的机器人的意思。但是现已被抽象化为如下的机器。时间是离散的t012……在每一个时刻它处于所存在的有限个内部状态中的一个。对每一个时刻给予有限个输入中的一个。那么下一个时刻的内部状态就由现在的输入和现在的内部状态所决定。每个时刻的输出只由那个时刻的内部状态所决定。
五、有限状态机的使用场景
有限状态机的写法逻辑清晰表达力强有利于封装事件。一个对象的状态越多、发生的事件越多就越适合采用有限状态机的写法。
