免费视频网站怎么赚钱,苏州聚尚网络科技有限公司,内蒙古自治区住房和城乡建设厅官网,网络管理系统怎么打开文章目录题目思路一代码一思路二代码二题目 思路一
考察有限状态自动机#xff08;参考jyd#xff09;#xff1a;
字符类型#xff1a; 空格 「 」、数字「 0—9 」 、正负号 「 」 、小数点 「 . 」 、幂符号 「 eE 」 。 状态定义#xff1a;
按照字符串从左到右的…
文章目录题目思路一代码一思路二代码二题目 思路一
考察有限状态自动机参考jyd
字符类型 空格 「 」、数字「 0—9 」 、正负号 「 ± 」 、小数点 「 . 」 、幂符号 「 eE 」 。 状态定义
按照字符串从左到右的顺序定义以下 9 种状态
开始的空格幂符号前的正负号小数点前的数字小数点、小数点后的数字当小数点前为空格时小数点、小数点后的数字幂符号幂符号后的正负号幂符号后的数字结尾的空格
结束状态
合法的结束状态有 2, 3, 7, 8 。 算法流程 初始化 状态转移表 maps 设 maps[i] 其中 i 为所处状态9种之一 maps[i] 使用哈希表存储可转移至的状态。键值对 (key, value) 含义若此时的字符是 key 则可从状态 i 转移至状态 value 。当前状态 p 起始状态初始化为 p 0 。 状态转移循环 遍历字符串 s 的每个字符 c 。 记录字符类型 t 分为四种情况。 当 c 为正负号时执行 t s ;当 c 为数字时执行 t d ;当 c 为 e , E 时执行 t e ;当 c 为 . , 空格 时执行 t c 即用字符本身表示字符类型;否则执行 t ‘?’ 代表为不属于判断范围的非法字符后续直接返回 false。 终止条件 若字符类型 t 不在哈希表 maps[p] 中说明无法转移至下一状态因此直接返回 False 。 状态转移 状态 p 转移至 maps[p][t] 。 返回值 跳出循环后若状态 p∈2,3,7,8 说明结尾合法返回 True 否则返回 False 。
再详细说一下状态转移表的作用下面代码部分的注释中有结合实例进行详解
处于第 i 行表明此时遍历到的字符是第 i1 种状态可以对照上文的状态定义那么我下一个字符可以是第 i 行中的各个 key 对应的字符。如果某字符没有写进第 i 行表示 i1 状态的下一个字符不应是某字符
复杂度分析
时间复杂度 O(N) 其中 N 为字符串 s 的长度判断需遍历字符串每轮状态转移的使用 O(1) 时间。空间复杂度 O(1) maps 和 p 使用常数大小的额外空间。
代码一
class Solution {
public:bool isNumber(string s) {vectormapchar,int maps {
// 状态转移表
// 以第一行为例状态转移表的含义为
// 开始的空格其下一个字符可以继续是空格也可以是符号、数字、小数点
// 但不可是第0行不存在的e。
// 也就是为了保证字符串是数值空格后面不能直接跟一个幂符号。{{ , 0}, {s, 1}, {d, 2}, {., 4}}, // 开始的空格{{d, 2}, {., 4}}, // 幂符号前的正负号{{d, 2}, {., 3}, {e, 5}, { , 8}}, // 小数点前的数字{{d, 3}, {e, 5}, { , 8}}, // 小数点、小数点后的数字{{d, 3}}, // 当小数点前为空格时小数点、小数点后的数字{{s, 6}, {d, 7}}, // 幂符号{{d, 7}}, // 幂符号后的正负号{{d, 7}, { , 8}}, // 幂符号后的数字{{ , 8}} // 结尾的空格};int p 0; //起始状态char t;for(char c : s) {if(c 0 c 9) t d;else if(c || c -) t s;else if(c e || c E) t e;else if(c . || c ) t c;else t ?;if(maps[p].find(t) maps[p].end()) return false;p maps[p][t];}return p 2 || p 3 || p 7 || p 8;}
};思路二
用 bool 类型变量 ret 存储搜索过程中的结果整个搜索过程如下
过滤首部空格过滤正负号紧接着检查是否有数字遇到第一个不是数字的字符应为 . 或者 e. 的后面可以有 e但 e 的后面不能有 . 所以先处理 . 再处理 e. 前面可以什么都没有后面也可以什么都没有只要有一边有数据就行e 的前后必须都要有数据并且后面可以存在正负号所以需要过滤正负号过滤尾部空格检查 ret 状态以及是否已经遍历完字符串
关于第8点检查是否已经遍历完字符串
因为如果字符串是数值尾部空格应该是字符串的末尾部分倒数几个字符空格完了字符串应该也就结束了。如果过滤完了尾部空格还有字符说明该字符串不是数值。
代码二
class Solution {
public:bool scanDigit(string s, int i){int count i;while(i ! s.size()){if(isdigit(s[i]))i;elsebreak;}return i count;//如果数据中没有一个数字则直接返回false有则返回true}bool scanSign(string s, int i){if(i s.size() s[i] || s[i] -){i;}//过滤正负号return scanDigit(s, i);}bool isNumber(string s) {if(s.empty())return false;int i 0;while(s[i] )i;//过滤首部空格bool ret scanSign(s, i);//第一遍搜索先走完.或者e前的所有数字//.的后面可以有e但e的后面不能有.,所以先处理.再处理eif(i s.size() s[i] .){ret scanDigit(s, i) || ret;//.前面可以什么都没有后面也可以什么都没有只要有一边有数据就行}if(i s.size() (s[i] e || s[i] E)){ret scanSign(s, i) ret;//e的前后必须都要有数据,并且e后面可以存在正负号所以需要过滤正负号}while(s[i] )i;//因为空格只能出现在末尾和首部过滤空格return ret (i s.size());//当e后面有数据并且字符串全部走完说明数据成立}
};
