LeetCode-Valid Number - 有限状态机
判断合法数字,之前好像在哪里看到过这题,
记得当时还写了好久,反正各种改,
今天看到了大神的解法(https://github.com/fuwutu/LeetCode/blob/master/Valid%20Number.cpp),
用有限状态机,非常简洁,不需要复杂的各种判断!
先枚举一下各种合法的输入情况:
1.空格+ 数字 +空格
2.空格+ 点 + 数字 +空格
3.空格+ 符号 + 数字 + 空格
4.空格 + 符号 + 点 + 数字 +空格
5.空格 + (1, 2, 3, 4) + e + (1, 2, 3, 4) +空格
组后合法的字符可以是:
1.数字
2.空格
有限状态机的状态转移过程:
起始为0:
当输入空格时,状态仍为0,
输入为符号时,状态转为3,3的转换和0是一样的,除了不能再接受符号,故在0的状态的基础上,把接受符号置为-1;
当输入为数字时,状态转为1, 状态1的转换在于无法再接受符号,可以接受空格,数字,点,指数;状态1为合法的结束状态;
当输入为点时,状态转为2,状态2必须再接受数字,接受其他均为非法;
当输入为指数时,非法;
状态1:
接受数字时仍转为状态1,
接受点时,转为状态4,可以接受空格,数字,指数,状态4为合法的结束状态,
接受指数时,转为状态5,可以接受符号,数字,不能再接受点,因为指数必须为整数,而且必须再接受数字;
状态2:
接受数字转为状态4;
状态3:
和0一样,只是不能接受符号;
状态4:
接受空格,合法接受;
接受数字,仍为状态4;
接受指数,转为状态5,
状态5:
接受符号,转为状态6,状态6和状态5一样,只是不能再接受符号,
接受数字,转为状态7,状态7只能接受空格或数字;状态7为合法的结束状态;
状态6:
只能接受数字,转为状态7;
状态7:
接受空格,转为状态8,状态7为合法的结束状态;
接受数字,仍为状态7;
状态8:
接受空格,转为状态8,状态8为合法的结束状态;
1 class Solution
2 {
3 public:
4 bool isNumber(const char *s)
5 {
6 enum InputType
7 {
8 INVALID, // 0
9 SPACE, // 1
10 SIGN, // 2
11 DIGIT, // 3
12 DOT, // 4
13 EXPONENT, // 5
14 NUM_INPUTS // 6
15 };
16
17 int transitionTable[][NUM_INPUTS] =
18 {
19 -1, 0, 3, 1, 2, -1, // next states for state 0
20 -1, 8, -1, 1, 4, 5, // next states for state 1
21 -1, -1, -1, 4, -1, -1, // next states for state 2
22 -1, -1, -1, 1, 2, -1, // next states for state 3
23 -1, 8, -1, 4, -1, 5, // next states for state 4
24 -1, -1, 6, 7, -1, -1, // next states for state 5
25 -1, -1, -1, 7, -1, -1, // next states for state 6
26 -1, 8, -1, 7, -1, -1, // next states for state 7
27 -1, 8, -1, -1, -1, -1, // next states for state 8
28 };
29
30 int state = 0;
31 while (*s != '\0')
32 {
33 InputType inputType = INVALID;
34 if (isspace(*s))
35 inputType = SPACE;
36 else if (*s == '+' || *s == '-')
37 inputType = SIGN;
38 else if (isdigit(*s))
39 inputType = DIGIT;
40 else if (*s == '.')
41 inputType = DOT;
42 else if (*s == 'e' || *s == 'E')
43 inputType = EXPONENT;
44
45 state = transitionTable[state][inputType];
46
47 if (state == -1)
48 return false;
49 else
50 ++s;
51 }
52
53 return state == 1 || state == 4 || state == 7 || state == 8;
54 }
55 };
最新文章
- MySQL监控系统MySQL MTOP的搭建(转VIII)
- POJ 3320 (尺取法+Hash)
- Spring 集成 Hibernate 和 Struts 2
- ios5 中文键盘高度变高覆盖现有ui问题的解决方案(获取键盘高度的方法)(转载)
- Linux SHELL脚本
- linux0.12 学习总序(不断更新状态中)
- css3动画之animate
- 平衡工作与生活的艺术——GTD简单介绍
- iOS中UITextField 使用全面解析 分类: ios技术 2015-04-10 14:37 153人阅读 评论(0) 收藏
- sqlserver修改增删改字段
- Carthage的安装和使用
- 【翻译】A Next-Generation Smart Contract and Decentralized Application Platform
- shell脚本-2
- app微信支付-java服务端接口 支付-查询-退款
- 分析轮子(二)- <;<; ,>;>;,>;>; (左移、右移、无符号右移)
- Python 中 and 和 or 的短路原则
- JS/Jquery版本的俄罗斯方块(附源码分析)
- ImageView setImageURI图片不改变\NetWorkImageView 不显示的问题
- extjs的使用笔记2
- HDU 4818 Golden Radio Base (2013长春现场赛B题)
热门文章
- 阅读c#程序——回答问题
- 3D 立体 backface-visibility
- Redis 总结精讲
- bootstrap响应式布局列子
- jsonp 接口
- css文本垂直居中
- hexo d 报错‘fatal: could not read Username for &#39;https://github.com&#39;: No error’
- Windows 64位环境的Java 服务配置
- Java 策略模式(Strategy)
- 去除百度搜索结果中的广告的 js 代码