由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - 秒杀valid number
相关主题
写了一下leetcode上Valid Number,用boolean表示一些状态是不是比较简单Programming interview exposed 上面的那道NULL or Cycle的linked list题
L二电面据,附面经求教一个题目,sudoku 下面代码哪里错了。。。
用有限状态机写了一下leetcode valid numberLeetcode Timeout
L家电面Interleave Strings那个题目有O(n)时间 O(1)空间算法么?
valid number这道题看到有人用有限状态机做 太牛不敢看interleave string 的题目
如何实现线程安全的哈希表Google电面题 写dominoChecker class
一道算法题请教n queen 问题的time complexity
新鲜Amazon面经(附参考答案) 顺便求各种大公司referIsomorphic Strings 的单Hashmap解法
相关话题的讨论汇总
话题: state话题: return话题: override话题: public话题: readdigit
进入JobHunting版参与讨论
1 (共1页)
s**x
发帖数: 7506
1
说一下思路吧,懒得写代码
1 skip white spaces
2 skip + or - if there is one.
3 skip all numeric digits, say n1 digits are skipped.
4 skip . if there is one
5 same as step 3, but save count to n2.
6 here is the key part, return false if n1 + n2 == 0.
7. Skip E or e if there is one.
8 if there is e or E, do step 2 and 3, return false if n1 == 0
9 skip white space
10 return false if string is empty now, otherwise return true.
Simple, fast and hard to make mistakes.
s**x
发帖数: 7506
2
有人找到了代码
bool isNumber(const char *s)
{
if (!s) return false;
s = skipSpace(s);
if (*s == '+' || *s == '-')
{
++s;
}
int n1 = getNumDigits(s);
s += n1;
if (*s == '.')
{
++s;
}
int n2 = getNumDigits(s);
if (n1 + n2 == 0) return false;
s += n2;
if (*s == 'E' || *s == 'e')
{
++s;
if (*s == '+' || *s == '-')
{
++s;
}
int n3 = getNumDigits(s);
if (n2 == 0) return false;
s += n3;
}
s = skipSpace(s);
return *s == '\0';
}
y****2
发帖数: 1017
3
我以前看过的最好的解法是那个用finite state machine做的。
我看看你的解法
y***n
发帖数: 1594
4
真心说,面试想清楚10步不容易。

【在 s**x 的大作中提到】
: 说一下思路吧,懒得写代码
: 1 skip white spaces
: 2 skip + or - if there is one.
: 3 skip all numeric digits, say n1 digits are skipped.
: 4 skip . if there is one
: 5 same as step 3, but save count to n2.
: 6 here is the key part, return false if n1 + n2 == 0.
: 7. Skip E or e if there is one.
: 8 if there is e or E, do step 2 and 3, return false if n1 == 0
: 9 skip white space

s**x
发帖数: 7506
5
sigh, 唯一的 trick 就是第六步。 写个浮点数 -123.E+5 , 一清二楚阿。
这个是最直接明了的土办法了。 我是慢慢琢磨出来的, 老觉得网上给出的算法都很坑
爹。 面试高度紧张, 好几个变量直接歇菜。

【在 y***n 的大作中提到】
: 真心说,面试想清楚10步不容易。
s**x
发帖数: 7506
6
那个当然是最优的, 可以提一下加分。

【在 y****2 的大作中提到】
: 我以前看过的最好的解法是那个用finite state machine做的。
: 我看看你的解法

y***n
发帖数: 1594
7
你误会了,你的解法很好,我是说看到一个新的题,要想到10步不容易。

【在 s**x 的大作中提到】
: sigh, 唯一的 trick 就是第六步。 写个浮点数 -123.E+5 , 一清二楚阿。
: 这个是最直接明了的土办法了。 我是慢慢琢磨出来的, 老觉得网上给出的算法都很坑
: 爹。 面试高度紧张, 好几个变量直接歇菜。

s*****r
发帖数: 43070
8
还是有corner case没有handle,比如多个.的情况

【在 s**x 的大作中提到】
: 说一下思路吧,懒得写代码
: 1 skip white spaces
: 2 skip + or - if there is one.
: 3 skip all numeric digits, say n1 digits are skipped.
: 4 skip . if there is one
: 5 same as step 3, but save count to n2.
: 6 here is the key part, return false if n1 + n2 == 0.
: 7. Skip E or e if there is one.
: 8 if there is e or E, do step 2 and 3, return false if n1 == 0
: 9 skip white space

s*****r
发帖数: 43070
9
如果真写成这样可以直接踢出去了
如果s里面有非数字的字符,getNumDigits()应该会返回何值,程序里面没有检测这种
返回值。getNumDigits()应该遇到什么情况返回,貌似条件是遇到.或者大小写e,但问
题来了,如果s里面有两个.,比如1.1.1,这个程序也会返回true
这个问题其实有点烦琐,因为需要一些context info

【在 s**x 的大作中提到】
: 有人找到了代码
: bool isNumber(const char *s)
: {
: if (!s) return false;
: s = skipSpace(s);
: if (*s == '+' || *s == '-')
: {
: ++s;
: }
: int n1 = getNumDigits(s);

m*****k
发帖数: 731
10
it works,
1.1.1
会return '.'=='\0'
相关主题
如何实现线程安全的哈希表Programming interview exposed 上面的那道NULL or Cycle的linked list题
一道算法题求教一个题目,sudoku 下面代码哪里错了。。。
新鲜Amazon面经(附参考答案) 顺便求各种大公司referLeetcode Timeout
进入JobHunting版参与讨论
z***c
发帖数: 78
11
我觉得这个解法很好,容易理解也容易写出来。为什么会被踢
b*****c
发帖数: 16
12
好思路,就是程序里if (n2 == 0) return false;那里 是不是应该是n3
附上我按照lz思路写的,leetcode OJ 136ms 通过
bool isNumber(const char *s) {
if (!s) return false;
while (*s == ' ') s++;
if (*s == '+' || *s == '-') s++;
int n1 = 0;
while (isdigit(*s)) {
n1++;
s++;
}
if (*s == '.') s++;
int n2 = 0;
while (isdigit(*s)) {
n2++;
s++;
}
if (n1 + n2 == 0) return false;
if (*s == 'e' || *s == 'E') {
s++;
if (*s == '+' || *s == '-') s++;
int n3 = 0;
while (isdigit(*s)) {
n3++;
s++;
}
if(n3 == 0) return false;
}
while (*s == ' ') s++;
return *s == '
s**x
发帖数: 7506
13
他好像是L家的,L家的面试官经常自己搞错的,版上经常碰到。给他们一个新解法看半
天都看不懂,sigh.

★ 发自iPhone App: ChineseWeb 8.7

【在 z***c 的大作中提到】
: 我觉得这个解法很好,容易理解也容易写出来。为什么会被踢
q********c
发帖数: 1774
14
L的码工coding水品堪忧啊,还一堆一堆senior SDE.

【在 s**x 的大作中提到】
: 他好像是L家的,L家的面试官经常自己搞错的,版上经常碰到。给他们一个新解法看半
: 天都看不懂,sigh.
:
: ★ 发自iPhone App: ChineseWeb 8.7

s*****r
发帖数: 43070
15
还是认真点吧,你的getNumDigits(char*)定义上面有问题,肯定会有bug,还不能
handle negative case
对于有经验的面试官,一眼就看出问题来

【在 s**x 的大作中提到】
: 他好像是L家的,L家的面试官经常自己搞错的,版上经常碰到。给他们一个新解法看半
: 天都看不懂,sigh.
:
: ★ 发自iPhone App: ChineseWeb 8.7

s**x
发帖数: 7506
16
sigh, 怎么说你呢? 真正有经验的读了那个说明根本就不需要看 code 了, 这个
code 真是太简单了, 想出错都很难, 真的, 因为就是简单的 sequencial
processing, 记得我最初 post 的 code, 有人发现有一部忘了移动指针. 如果你用
pointer reference for functions, 这个都不会出错。
为了帮助你, getNUmDigits should really be skipNumDigits to be consistent
with my comments in first post, it is someone else's post, i did not change
completely. but every junior level engineer should know what it does.

【在 s*****r 的大作中提到】
: 还是认真点吧,你的getNumDigits(char*)定义上面有问题,肯定会有bug,还不能
: handle negative case
: 对于有经验的面试官,一眼就看出问题来

h*********2
发帖数: 444
17
我觉得挺好
但是为什么是n1+n2 == 0 return false
.1 和 1. 都是valid吗
h*********2
发帖数: 444
18
比如说1.e5,看着感觉有点别扭。
s**x
发帖数: 7506
m*****k
发帖数: 731
20
I like it too!

【在 z***c 的大作中提到】
: 我觉得这个解法很好,容易理解也容易写出来。为什么会被踢
相关主题
Interleave Strings那个题目有O(n)时间 O(1)空间算法么?请教n queen 问题的time complexity
interleave string 的题目Isomorphic Strings 的单Hashmap解法
Google电面题 写dominoChecker classjava 基本问题
进入JobHunting版参与讨论
l***4
发帖数: 1788
21
为什么不用正则表达式?

【在 s**x 的大作中提到】
: 说一下思路吧,懒得写代码
: 1 skip white spaces
: 2 skip + or - if there is one.
: 3 skip all numeric digits, say n1 digits are skipped.
: 4 skip . if there is one
: 5 same as step 3, but save count to n2.
: 6 here is the key part, return false if n1 + n2 == 0.
: 7. Skip E or e if there is one.
: 8 if there is e or E, do step 2 and 3, return false if n1 == 0
: 9 skip white space

y****2
发帖数: 1017
22
确实很赞。我写了一遍。 过了Leetcode.
l****s
发帖数: 75
23
我写了一遍。正则的太麻烦了。
还是楼主的思路好!再贴一下:
class Solution {
private:
void skipSpace(const char *& s)
{
while (*s == ' ' || *s == 't')
{
++s;
}
}
int getNumDigits(const char *s)
{
int num = 0;
while (*s >= '0' && *s <= '9')
{
++s;
++num;
}
return num;
}

public:
bool isNumber(const char *s) {
if (!s) return false;
skipSpace(s);
if (*s == '+' || *s == '-')
{
++s;
}
int numDigits1 = getNumDigits(s);
s += numDigits1;
if (*s == '.')
{
++s;
}
int numDigits2 = getNumDigits(s);
if (numDigits1 + numDigits2 == 0) return false; //点前后不能都没有数字
s += numDigits2;
if (*s == 'E' || *s == 'e')
{
++s;
if (*s == '+' || *s == '-')
{
++s;
}
int numDigits3 = getNumDigits(s);
if (numDigits3 == 0) return false;
s += numDigits3;
}
skipSpace(s);
return *s == '\0';
}
};

【在 l***4 的大作中提到】
: 为什么不用正则表达式?
l****s
发帖数: 75
24
对。点前后不能都没有数字

【在 h*********2 的大作中提到】
: 我觉得挺好
: 但是为什么是n1+n2 == 0 return false
: .1 和 1. 都是valid吗

m**e
发帖数: 150
25
切记,if 后面一定要换一行,不然可能被评coding style不好。

【在 l****s 的大作中提到】
: 我写了一遍。正则的太麻烦了。
: 还是楼主的思路好!再贴一下:
: class Solution {
: private:
: void skipSpace(const char *& s)
: {
: while (*s == ' ' || *s == 't')
: {
: ++s;
: }

g**********s
发帖数: 13
26
E后面不能是小数吗,指数不一定非是整数的
p***y
发帖数: 637
27
if(....){
a=1;
}
这个风格在面试里算好还是太啰嗦?

【在 m**e 的大作中提到】
: 切记,if 后面一定要换一行,不然可能被评coding style不好。
s*****B
发帖数: 32
28


【在 s**x 的大作中提到】
: 说一下思路吧,懒得写代码
: 1 skip white spaces
: 2 skip + or - if there is one.
: 3 skip all numeric digits, say n1 digits are skipped.
: 4 skip . if there is one
: 5 same as step 3, but save count to n2.
: 6 here is the key part, return false if n1 + n2 == 0.
: 7. Skip E or e if there is one.
: 8 if there is e or E, do step 2 and 3, return false if n1 == 0
: 9 skip white space

f*****u
发帖数: 308
29
这个用finite state machine做的方法谁能给个代码链接?学习下。

【在 y****2 的大作中提到】
: 我以前看过的最好的解法是那个用finite state machine做的。
: 我看看你的解法

z***m
发帖数: 1602
30
很好

【在 s**x 的大作中提到】
: 说一下思路吧,懒得写代码
: 1 skip white spaces
: 2 skip + or - if there is one.
: 3 skip all numeric digits, say n1 digits are skipped.
: 4 skip . if there is one
: 5 same as step 3, but save count to n2.
: 6 here is the key part, return false if n1 + n2 == 0.
: 7. Skip E or e if there is one.
: 8 if there is e or E, do step 2 and 3, return false if n1 == 0
: 9 skip white space

相关主题
leetcode是不是最近有点问题?L二电面据,附面经
问个Java的HashSet.contains的问题用有限状态机写了一下leetcode valid number
写了一下leetcode上Valid Number,用boolean表示一些状态是不是比较简单L家电面
进入JobHunting版参与讨论
p***y
发帖数: 637
31
基本思路应该是按parsing的思路走,然后无需真的计算出数字来。

【在 s**x 的大作中提到】
: 说一下思路吧,懒得写代码
: 1 skip white spaces
: 2 skip + or - if there is one.
: 3 skip all numeric digits, say n1 digits are skipped.
: 4 skip . if there is one
: 5 same as step 3, but save count to n2.
: 6 here is the key part, return false if n1 + n2 == 0.
: 7. Skip E or e if there is one.
: 8 if there is e or E, do step 2 and 3, return false if n1 == 0
: 9 skip white space

l********s
发帖数: 358
32
我的秒杀办法:
public boolean isNumber(String s) {
try {
Double.valueOf(s);
return true;
} catch (NumberFormatException e) {
return false;
}
}
N*D
发帖数: 3641
33
def toNum(s: String) = (scala.util.control.Exception.allCatch opt s.toDouble
).isDefined

【在 l********s 的大作中提到】
: 我的秒杀办法:
: public boolean isNumber(String s) {
: try {
: Double.valueOf(s);
: return true;
: } catch (NumberFormatException e) {
: return false;
: }
: }

w*****j
发帖数: 226
34
用自动机写的
求批判
个人觉得自动机的好处是可视化,只要图画对,代码不容易写错
corner case看得也比较清楚
enum State
{
ErrorState
{
@Override
public boolean isValid() { return false; }
},
EndState,
StartState
{
@Override
public State readDigit() { return DigitState; }
@Override
public State readPlus() { return PlusState; }

@Override
public State readMinus() { return MinusState; }

@Override
public State readPoint() { return PointState; }

@Override
public State readSpace() { return this; }
},
PlusState
{
@Override
public State readDigit() { return DigitState; }

@Override
public State readPoint() { return PlusPointState; }
},
MinusState
{
@Override
public State readDigit() { return DigitState; }

@Override
public State readPoint() { return MinusPointState; }
},
PlusPointState
{
@Override
public State readDigit() { return DigitState; }
},
MinusPointState
{
@Override
public State readDigit() { return DigitState; }
},
DigitState
{
@Override
public State readDigit() { return this; }

@Override
public State readPoint() { return DigitPointState; }

@Override
public State readE() { return EState; }

@Override
public State readEnd() { return EndState; }
},
DigitPointState
{
@Override
public State readDigit() { return PointDigitState; }

@Override
public State readEnd() { return EndState; }

@Override
public State readE() { return EState; }
},
PointState
{
@Override
public State readDigit() { return PointDigitState; }
},
PointDigitState
{
@Override
public State readDigit() { return this; }

@Override
public State readEnd() { return EndState; }

@Override
public State readE() { return EState; }
},
EState
{
@Override
public State readDigit() { return EDigitState; }

@Override
public State readPlus() { return EPlusState; }

@Override
public State readMinus() { return EMinusState; }
},
EPlusState
{
@Override
public State readDigit() { return EDigitState; }
},
EMinusState
{
@Override
public State readDigit() { return EDigitState; }
},
EDigitState
{
@Override
public State readDigit() { return this; }

@Override
public State readEnd() { return EndState; }
};

public boolean isValid() { return true; }
public State readSpace() { return ErrorState; }
public State readDigit() { return ErrorState; }
public State readPlus() { return ErrorState; }
public State readMinus() { return ErrorState; }
public State readPoint() { return ErrorState; }
public State readE() { return ErrorState; }
public State readEnd() { return ErrorState; }
}
public class ValidNumber
{
private static boolean invalidChar(char input) {
return !(Character.isDigit(input) ||
input == ' ' ||
input == '+' ||
input == '-' ||
input == '.' ||
input == 'e' ||
input == 'E');
}

public static boolean isNumber(String s)
{
s = s.trim(); // remove leading and trailing spaces
State state = State.StartState;
for(char c: s.toCharArray())
{
// some chars are not acceptable by any state
if(invalidChar(c))
return false;

if(Character.isDigit(c))
state = state.readDigit();
else if(c == ' ')
state = state.readSpace();
else if(c == '+')
state = state.readPlus();
else if(c == '-')
state = state.readMinus();
else if(c == '.')
state = state.readPoint();
else if(c == 'e' || c == 'E')
state = state.readE();

if(!state.isValid())
return false;
}
state = state.readEnd();
return state == State.EndState;
}
}

【在 f*****u 的大作中提到】
: 这个用finite state machine做的方法谁能给个代码链接?学习下。
b******g
发帖数: 3616
35
跪了。。。自动机的方法太高深了

【在 w*****j 的大作中提到】
: 用自动机写的
: 求批判
: 个人觉得自动机的好处是可视化,只要图画对,代码不容易写错
: corner case看得也比较清楚
: enum State
: {
: ErrorState
: {
: @Override
: public boolean isValid() { return false; }

w*****j
发帖数: 226
36
补充一句,自动机另一种写法是用二维表格来记录状态转换,更简洁,但是可读性更差
Q****a
发帖数: 296
37
可以用regex写吗? 面试官会允许么? 那样就几行
s**x
发帖数: 7506
38
说一下思路吧,懒得写代码
1 skip white spaces
2 skip + or - if there is one.
3 skip all numeric digits, say n1 digits are skipped.
4 skip . if there is one
5 same as step 3, but save count to n2.
6 here is the key part, return false if n1 + n2 == 0.
7. Skip E or e if there is one.
8 if there is e or E, do step 2 and 3, return false if n1 == 0
9 skip white space
10 return false if string is empty now, otherwise return true.
Simple, fast and hard to make mistakes.
s**x
发帖数: 7506
39
有人找到了代码
bool isNumber(const char *s)
{
if (!s) return false;
s = skipSpace(s);
if (*s == '+' || *s == '-')
{
++s;
}
int n1 = getNumDigits(s);
s += n1;
if (*s == '.')
{
++s;
}
int n2 = getNumDigits(s);
if (n1 + n2 == 0) return false;
s += n2;
if (*s == 'E' || *s == 'e')
{
++s;
if (*s == '+' || *s == '-')
{
++s;
}
int n3 = getNumDigits(s);
if (n2 == 0) return false;
s += n3;
}
s = skipSpace(s);
return *s == '\0';
}
y****2
发帖数: 1017
40
我以前看过的最好的解法是那个用finite state machine做的。
我看看你的解法
相关主题
L家电面一道算法题
valid number这道题看到有人用有限状态机做 太牛不敢看新鲜Amazon面经(附参考答案) 顺便求各种大公司refer
如何实现线程安全的哈希表Programming interview exposed 上面的那道NULL or Cycle的linked list题
进入JobHunting版参与讨论
y***n
发帖数: 1594
41
真心说,面试想清楚10步不容易。

【在 s**x 的大作中提到】
: 说一下思路吧,懒得写代码
: 1 skip white spaces
: 2 skip + or - if there is one.
: 3 skip all numeric digits, say n1 digits are skipped.
: 4 skip . if there is one
: 5 same as step 3, but save count to n2.
: 6 here is the key part, return false if n1 + n2 == 0.
: 7. Skip E or e if there is one.
: 8 if there is e or E, do step 2 and 3, return false if n1 == 0
: 9 skip white space

s**x
发帖数: 7506
42
sigh, 唯一的 trick 就是第六步。 写个浮点数 -123.E+5 , 一清二楚阿。
这个是最直接明了的土办法了。 我是慢慢琢磨出来的, 老觉得网上给出的算法都很坑
爹。 面试高度紧张, 好几个变量直接歇菜。

【在 y***n 的大作中提到】
: 真心说,面试想清楚10步不容易。
s**x
发帖数: 7506
43
那个当然是最优的, 可以提一下加分。

【在 y****2 的大作中提到】
: 我以前看过的最好的解法是那个用finite state machine做的。
: 我看看你的解法

y***n
发帖数: 1594
44
你误会了,你的解法很好,我是说看到一个新的题,要想到10步不容易。

【在 s**x 的大作中提到】
: sigh, 唯一的 trick 就是第六步。 写个浮点数 -123.E+5 , 一清二楚阿。
: 这个是最直接明了的土办法了。 我是慢慢琢磨出来的, 老觉得网上给出的算法都很坑
: 爹。 面试高度紧张, 好几个变量直接歇菜。

s*****r
发帖数: 43070
45
还是有corner case没有handle,比如多个.的情况

【在 s**x 的大作中提到】
: 说一下思路吧,懒得写代码
: 1 skip white spaces
: 2 skip + or - if there is one.
: 3 skip all numeric digits, say n1 digits are skipped.
: 4 skip . if there is one
: 5 same as step 3, but save count to n2.
: 6 here is the key part, return false if n1 + n2 == 0.
: 7. Skip E or e if there is one.
: 8 if there is e or E, do step 2 and 3, return false if n1 == 0
: 9 skip white space

s*****r
发帖数: 43070
46
如果真写成这样可以直接踢出去了
如果s里面有非数字的字符,getNumDigits()应该会返回何值,程序里面没有检测这种
返回值。getNumDigits()应该遇到什么情况返回,貌似条件是遇到.或者大小写e,但问
题来了,如果s里面有两个.,比如1.1.1,这个程序也会返回true
这个问题其实有点烦琐,因为需要一些context info

【在 s**x 的大作中提到】
: 有人找到了代码
: bool isNumber(const char *s)
: {
: if (!s) return false;
: s = skipSpace(s);
: if (*s == '+' || *s == '-')
: {
: ++s;
: }
: int n1 = getNumDigits(s);

m*****k
发帖数: 731
47
it works,
1.1.1
会return '.'=='\0'
z***c
发帖数: 78
48
我觉得这个解法很好,容易理解也容易写出来。为什么会被踢
b*****c
发帖数: 16
49
好思路,就是程序里if (n2 == 0) return false;那里 是不是应该是n3
附上我按照lz思路写的,leetcode OJ 136ms 通过
bool isNumber(const char *s) {
if (!s) return false;
while (*s == ' ') s++;
if (*s == '+' || *s == '-') s++;
int n1 = 0;
while (isdigit(*s)) {
n1++;
s++;
}
if (*s == '.') s++;
int n2 = 0;
while (isdigit(*s)) {
n2++;
s++;
}
if (n1 + n2 == 0) return false;
if (*s == 'e' || *s == 'E') {
s++;
if (*s == '+' || *s == '-') s++;
int n3 = 0;
while (isdigit(*s)) {
n3++;
s++;
}
if(n3 == 0) return false;
}
while (*s == ' ') s++;
return *s == '
s**x
发帖数: 7506
50
他好像是L家的,L家的面试官经常自己搞错的,版上经常碰到。给他们一个新解法看半
天都看不懂,sigh.

★ 发自iPhone App: ChineseWeb 8.7

【在 z***c 的大作中提到】
: 我觉得这个解法很好,容易理解也容易写出来。为什么会被踢
相关主题
求教一个题目,sudoku 下面代码哪里错了。。。interleave string 的题目
Leetcode TimeoutGoogle电面题 写dominoChecker class
Interleave Strings那个题目有O(n)时间 O(1)空间算法么?请教n queen 问题的time complexity
进入JobHunting版参与讨论
q********c
发帖数: 1774
51
L的码工coding水品堪忧啊,还一堆一堆senior SDE.

【在 s**x 的大作中提到】
: 他好像是L家的,L家的面试官经常自己搞错的,版上经常碰到。给他们一个新解法看半
: 天都看不懂,sigh.
:
: ★ 发自iPhone App: ChineseWeb 8.7

s*****r
发帖数: 43070
52
还是认真点吧,你的getNumDigits(char*)定义上面有问题,肯定会有bug,还不能
handle negative case
对于有经验的面试官,一眼就看出问题来

【在 s**x 的大作中提到】
: 他好像是L家的,L家的面试官经常自己搞错的,版上经常碰到。给他们一个新解法看半
: 天都看不懂,sigh.
:
: ★ 发自iPhone App: ChineseWeb 8.7

s**x
发帖数: 7506
53
sigh, 怎么说你呢? 真正有经验的读了那个说明根本就不需要看 code 了, 这个
code 真是太简单了, 想出错都很难, 真的, 因为就是简单的 sequencial
processing, 记得我最初 post 的 code, 有人发现有一部忘了移动指针. 如果你用
pointer reference for functions, 这个都不会出错。
为了帮助你, getNUmDigits should really be skipNumDigits to be consistent
with my comments in first post, it is someone else's post, i did not change
completely. but every junior level engineer should know what it does.

【在 s*****r 的大作中提到】
: 还是认真点吧,你的getNumDigits(char*)定义上面有问题,肯定会有bug,还不能
: handle negative case
: 对于有经验的面试官,一眼就看出问题来

h*********2
发帖数: 444
54
我觉得挺好
但是为什么是n1+n2 == 0 return false
.1 和 1. 都是valid吗
h*********2
发帖数: 444
55
比如说1.e5,看着感觉有点别扭。
s**x
发帖数: 7506
m*****k
发帖数: 731
57
I like it too!

【在 z***c 的大作中提到】
: 我觉得这个解法很好,容易理解也容易写出来。为什么会被踢
l***4
发帖数: 1788
58
为什么不用正则表达式?

【在 s**x 的大作中提到】
: 说一下思路吧,懒得写代码
: 1 skip white spaces
: 2 skip + or - if there is one.
: 3 skip all numeric digits, say n1 digits are skipped.
: 4 skip . if there is one
: 5 same as step 3, but save count to n2.
: 6 here is the key part, return false if n1 + n2 == 0.
: 7. Skip E or e if there is one.
: 8 if there is e or E, do step 2 and 3, return false if n1 == 0
: 9 skip white space

y****2
发帖数: 1017
59
确实很赞。我写了一遍。 过了Leetcode.
l****s
发帖数: 75
60
我写了一遍。正则的太麻烦了。
还是楼主的思路好!再贴一下:
class Solution {
private:
void skipSpace(const char *& s)
{
while (*s == ' ' || *s == 't')
{
++s;
}
}
int getNumDigits(const char *s)
{
int num = 0;
while (*s >= '0' && *s <= '9')
{
++s;
++num;
}
return num;
}

public:
bool isNumber(const char *s) {
if (!s) return false;
skipSpace(s);
if (*s == '+' || *s == '-')
{
++s;
}
int numDigits1 = getNumDigits(s);
s += numDigits1;
if (*s == '.')
{
++s;
}
int numDigits2 = getNumDigits(s);
if (numDigits1 + numDigits2 == 0) return false; //点前后不能都没有数字
s += numDigits2;
if (*s == 'E' || *s == 'e')
{
++s;
if (*s == '+' || *s == '-')
{
++s;
}
int numDigits3 = getNumDigits(s);
if (numDigits3 == 0) return false;
s += numDigits3;
}
skipSpace(s);
return *s == '\0';
}
};

【在 l***4 的大作中提到】
: 为什么不用正则表达式?
相关主题
Isomorphic Strings 的单Hashmap解法问个Java的HashSet.contains的问题
java 基本问题写了一下leetcode上Valid Number,用boolean表示一些状态是不是比较简单
leetcode是不是最近有点问题?L二电面据,附面经
进入JobHunting版参与讨论
l****s
发帖数: 75
61
对。点前后不能都没有数字

【在 h*********2 的大作中提到】
: 我觉得挺好
: 但是为什么是n1+n2 == 0 return false
: .1 和 1. 都是valid吗

m**e
发帖数: 150
62
切记,if 后面一定要换一行,不然可能被评coding style不好。

【在 l****s 的大作中提到】
: 我写了一遍。正则的太麻烦了。
: 还是楼主的思路好!再贴一下:
: class Solution {
: private:
: void skipSpace(const char *& s)
: {
: while (*s == ' ' || *s == 't')
: {
: ++s;
: }

g**********s
发帖数: 13
63
E后面不能是小数吗,指数不一定非是整数的
p***y
发帖数: 637
64
if(....){
a=1;
}
这个风格在面试里算好还是太啰嗦?

【在 m**e 的大作中提到】
: 切记,if 后面一定要换一行,不然可能被评coding style不好。
s*****B
发帖数: 32
65


【在 s**x 的大作中提到】
: 说一下思路吧,懒得写代码
: 1 skip white spaces
: 2 skip + or - if there is one.
: 3 skip all numeric digits, say n1 digits are skipped.
: 4 skip . if there is one
: 5 same as step 3, but save count to n2.
: 6 here is the key part, return false if n1 + n2 == 0.
: 7. Skip E or e if there is one.
: 8 if there is e or E, do step 2 and 3, return false if n1 == 0
: 9 skip white space

f*****u
发帖数: 308
66
这个用finite state machine做的方法谁能给个代码链接?学习下。

【在 y****2 的大作中提到】
: 我以前看过的最好的解法是那个用finite state machine做的。
: 我看看你的解法

z***m
发帖数: 1602
67
很好

【在 s**x 的大作中提到】
: 说一下思路吧,懒得写代码
: 1 skip white spaces
: 2 skip + or - if there is one.
: 3 skip all numeric digits, say n1 digits are skipped.
: 4 skip . if there is one
: 5 same as step 3, but save count to n2.
: 6 here is the key part, return false if n1 + n2 == 0.
: 7. Skip E or e if there is one.
: 8 if there is e or E, do step 2 and 3, return false if n1 == 0
: 9 skip white space

p***y
发帖数: 637
68
基本思路应该是按parsing的思路走,然后无需真的计算出数字来。

【在 s**x 的大作中提到】
: 说一下思路吧,懒得写代码
: 1 skip white spaces
: 2 skip + or - if there is one.
: 3 skip all numeric digits, say n1 digits are skipped.
: 4 skip . if there is one
: 5 same as step 3, but save count to n2.
: 6 here is the key part, return false if n1 + n2 == 0.
: 7. Skip E or e if there is one.
: 8 if there is e or E, do step 2 and 3, return false if n1 == 0
: 9 skip white space

l********s
发帖数: 358
69
我的秒杀办法:
public boolean isNumber(String s) {
try {
Double.valueOf(s);
return true;
} catch (NumberFormatException e) {
return false;
}
}
N*D
发帖数: 3641
70
def toNum(s: String) = (scala.util.control.Exception.allCatch opt s.toDouble
).isDefined

【在 l********s 的大作中提到】
: 我的秒杀办法:
: public boolean isNumber(String s) {
: try {
: Double.valueOf(s);
: return true;
: } catch (NumberFormatException e) {
: return false;
: }
: }

相关主题
L二电面据,附面经valid number这道题看到有人用有限状态机做 太牛不敢看
用有限状态机写了一下leetcode valid number如何实现线程安全的哈希表
L家电面一道算法题
进入JobHunting版参与讨论
w*****j
发帖数: 226
71
用自动机写的
求批判
个人觉得自动机的好处是可视化,只要图画对,代码不容易写错
corner case看得也比较清楚
enum State
{
ErrorState
{
@Override
public boolean isValid() { return false; }
},
EndState,
StartState
{
@Override
public State readDigit() { return DigitState; }
@Override
public State readPlus() { return PlusState; }

@Override
public State readMinus() { return MinusState; }

@Override
public State readPoint() { return PointState; }

@Override
public State readSpace() { return this; }
},
PlusState
{
@Override
public State readDigit() { return DigitState; }

@Override
public State readPoint() { return PlusPointState; }
},
MinusState
{
@Override
public State readDigit() { return DigitState; }

@Override
public State readPoint() { return MinusPointState; }
},
PlusPointState
{
@Override
public State readDigit() { return DigitState; }
},
MinusPointState
{
@Override
public State readDigit() { return DigitState; }
},
DigitState
{
@Override
public State readDigit() { return this; }

@Override
public State readPoint() { return DigitPointState; }

@Override
public State readE() { return EState; }

@Override
public State readEnd() { return EndState; }
},
DigitPointState
{
@Override
public State readDigit() { return PointDigitState; }

@Override
public State readEnd() { return EndState; }

@Override
public State readE() { return EState; }
},
PointState
{
@Override
public State readDigit() { return PointDigitState; }
},
PointDigitState
{
@Override
public State readDigit() { return this; }

@Override
public State readEnd() { return EndState; }

@Override
public State readE() { return EState; }
},
EState
{
@Override
public State readDigit() { return EDigitState; }

@Override
public State readPlus() { return EPlusState; }

@Override
public State readMinus() { return EMinusState; }
},
EPlusState
{
@Override
public State readDigit() { return EDigitState; }
},
EMinusState
{
@Override
public State readDigit() { return EDigitState; }
},
EDigitState
{
@Override
public State readDigit() { return this; }

@Override
public State readEnd() { return EndState; }
};

public boolean isValid() { return true; }
public State readSpace() { return ErrorState; }
public State readDigit() { return ErrorState; }
public State readPlus() { return ErrorState; }
public State readMinus() { return ErrorState; }
public State readPoint() { return ErrorState; }
public State readE() { return ErrorState; }
public State readEnd() { return ErrorState; }
}
public class ValidNumber
{
private static boolean invalidChar(char input) {
return !(Character.isDigit(input) ||
input == ' ' ||
input == '+' ||
input == '-' ||
input == '.' ||
input == 'e' ||
input == 'E');
}

public static boolean isNumber(String s)
{
s = s.trim(); // remove leading and trailing spaces
State state = State.StartState;
for(char c: s.toCharArray())
{
// some chars are not acceptable by any state
if(invalidChar(c))
return false;

if(Character.isDigit(c))
state = state.readDigit();
else if(c == ' ')
state = state.readSpace();
else if(c == '+')
state = state.readPlus();
else if(c == '-')
state = state.readMinus();
else if(c == '.')
state = state.readPoint();
else if(c == 'e' || c == 'E')
state = state.readE();

if(!state.isValid())
return false;
}
state = state.readEnd();
return state == State.EndState;
}
}

【在 f*****u 的大作中提到】
: 这个用finite state machine做的方法谁能给个代码链接?学习下。
b******g
发帖数: 3616
72
跪了。。。自动机的方法太高深了

【在 w*****j 的大作中提到】
: 用自动机写的
: 求批判
: 个人觉得自动机的好处是可视化,只要图画对,代码不容易写错
: corner case看得也比较清楚
: enum State
: {
: ErrorState
: {
: @Override
: public boolean isValid() { return false; }

w*****j
发帖数: 226
73
补充一句,自动机另一种写法是用二维表格来记录状态转换,更简洁,但是可读性更差
Q****a
发帖数: 296
74
可以用regex写吗? 面试官会允许么? 那样就几行
Z**0
发帖数: 1119
75
大家都没有修过编译原理?都是要要求你自己实现一个parser, 然后用再用yacc/bison
实现一次。
w*****t
发帖数: 485
76
shortest version, according to these guidelines and leetcode's offcial codes:
class Solution {
public:
bool isNumber(const char *s) {
if (!s) return false;
while (*s && isblank(*s)) ++s; // preceding spaces
if (*s && ('+' == *s || '-' == *s)) ++s; // preceding +/-
bool ret = false;
for (; *s && isdigit(*s); ret = true, ++s); // integer part
if (*s && '.' == *s) ++s;
for (; *s && isdigit(*s); ret = true, ++s); // decimal
if (ret && *s && 'e' == tolower(*s)) {
++s;
ret = false;
if (*s && ('+' == *s || '-' == *s)) ++s; // preceding +/-
for (; *s && isdigit(*s); ret = true, ++s); // integer part
}
while (*s && isblank(*s)) ++s; // tail spaces
return ret && !*s;
}
};
f*********0
发帖数: 17
77
跟我写的基本完全一样啊!
n1+n2==0判断是否valid太赞了!
另外,if,while后面只有一句的到底要不要加花括号啊?
class Solution {
public:
bool isNumber(const char *s) {
while (*s == ' ') s++;
if (*s == '+' || *s == '-') s++;
int n1 = 0;
while (*s <= '9' && *s >= '0') {
n1++;
s++;
}
if (*s == '.') s++;
int n2 = 0;
while (*s <= '9' && *s >= '0') {
n2++;
s++;
}
if (n1+n2 == 0) return false;
if (*s == 'e' || *s == 'E') {
s++;
if (*s == '+' || *s == '-') s++;
int n3 = 0;
while (*s <= '9' && *s >= '0') {
s++;
n3++;
}
if (n3 == 0) return false;
}
while (*s == ' ') s++;
return *s == '
s**x
发帖数: 7506
78
这好像是俺刷题时唯一自己想出来解法的题。
x*****a
发帖数: 610
79
你是在开玩笑?
Leetcode很多简单题三五行代码就写出来的你不会做偏偏会做这个?

【在 s**x 的大作中提到】
: 这好像是俺刷题时唯一自己想出来解法的题。
p*****p
发帖数: 379
80
public class Solution {

int[][] stateTrans = {
{1, 2, 3, -1, -1},
{1, -1, 4, 5, -1},
{1, -1, 3, -1, -1},
{4, -1, -1, -1, -1},
{4, -1, -1, 5, -1},
{7, 6, -1, -1, -1},
{7, -1, -1, -1, -1},
{7, -1, -1, -1, -1}
};

public boolean isNumber(String s) {
int state = 0;
s = s.trim();
for (int i = 0; i < s.length(); i++) {
state = stateTrans[state][getCharGroup(s.charAt(i))];
if (state == -1) {
return false;
}
}
return state == 7 || state == 4 || state == 1;
}

private int getCharGroup(char c) {
if (c >= '0' && c <= '9') {
return 0;
}
else if (c == '-' || c == '+') {
return 1;
}
else if (c == '.') {
return 2;
}
else if (c == 'e' || c == 'E') {
return 3;
}
return 4;
}
}
1 (共1页)
进入JobHunting版参与讨论
相关主题
Isomorphic Strings 的单Hashmap解法valid number这道题看到有人用有限状态机做 太牛不敢看
java 基本问题如何实现线程安全的哈希表
leetcode是不是最近有点问题?一道算法题
问个Java的HashSet.contains的问题新鲜Amazon面经(附参考答案) 顺便求各种大公司refer
写了一下leetcode上Valid Number,用boolean表示一些状态是不是比较简单Programming interview exposed 上面的那道NULL or Cycle的linked list题
L二电面据,附面经求教一个题目,sudoku 下面代码哪里错了。。。
用有限状态机写了一下leetcode valid numberLeetcode Timeout
L家电面Interleave Strings那个题目有O(n)时间 O(1)空间算法么?
相关话题的讨论汇总
话题: state话题: return话题: override话题: public话题: readdigit