由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - 用有限状态机写了一下leetcode valid number
相关主题
L二电面据,附面经问一个atoi overflow的问题
写了一下leetcode上Valid Number,用boolean表示一些状态是不是比较简单a[i] + b[j] = c[k] 的题有靠谱的答案不?
发现valid number真是必杀题秒杀valid number
ebay第一轮电话面经valid number这道题看到有人用有限状态机做 太牛不敢看
g面经来一个。你们说leetcode做了*遍,是所有题都做了吗?
leetcode valid numberLeetcode Valid Number
leetcode是不是最近有点问题?Search a 2D Matrix的两种写法,哪种更好?
L家电面一个面试题
相关话题的讨论汇总
话题: else话题: false话题: state话题: return话题: ncurstate
1 (共1页)
w****x
发帖数: 2483
1
/*Validate if a given string is numeric.
Some examples:
"0" => true
" 0.1 " => true
"abc" => false
"1 a" => false
"2e10" => true
*/
bool isNumber(const char *s) {

bool bIntNum = false;
int nCurState = 1;
while (true)
{
if (nCurState == 1)
{
while (*s == ' ')
s++;

if (*s == '+' || *s == '-')
s++;

if (*s >= '0' && *s <= '9')
{
while (*s >= '0' && *s <= '9')
s++;
bIntNum = true;
}
else
{
if (*s != '.') return false;
}

if (*s == '.')
{
nCurState = 2;
s++;
}
else if (*s == 'e')
{
nCurState = 3;
s++;
}
else
break;
}
else if (nCurState == 2)
{
if (*s >= '0' && *s <= '9')
{
while (*s >= '0' && *s <= '9')
s++;
}
else if (!bIntNum) return false;

if (*s == 'e')
{
nCurState = 3;
s++;
}
else break;
}
else
{
if (*s == '+' || *s == '-')
s++;

if (*s >= '0' && *s <= '9')
{
while (*s >= '0' && *s <= '9')
s++;
}
else return false;

break;
}
}

while (*s == ' ') s++;
return *s == 0;
}
=============================================
status 1 => 小数点前面的部分
status 2 => 小数点后到'e'前面的部分
status 3 => e后面的科学计数法部分
隐含的最后一个status => break 出while loop后的只允许空格的部分
n******n
发帖数: 567
2
leetcode还是加点题吧,这都被人玩出花了
j*****y
发帖数: 1071
3
最好是加些 graph方面的题目。

【在 n******n 的大作中提到】
: leetcode还是加点题吧,这都被人玩出花了
j*****y
发帖数: 1071
4
好厉害,学一下

【在 w****x 的大作中提到】
: /*Validate if a given string is numeric.
: Some examples:
: "0" => true
: " 0.1 " => true
: "abc" => false
: "1 a" => false
: "2e10" => true
: */
: bool isNumber(const char *s) {
:

p*****2
发帖数: 21240
5

graph不太好加。

【在 j*****y 的大作中提到】
: 最好是加些 graph方面的题目。
j*****y
发帖数: 1071
6
用 adjecency-list 或者 adjecency-matrix 产生 input. 其他的也没什么不一样的地
方吧?

【在 p*****2 的大作中提到】
:
: graph不太好加。

p*****2
发帖数: 21240
7

常见的graph的题有哪些呢?

【在 j*****y 的大作中提到】
: 用 adjecency-list 或者 adjecency-matrix 产生 input. 其他的也没什么不一样的地
: 方吧?

j*****y
发帖数: 1071
8
至少可以 把 dfs, bfs, topological sort, 这些过一遍吧?

【在 p*****2 的大作中提到】
:
: 常见的graph的题有哪些呢?

n******n
发帖数: 567
9
觉得不用加难的吧,就把150题或稍低难度的基础题加一下
t****a
发帖数: 1212
10
这题用有限状态机确实是蛮漂亮的解法啊。
不过呢,要把程序再弄漂亮一些的话,可以在外部文件中或者常量里定义个规则来表示
状态转移图,然后主程序解析这个状态转移输入图,这样就不用hard code规则了,程
序也比较好维护。

【在 w****x 的大作中提到】
: /*Validate if a given string is numeric.
: Some examples:
: "0" => true
: " 0.1 " => true
: "abc" => false
: "1 a" => false
: "2e10" => true
: */
: bool isNumber(const char *s) {
:

相关主题
leetcode valid number问一个atoi overflow的问题
leetcode是不是最近有点问题?a[i] + b[j] = c[k] 的题有靠谱的答案不?
L家电面秒杀valid number
n******n
发帖数: 567
11
LZ......其实自动机不是这么写的,你可以搜一下正规的写法。我当初面hulu就是这道
题,我也是这么写的,最好被灭了
f*****e
发帖数: 2992
12
二维数组?

【在 n******n 的大作中提到】
: LZ......其实自动机不是这么写的,你可以搜一下正规的写法。我当初面hulu就是这道
: 题,我也是这么写的,最好被灭了

l*******b
发帖数: 2586
13
搭车问有限机处理string match. Match 任意多个任意字符的*不难处理。可是单个字
符的?貌似没办法啊

【在 n******n 的大作中提到】
: LZ......其实自动机不是这么写的,你可以搜一下正规的写法。我当初面hulu就是这道
: 题,我也是这么写的,最好被灭了

w****x
发帖数: 2483
14

被灭的原因应该不是这个吧, 这题基本算是我见过最麻烦的题了。
我也不大清楚state machine的标准写法, 大致意思意思。
谁给个更简洁的state machine的解法?

【在 n******n 的大作中提到】
: LZ......其实自动机不是这么写的,你可以搜一下正规的写法。我当初面hulu就是这道
: 题,我也是这么写的,最好被灭了

l*******b
发帖数: 2586
15
写成state machine得有7种状态,5种字符,还不能handle + -空格。。。
val table = Array(Array(0,0,0,0,0), // 0 false
Array(0,2,0,0,7), // 1 numbers eof
Array(0,2,3,5,7), // 2 numbers e . eof
Array(0,4,0,0,0), // 3 numbers
Array(0,4,0,5,7), // 4 numbers e eof
Array(0,6,0,0,0), // 5 numbers
Array(0,6,0,0,7), // 6 numbers eof
Array(7,7,7,7,7)) // 7 true
def isNumber(s: String) = {
def isNumber_helper(index: Int, stat: Int) :Boolean = {
val typeOfChar = {
if(index > s.length - 1) 4 // eof
else {
val c = s(index)
if(c <= '9' && c >= '0') 1 // number
else if(c == '.') 2 // .
else if(c == 'e') 3 // e
else 0
}
}
if(stat == 7) true
else if(stat == 0) false
else isNumber_helper(index + 1, table(stat)(typeOfChar))
}
isNumber_helper(0,1)
}
val v = "123.456e8"
val test = isNumber(v)

【在 w****x 的大作中提到】
:
: 被灭的原因应该不是这个吧, 这题基本算是我见过最麻烦的题了。
: 我也不大清楚state machine的标准写法, 大致意思意思。
: 谁给个更简洁的state machine的解法?

w****x
发帖数: 2483
16

大牛能不能用C++再写个能过OJ的版本给我参考一下?
http://www.leetcode.com/onlinejudge
搜valid number

【在 l*******b 的大作中提到】
: 写成state machine得有7种状态,5种字符,还不能handle + -空格。。。
: val table = Array(Array(0,0,0,0,0), // 0 false
: Array(0,2,0,0,7), // 1 numbers eof
: Array(0,2,3,5,7), // 2 numbers e . eof
: Array(0,4,0,0,0), // 3 numbers
: Array(0,4,0,5,7), // 4 numbers e eof
: Array(0,6,0,0,0), // 5 numbers
: Array(0,6,0,0,7), // 6 numbers eof
: Array(7,7,7,7,7)) // 7 true
: def isNumber(s: String) = {

l*******b
发帖数: 2586
17
等我写个,属于OJ上剩下几个正在发愁的题目之一

【在 w****x 的大作中提到】
:
: 大牛能不能用C++再写个能过OJ的版本给我参考一下?
: http://www.leetcode.com/onlinejudge
: 搜valid number

t*********h
发帖数: 941
18
这题得把dfa画出来在编程吧

【在 l*******b 的大作中提到】
: 写成state machine得有7种状态,5种字符,还不能handle + -空格。。。
: val table = Array(Array(0,0,0,0,0), // 0 false
: Array(0,2,0,0,7), // 1 numbers eof
: Array(0,2,3,5,7), // 2 numbers e . eof
: Array(0,4,0,0,0), // 3 numbers
: Array(0,4,0,5,7), // 4 numbers e eof
: Array(0,6,0,0,0), // 5 numbers
: Array(0,6,0,0,7), // 6 numbers eof
: Array(7,7,7,7,7)) // 7 true
: def isNumber(s: String) = {

l*******b
发帖数: 2586
19
经过很久挣扎终于调成功了。。。test case好诡异
#include
using namespace std;
class Play {
public:
bool isNumber(const char *s) {
int mat[11][7] = {0 ,0 ,0 ,0 ,0 ,0 ,0, // false
0 ,2 ,3 ,0 ,1 ,4 ,0, // 1
0 ,2 ,5 ,6 ,9 ,0 ,10,// 2
0 ,5 ,0 ,0 ,0 ,0 ,0, // 3
0 ,2 ,3 ,0 ,0 ,0 ,0, // 4
0 ,5 ,0 ,6 ,9 ,0 ,10,// 5
0 ,7 ,0 ,0 ,0 ,8 ,0, // 6
0 ,7 ,0 ,0 ,9 ,0 ,10,// 7
0 ,7 ,0 ,0 ,0 ,0 ,0, // 8
0 ,0 ,0 ,0 ,9 ,0 ,10,// 9
10,10,10,10,10,10,10 // 10
};
int i = 0;
int stat = 1;
while(s[i] != 0) {
int type = 0;
if(s[i] >= '0' && s[i] <= '9')
type = 1;
else if(s[i] == '.')
type = 2;
else if(s[i] == 'e')
type = 3;
else if(s[i] == ' ')
type = 4;
else if(s[i] == '+' || s[i] == '-')
type = 5;
if(stat == 0)
return false;
stat = mat[stat][type];
i++;
}
stat = mat[stat][6];
if(stat == 10)
return true;
else
return false;
}
};
int main() {
Play pp;
string s;
while(cin >> s) {
if(pp.isNumber(s.c_str()))
cout << "YES !" << endl;
else
cout << "NO !" << endl;
}
return 0;
}

【在 t*********h 的大作中提到】
: 这题得把dfa画出来在编程吧
t*********h
发帖数: 941
20
牛鼻 你那个matrix啥含义能不能说说

【在 l*******b 的大作中提到】
: 经过很久挣扎终于调成功了。。。test case好诡异
: #include
: using namespace std;
: class Play {
: public:
: bool isNumber(const char *s) {
: int mat[11][7] = {0 ,0 ,0 ,0 ,0 ,0 ,0, // false
: 0 ,2 ,3 ,0 ,1 ,4 ,0, // 1
: 0 ,2 ,5 ,6 ,9 ,0 ,10,// 2
: 0 ,5 ,0 ,0 ,0 ,0 ,0, // 3

相关主题
valid number这道题看到有人用有限状态机做 太牛不敢看Search a 2D Matrix的两种写法,哪种更好?
你们说leetcode做了*遍,是所有题都做了吗?一个面试题
Leetcode Valid Number贡献今天facebook电面 一道题
l*******b
发帖数: 2586
21
1: 第一个字符,可能是 number . space sign
2: 读取一个数字但未读取 . 的时候,下一个字符可以是 number . e space eof
读取到number保持状态
读取到 . 进入 5
读取到e 进入 6
读取到 space 或者 eof结尾
3: 读取到一个 . 而且之前没有读到数字,此时下一个字符必须为数字
4: 读取到第一个字符为 sign 下一个字符可以是 . 或者number,规约到情形2,3
5: 读取到一个 . 以后下一个字符可以是number e space
下一个如果是number, 则状态保持,读到e则进入下一阶段 6,读到space就扫结尾
9
6: e 已经读取,下一个可以是number sign
是number则进入 7 再下一个为number 或者space进入9扫描结尾
是sign 则必须进入 8 再读取一个数字,然后规约到 7
9: 扫描结尾的 space

【在 t*********h 的大作中提到】
: 牛鼻 你那个matrix啥含义能不能说说
w****x
发帖数: 2483
22

滔滔江水啊, 过OJ了吧

【在 l*******b 的大作中提到】
: 经过很久挣扎终于调成功了。。。test case好诡异
: #include
: using namespace std;
: class Play {
: public:
: bool isNumber(const char *s) {
: int mat[11][7] = {0 ,0 ,0 ,0 ,0 ,0 ,0, // false
: 0 ,2 ,3 ,0 ,1 ,4 ,0, // 1
: 0 ,2 ,5 ,6 ,9 ,0 ,10,// 2
: 0 ,5 ,0 ,0 ,0 ,0 ,0, // 3

l*******b
发帖数: 2586
23
过了

【在 w****x 的大作中提到】
:
: 滔滔江水啊, 过OJ了吧

l*******b
发帖数: 2586
24
这个题化成regular expression再用general的方法解灵不灵啊,搜到一个写法
^[-+]?[0-9]*\.?[0-9]*([eE][-+]?[0-9]+)?$
match regular expression
j*****y
发帖数: 1071
25
大牛太厉害了。
可不可以把那个 roman to integer 和 integer to roman的也用有限状态机 写个简
单点的?

【在 l*******b 的大作中提到】
: 过了
d******e
发帖数: 164
26
bool isNumber(const char *s) {
while (isspace(*s)) s++;
if (*s == '+' || *s == '-') s++;
bool num = false;
while (isdigit(*s)) {
s++;
num = true;
}
if (*s == '.') {
s++;
while (isdigit(*s)) {
s++;
num = true;
}
}
if (*s == 'e') {
if (!num) return false;
s++;
if (*s == '+' || *s == '-') s++;
num = false;
while (isdigit(*s)) {
s++;
num = true;
}
}
while (isspace(*s)) s++;
if (!*s) return num;
return false;
}

【在 w****x 的大作中提到】
: /*Validate if a given string is numeric.
: Some examples:
: "0" => true
: " 0.1 " => true
: "abc" => false
: "1 a" => false
: "2e10" => true
: */
: bool isNumber(const char *s) {
:

s*******y
发帖数: 44
27
低调哥这个是我见过最简洁的code了。
我也用有限状态机写了一个,画状态机麻烦,code倒是不难写,就是比较繁琐。
bool isNumber(const char *s) {
int state = 0;
while (*s) {
switch (state) {
case 0:
if (*s == ' ') state = 0;
else if (*s == '+' || *s == '-') state = 11;
else if (isdigit(*s)) state = 21;
else if (*s == '.') state = 1;
else return false;
break;
case 1:
if (isdigit(*s)) state = 22;
else return false;
break;
case 11:
if (*s == '.') state = 1;
else if (isdigit(*s)) state = 24;
else return false;
break;
case 21:
if (isdigit(*s)) state = 21;
else if (*s == 'e') state = 3;
else if (*s == '.') state = 22;
else if (*s == ' ') state = 6;
else return false;
break;
case 22:
if (isdigit(*s)) state = 23;
else if (*s == 'e') state = 3;
else if (*s == ' ') state = 6;
else return false;
break;
case 23:
if (isdigit(*s)) state = 23;
else if (*s == 'e') state = 3;
else if (*s == ' ') state = 6;
else return false;
break;
case 24:
if (isdigit(*s)) state = 24;
else if (*s == '.') state = 22;
else if (*s == 'e') state = 3;
else if (*s == ' ') state = 6;
else return false;
break;
case 3:
if (*s == '+' || *s == '-') state = 4;
else if (isdigit(*s)) state = 5;
else return false;
break;
case 4:
if (isdigit(*s)) state = 5;
else return false;
break;
case 5:
if (isdigit(*s)) state = 5;
else if (*s == ' ') state = 6;
else return false;
break;
case 6:
if (*s == ' ') state = 6;
else return false;
break;
default: break;
}
s++;
}
if (state == 21 || state == 22 || state == 23 || state == 24 ||
state == 5 || state == 6) return true;
return false;
}
w****x
发帖数: 2483
28

这个相当简洁啊!
膜拜之~~

【在 d******e 的大作中提到】
: bool isNumber(const char *s) {
: while (isspace(*s)) s++;
: if (*s == '+' || *s == '-') s++;
: bool num = false;
: while (isdigit(*s)) {
: s++;
: num = true;
: }
: if (*s == '.') {
: s++;

w****x
发帖数: 2483
29
/*Validate if a given string is numeric.
Some examples:
"0" => true
" 0.1 " => true
"abc" => false
"1 a" => false
"2e10" => true
*/
bool isNumber(const char *s) {

bool bIntNum = false;
int nCurState = 1;
while (true)
{
if (nCurState == 1)
{
while (*s == ' ')
s++;

if (*s == '+' || *s == '-')
s++;

if (*s >= '0' && *s <= '9')
{
while (*s >= '0' && *s <= '9')
s++;
bIntNum = true;
}
else
{
if (*s != '.') return false;
}

if (*s == '.')
{
nCurState = 2;
s++;
}
else if (*s == 'e')
{
nCurState = 3;
s++;
}
else
break;
}
else if (nCurState == 2)
{
if (*s >= '0' && *s <= '9')
{
while (*s >= '0' && *s <= '9')
s++;
}
else if (!bIntNum) return false;

if (*s == 'e')
{
nCurState = 3;
s++;
}
else break;
}
else
{
if (*s == '+' || *s == '-')
s++;

if (*s >= '0' && *s <= '9')
{
while (*s >= '0' && *s <= '9')
s++;
}
else return false;

break;
}
}

while (*s == ' ') s++;
return *s == 0;
}
=============================================
status 1 => 小数点前面的部分
status 2 => 小数点后到'e'前面的部分
status 3 => e后面的科学计数法部分
隐含的最后一个status => break 出while loop后的只允许空格的部分
n******n
发帖数: 567
30
leetcode还是加点题吧,这都被人玩出花了
相关主题
这题也可以DP 解吧?写了一下leetcode上Valid Number,用boolean表示一些状态是不是比较简单
关于找Kth Min in 2 sorted array的问题(leetcode请进)发现valid number真是必杀题
L二电面据,附面经ebay第一轮电话面经
j*****y
发帖数: 1071
31
最好是加些 graph方面的题目。

【在 n******n 的大作中提到】
: leetcode还是加点题吧,这都被人玩出花了
j*****y
发帖数: 1071
32
好厉害,学一下

【在 w****x 的大作中提到】
: /*Validate if a given string is numeric.
: Some examples:
: "0" => true
: " 0.1 " => true
: "abc" => false
: "1 a" => false
: "2e10" => true
: */
: bool isNumber(const char *s) {
:

p*****2
发帖数: 21240
33

graph不太好加。

【在 j*****y 的大作中提到】
: 最好是加些 graph方面的题目。
j*****y
发帖数: 1071
34
用 adjecency-list 或者 adjecency-matrix 产生 input. 其他的也没什么不一样的地
方吧?

【在 p*****2 的大作中提到】
:
: graph不太好加。

p*****2
发帖数: 21240
35

常见的graph的题有哪些呢?

【在 j*****y 的大作中提到】
: 用 adjecency-list 或者 adjecency-matrix 产生 input. 其他的也没什么不一样的地
: 方吧?

j*****y
发帖数: 1071
36
至少可以 把 dfs, bfs, topological sort, 这些过一遍吧?

【在 p*****2 的大作中提到】
:
: 常见的graph的题有哪些呢?

n******n
发帖数: 567
37
觉得不用加难的吧,就把150题或稍低难度的基础题加一下
t****a
发帖数: 1212
38
这题用有限状态机确实是蛮漂亮的解法啊。
不过呢,要把程序再弄漂亮一些的话,可以在外部文件中或者常量里定义个规则来表示
状态转移图,然后主程序解析这个状态转移输入图,这样就不用hard code规则了,程
序也比较好维护。

【在 w****x 的大作中提到】
: /*Validate if a given string is numeric.
: Some examples:
: "0" => true
: " 0.1 " => true
: "abc" => false
: "1 a" => false
: "2e10" => true
: */
: bool isNumber(const char *s) {
:

n******n
发帖数: 567
39
LZ......其实自动机不是这么写的,你可以搜一下正规的写法。我当初面hulu就是这道
题,我也是这么写的,最好被灭了
f*****e
发帖数: 2992
40
二维数组?

【在 n******n 的大作中提到】
: LZ......其实自动机不是这么写的,你可以搜一下正规的写法。我当初面hulu就是这道
: 题,我也是这么写的,最好被灭了

相关主题
ebay第一轮电话面经leetcode是不是最近有点问题?
g面经来一个。L家电面
leetcode valid number问一个atoi overflow的问题
l*******b
发帖数: 2586
41
搭车问有限机处理string match. Match 任意多个任意字符的*不难处理。可是单个字
符的?貌似没办法啊

【在 n******n 的大作中提到】
: LZ......其实自动机不是这么写的,你可以搜一下正规的写法。我当初面hulu就是这道
: 题,我也是这么写的,最好被灭了

w****x
发帖数: 2483
42

被灭的原因应该不是这个吧, 这题基本算是我见过最麻烦的题了。
我也不大清楚state machine的标准写法, 大致意思意思。
谁给个更简洁的state machine的解法?

【在 n******n 的大作中提到】
: LZ......其实自动机不是这么写的,你可以搜一下正规的写法。我当初面hulu就是这道
: 题,我也是这么写的,最好被灭了

l*******b
发帖数: 2586
43
写成state machine得有7种状态,5种字符,还不能handle + -空格。。。
val table = Array(Array(0,0,0,0,0), // 0 false
Array(0,2,0,0,7), // 1 numbers eof
Array(0,2,3,5,7), // 2 numbers e . eof
Array(0,4,0,0,0), // 3 numbers
Array(0,4,0,5,7), // 4 numbers e eof
Array(0,6,0,0,0), // 5 numbers
Array(0,6,0,0,7), // 6 numbers eof
Array(7,7,7,7,7)) // 7 true
def isNumber(s: String) = {
def isNumber_helper(index: Int, stat: Int) :Boolean = {
val typeOfChar = {
if(index > s.length - 1) 4 // eof
else {
val c = s(index)
if(c <= '9' && c >= '0') 1 // number
else if(c == '.') 2 // .
else if(c == 'e') 3 // e
else 0
}
}
if(stat == 7) true
else if(stat == 0) false
else isNumber_helper(index + 1, table(stat)(typeOfChar))
}
isNumber_helper(0,1)
}
val v = "123.456e8"
val test = isNumber(v)

【在 w****x 的大作中提到】
:
: 被灭的原因应该不是这个吧, 这题基本算是我见过最麻烦的题了。
: 我也不大清楚state machine的标准写法, 大致意思意思。
: 谁给个更简洁的state machine的解法?

w****x
发帖数: 2483
44

大牛能不能用C++再写个能过OJ的版本给我参考一下?
http://www.leetcode.com/onlinejudge
搜valid number

【在 l*******b 的大作中提到】
: 写成state machine得有7种状态,5种字符,还不能handle + -空格。。。
: val table = Array(Array(0,0,0,0,0), // 0 false
: Array(0,2,0,0,7), // 1 numbers eof
: Array(0,2,3,5,7), // 2 numbers e . eof
: Array(0,4,0,0,0), // 3 numbers
: Array(0,4,0,5,7), // 4 numbers e eof
: Array(0,6,0,0,0), // 5 numbers
: Array(0,6,0,0,7), // 6 numbers eof
: Array(7,7,7,7,7)) // 7 true
: def isNumber(s: String) = {

l*******b
发帖数: 2586
45
等我写个,属于OJ上剩下几个正在发愁的题目之一

【在 w****x 的大作中提到】
:
: 大牛能不能用C++再写个能过OJ的版本给我参考一下?
: http://www.leetcode.com/onlinejudge
: 搜valid number

t*********h
发帖数: 941
46
这题得把dfa画出来在编程吧

【在 l*******b 的大作中提到】
: 写成state machine得有7种状态,5种字符,还不能handle + -空格。。。
: val table = Array(Array(0,0,0,0,0), // 0 false
: Array(0,2,0,0,7), // 1 numbers eof
: Array(0,2,3,5,7), // 2 numbers e . eof
: Array(0,4,0,0,0), // 3 numbers
: Array(0,4,0,5,7), // 4 numbers e eof
: Array(0,6,0,0,0), // 5 numbers
: Array(0,6,0,0,7), // 6 numbers eof
: Array(7,7,7,7,7)) // 7 true
: def isNumber(s: String) = {

l*******b
发帖数: 2586
47
经过很久挣扎终于调成功了。。。test case好诡异
#include
using namespace std;
class Play {
public:
bool isNumber(const char *s) {
int mat[11][7] = {0 ,0 ,0 ,0 ,0 ,0 ,0, // false
0 ,2 ,3 ,0 ,1 ,4 ,0, // 1
0 ,2 ,5 ,6 ,9 ,0 ,10,// 2
0 ,5 ,0 ,0 ,0 ,0 ,0, // 3
0 ,2 ,3 ,0 ,0 ,0 ,0, // 4
0 ,5 ,0 ,6 ,9 ,0 ,10,// 5
0 ,7 ,0 ,0 ,0 ,8 ,0, // 6
0 ,7 ,0 ,0 ,9 ,0 ,10,// 7
0 ,7 ,0 ,0 ,0 ,0 ,0, // 8
0 ,0 ,0 ,0 ,9 ,0 ,10,// 9
10,10,10,10,10,10,10 // 10
};
int i = 0;
int stat = 1;
while(s[i] != 0) {
int type = 0;
if(s[i] >= '0' && s[i] <= '9')
type = 1;
else if(s[i] == '.')
type = 2;
else if(s[i] == 'e')
type = 3;
else if(s[i] == ' ')
type = 4;
else if(s[i] == '+' || s[i] == '-')
type = 5;
if(stat == 0)
return false;
stat = mat[stat][type];
i++;
}
stat = mat[stat][6];
if(stat == 10)
return true;
else
return false;
}
};
int main() {
Play pp;
string s;
while(cin >> s) {
if(pp.isNumber(s.c_str()))
cout << "YES !" << endl;
else
cout << "NO !" << endl;
}
return 0;
}

【在 t*********h 的大作中提到】
: 这题得把dfa画出来在编程吧
t*********h
发帖数: 941
48
牛鼻 你那个matrix啥含义能不能说说

【在 l*******b 的大作中提到】
: 经过很久挣扎终于调成功了。。。test case好诡异
: #include
: using namespace std;
: class Play {
: public:
: bool isNumber(const char *s) {
: int mat[11][7] = {0 ,0 ,0 ,0 ,0 ,0 ,0, // false
: 0 ,2 ,3 ,0 ,1 ,4 ,0, // 1
: 0 ,2 ,5 ,6 ,9 ,0 ,10,// 2
: 0 ,5 ,0 ,0 ,0 ,0 ,0, // 3

l*******b
发帖数: 2586
49
1: 第一个字符,可能是 number . space sign
2: 读取一个数字但未读取 . 的时候,下一个字符可以是 number . e space eof
读取到number保持状态
读取到 . 进入 5
读取到e 进入 6
读取到 space 或者 eof结尾
3: 读取到一个 . 而且之前没有读到数字,此时下一个字符必须为数字
4: 读取到第一个字符为 sign 下一个字符可以是 . 或者number,规约到情形2,3
5: 读取到一个 . 以后下一个字符可以是number e space
下一个如果是number, 则状态保持,读到e则进入下一阶段 6,读到space就扫结尾
9
6: e 已经读取,下一个可以是number sign
是number则进入 7 再下一个为number 或者space进入9扫描结尾
是sign 则必须进入 8 再读取一个数字,然后规约到 7
9: 扫描结尾的 space

【在 t*********h 的大作中提到】
: 牛鼻 你那个matrix啥含义能不能说说
w****x
发帖数: 2483
50

滔滔江水啊, 过OJ了吧

【在 l*******b 的大作中提到】
: 经过很久挣扎终于调成功了。。。test case好诡异
: #include
: using namespace std;
: class Play {
: public:
: bool isNumber(const char *s) {
: int mat[11][7] = {0 ,0 ,0 ,0 ,0 ,0 ,0, // false
: 0 ,2 ,3 ,0 ,1 ,4 ,0, // 1
: 0 ,2 ,5 ,6 ,9 ,0 ,10,// 2
: 0 ,5 ,0 ,0 ,0 ,0 ,0, // 3

相关主题
a[i] + b[j] = c[k] 的题有靠谱的答案不?你们说leetcode做了*遍,是所有题都做了吗?
秒杀valid numberLeetcode Valid Number
valid number这道题看到有人用有限状态机做 太牛不敢看Search a 2D Matrix的两种写法,哪种更好?
l*******b
发帖数: 2586
51
过了

【在 w****x 的大作中提到】
:
: 滔滔江水啊, 过OJ了吧

l*******b
发帖数: 2586
52
这个题化成regular expression再用general的方法解灵不灵啊,搜到一个写法
^[-+]?[0-9]*\.?[0-9]*([eE][-+]?[0-9]+)?$
match regular expression
j*****y
发帖数: 1071
53
大牛太厉害了。
可不可以把那个 roman to integer 和 integer to roman的也用有限状态机 写个简
单点的?

【在 l*******b 的大作中提到】
: 过了
s*******y
发帖数: 44
54
低调哥这个是我见过最简洁的code了。
我也用有限状态机写了一个,画状态机麻烦,code倒是不难写,就是比较繁琐。
bool isNumber(const char *s) {
int state = 0;
while (*s) {
switch (state) {
case 0:
if (*s == ' ') state = 0;
else if (*s == '+' || *s == '-') state = 11;
else if (isdigit(*s)) state = 21;
else if (*s == '.') state = 1;
else return false;
break;
case 1:
if (isdigit(*s)) state = 22;
else return false;
break;
case 11:
if (*s == '.') state = 1;
else if (isdigit(*s)) state = 24;
else return false;
break;
case 21:
if (isdigit(*s)) state = 21;
else if (*s == 'e') state = 3;
else if (*s == '.') state = 22;
else if (*s == ' ') state = 6;
else return false;
break;
case 22:
if (isdigit(*s)) state = 23;
else if (*s == 'e') state = 3;
else if (*s == ' ') state = 6;
else return false;
break;
case 23:
if (isdigit(*s)) state = 23;
else if (*s == 'e') state = 3;
else if (*s == ' ') state = 6;
else return false;
break;
case 24:
if (isdigit(*s)) state = 24;
else if (*s == '.') state = 22;
else if (*s == 'e') state = 3;
else if (*s == ' ') state = 6;
else return false;
break;
case 3:
if (*s == '+' || *s == '-') state = 4;
else if (isdigit(*s)) state = 5;
else return false;
break;
case 4:
if (isdigit(*s)) state = 5;
else return false;
break;
case 5:
if (isdigit(*s)) state = 5;
else if (*s == ' ') state = 6;
else return false;
break;
case 6:
if (*s == ' ') state = 6;
else return false;
break;
default: break;
}
s++;
}
if (state == 21 || state == 22 || state == 23 || state == 24 ||
state == 5 || state == 6) return true;
return false;
}
w****x
发帖数: 2483
55

这个相当简洁啊!
膜拜之~~

【在 d******e 的大作中提到】
: bool isNumber(const char *s) {
: while (isspace(*s)) s++;
: if (*s == '+' || *s == '-') s++;
: bool num = false;
: while (isdigit(*s)) {
: s++;
: num = true;
: }
: if (*s == '.') {
: s++;

J****3
发帖数: 427
56
膜拜+1. 今天又写这个翻出来
s*********s
发帖数: 318
57
didiaoge 的 简洁code在哪里?
c******t
发帖数: 1500
58
Google “低调哥 isNumber” 就是

【在 s*********s 的大作中提到】
: didiaoge 的 简洁code在哪里?
c********p
发帖数: 1969
59
听说是大牛,赶紧来mark
a*****a
发帖数: 46
60
[0-9]*.?[0-9]* 这样的话“."就返回true了吧?
我写的是这样的,过了OJ了
^(space)*[+-]?([0-9]+|[0-9]*.[0-9]+|[0-9]+.[0-9]*)([eE][+-]?[0-9]+)?(space)*$

【在 l*******b 的大作中提到】
: 这个题化成regular expression再用general的方法解灵不灵啊,搜到一个写法
: ^[-+]?[0-9]*\.?[0-9]*([eE][-+]?[0-9]+)?$
: match regular expression

1 (共1页)
相关主题
一个面试题g面经来一个。
贡献今天facebook电面 一道题leetcode valid number
这题也可以DP 解吧?leetcode是不是最近有点问题?
关于找Kth Min in 2 sorted array的问题(leetcode请进)L家电面
L二电面据,附面经问一个atoi overflow的问题
写了一下leetcode上Valid Number,用boolean表示一些状态是不是比较简单a[i] + b[j] = c[k] 的题有靠谱的答案不?
发现valid number真是必杀题秒杀valid number
ebay第一轮电话面经valid number这道题看到有人用有限状态机做 太牛不敢看
相关话题的讨论汇总
话题: else话题: false话题: state话题: return话题: ncurstate