首页 > 代码库 > leetcode-valid number ZZ
leetcode-valid number ZZ
http://blog.csdn.net/kenden23/article/details/18696083
本题是十分麻烦的题目，情况是非常多，网上也很多方法，其中最有效，优雅的方法是有限状态自动机(Finite automata machine)。其他一般方法都会十分复杂，而代码不能算优雅。为此我也曾经专门修了一个automata的知识。
只要设计好Finite Automata Machine之后，写程序就可以很优雅，很简单了。
但是，问题是要构造一个Finite Automata也是十分麻烦的事情，我画了一张A4纸，像蜘蛛网一样的，故此就不贴出来了，也搞了一两个小时，要多练练automata才能快起来吧
注释一下本题分多少状态吧：
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 Include: Alphas, ‘(‘, ‘&‘ ans so on
SPACE, // 1
SIGN, // 2 ‘+‘,‘-‘
DIGIT, // 3 numbers
DOT, // 4 ‘.‘
EXPONENT, // 5 ‘e‘ ‘E‘
然后就是画蜘蛛网吧，什么状态可以转换到什么状态的。
下面代码也注释出来了，参照了Leetcode论坛上的代码写的：
1 class Solution { 2 public: 3 bool isNumber(const char *s) { 4 enum InputType { 5 INVALID, // 0 Include: Alphas, ‘(‘, ‘&‘ ans so on 6 SPACE, // 1 7 SIGN, // 2 ‘+‘,‘-‘ 8 DIGIT, // 3 numbers 9 DOT, // 4 ‘.‘10 EXPONENT, // 5 ‘e‘ ‘E‘11 };12 int transTable[][6] = {13 //0INVA,1SPA,2SIG,3DI,4DO,5E14 -1, 0, 3, 1, 2, -1,//0初始无输入或者只有space的状态15 -1, 8, -1, 1, 4, 5,//1输入了数字之后的状态16 -1, -1, -1, 4, -1, -1,//2前面无数字，只输入了Dot的状态17 -1, -1, -1, 1, 2, -1,//3输入了符号状态18 -1, 8, -1, 4, -1, 5,//4前面有数字和有dot的状态19 -1, -1, 6, 7, -1, -1,//5‘e‘ or ‘E‘输入后的状态20 -1, -1, -1, 7, -1, -1,//6输入e之后输入Sign的状态21 -1, 8, -1, 7, -1, -1,//7输入e后输入数字的状态22 -1, 8, -1, -1, -1, -1,//8前面有有效数输入之后，输入space的状态23 };24 int state = 0;25 while (*s)26 {27 InputType input = INVALID;28 if (*s == ‘ ‘) input = SPACE;29 else if (*s == ‘+‘ || *s == ‘-‘) input = SIGN;30 else if (isdigit(*s)) input = DIGIT;31 else if (*s == ‘.‘) input = DOT;32 else if (*s == ‘e‘ || *s == ‘E‘) input = EXPONENT;33 state = transTable[state][input];34 if (state == -1) return false;35 ++s;36 }37 return state == 1 || state == 4 || state == 7 || state == 8;38 }39 };
leetcode-valid number ZZ
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。