Redian新闻
>
我觉得valid number其实并不难
avatar
我觉得valid number其实并不难# JobHunting - 待字闺中
z*3
1
五个步骤
0)预处理,把输入的string给trim一下,这个适用于任何string作为输入的问题
1)写出is unsigned integer的方法
2)写出is integer的方法,借用步骤1写好的方法,加一个判断是不是+-号开头
3)写出is unsigned double的方法,借用步骤1写好的方法
这里有一个很特殊的corner case,就是.单独出现的情况,其实整个流程就这一个
corner case
4)写出is double的方法,借用步骤3写好的方法
5)然后valid number根据e做切割
e后面必需是integer,用步骤2的方法
e前面必需是double,用步骤4的方法
搞定
看起来很长,其实没啥东西,甚至没有脑筋急转弯的地方,就一个corner case记住就
好了
如果可以自由选择java类库的话,double.parseDouble(String)和integer.parseInt(
String)
加上try catch exception block,简简单单搞定一大串内容
废话说完咯,以下是代码
public class Solution {
public boolean isNumber(String s) {
// Start typing your Java solution below
// DO NOT write main() function
s=s.trim();
if(s.indexOf('e')==-1){
return isDouble(s);
}else{
return isDouble(s.substring(0,s.indexOf('e')))
&& isInteger(s.substring(s.indexOf('e')+1));
}
}
private boolean isDouble(String s){
if(s.startsWith("+")||s.startsWith("-")) return isUnsignedDouble(s.
substring(1));
else return isUnsignedDouble(s);
}
private boolean isUnsignedDouble(String s){
if(s.indexOf('.')==-1){
return isUnsignedInteger(s);
}else{
if(s.length()==1) return false;
int i = s.indexOf('.');
return (s.substring(0,i).equals("")||isUnsignedInteger(s.
substring(0,i)))&&
(s.substring(i+1).equals("")||isUnsignedInteger(s.substring(i+1)
));
}
}
private boolean isInteger(String s){
if(s.startsWith("+")||s.startsWith("-")) return isUnsignedInteger(s.
substring(1));
else return isUnsignedInteger(s);
}
private boolean isUnsignedInteger(String s){
if(s.length()==0) return false;
for(int i=0;iif(!Character.isDigit(s.charAt(i))) return false;
}
return true;
}
}
avatar
p*2
2
大牛用C写一个看看?
avatar
z*3
3
“面试用c类语言就是自虐”
--北京二爷

【在 p*****2 的大作中提到】
: 大牛用C写一个看看?
avatar
s*x
4
建议不要用substring, pass in original string and start/end index

【在 z*******3 的大作中提到】
: 五个步骤
: 0)预处理,把输入的string给trim一下,这个适用于任何string作为输入的问题
: 1)写出is unsigned integer的方法
: 2)写出is integer的方法,借用步骤1写好的方法,加一个判断是不是+-号开头
: 3)写出is unsigned double的方法,借用步骤1写好的方法
: 这里有一个很特殊的corner case,就是.单独出现的情况,其实整个流程就这一个
: corner case
: 4)写出is double的方法,借用步骤3写好的方法
: 5)然后valid number根据e做切割
: e后面必需是integer,用步骤2的方法

avatar
A*g
5
大牛,你的做法写起来简单但不是算法最优,
一次indexOf扫过整个String
这样整个String扫了很多次了
最优的算法就是实现一个dfa,
整个string只扫一次,时间n,空间n,不好写的
其实用scheme (number? x) 连空格11个字符

【在 z*******3 的大作中提到】
: 五个步骤
: 0)预处理,把输入的string给trim一下,这个适用于任何string作为输入的问题
: 1)写出is unsigned integer的方法
: 2)写出is integer的方法,借用步骤1写好的方法,加一个判断是不是+-号开头
: 3)写出is unsigned double的方法,借用步骤1写好的方法
: 这里有一个很特殊的corner case,就是.单独出现的情况,其实整个流程就这一个
: corner case
: 4)写出is double的方法,借用步骤3写好的方法
: 5)然后valid number根据e做切割
: e后面必需是integer,用步骤2的方法

avatar
u*o
6
MARK一下,以后看到这题再仔细看。
avatar
s*x
7
用同样的思路写了一个,没有测,可能有小bug。但应该是只扫一遍。
private static boolean isWhiteSpace(char c) {
if (c == ' ' || c == '\t') {
return true;
}

return false;
}

public static boolean isNumber(String s) {
if (s == null || s.length() == 0) {
throw new IllegalArgumentException();
}
int start = 0, end = s.length() - 1;
// trim
while ((end-1) >= 0 && isWhiteSpace(s.charAt(end))) {
end--;
}
while ((start+1) <= end && isWhiteSpace(s.charAt(start))) {
start++;
}
// skip beginning + or -
if ((start+1) <= end && s.charAt(start) == '+' || s.charAt(start) == '-') {
start++;
}
start = isInteger(start, end, s);
if (start < 0) {
return false;
}
if (start+1 <= end && s.charAt(start) == '.') {
start++; // now it's a double
}
start = isInteger(start, end, s);
if (start < 0) {
return false;
}
if (start+1 <= end && s.charAt(start) == 'e') {
start++; // now the rest has to be integer
}
start = isInteger(start, end, s);
return start >0 && start == end && s.charAt(start) <= '9' && s.charAt(
start) >= '0';
}
private static int isInteger(int start, int end, String s) {
if (start > end || s.charAt(start) < '0' || s.charAt(start) > '9') {
return -1; // invalid
}
while ((start+1) <= end && s.charAt(start) <= '9' && s.charAt(start) >= '0
') {
start++;
}
return start;
}

【在 A******g 的大作中提到】
: 大牛,你的做法写起来简单但不是算法最优,
: 一次indexOf扫过整个String
: 这样整个String扫了很多次了
: 最优的算法就是实现一个dfa,
: 整个string只扫一次,时间n,空间n,不好写的
: 其实用scheme (number? x) 连空格11个字符

avatar
c*p
8
这个id是你的马甲??
这个题。。。我做的乱七八糟的。。。
avatar
A*g
9
大牛,随便看了一眼,至少过不了 +.33 这样的

【在 s********x 的大作中提到】
: 用同样的思路写了一个,没有测,可能有小bug。但应该是只扫一遍。
: private static boolean isWhiteSpace(char c) {
: if (c == ' ' || c == '\t') {
: return true;
: }
:
: return false;
: }
:
: public static boolean isNumber(String s) {

avatar
s*x
10
我不认为那是valid number,应该是0.33

【在 A******g 的大作中提到】
: 大牛,随便看了一眼,至少过不了 +.33 这样的
avatar
A*g
11
大牛,
我们面试时不能以我们认为为准吧?
leetcode认为,几乎所有的programming language都认为比如java,python
这题各种奇怪的边角情况才是难点
比如:
+.33
3.
.3e.3
+.3e10
-3.e.4
这个正则表达式是
Space := ('n'|'t'|' ')
Sign := ('-'|'+')
DOT := '.'
Digit := ('0'|...|'9')
NUMBER := Space* Sign? ((Digit Digit* DOT? Digit*)|(Digit* DOT? Digit Digit*
)) (Space* | (E Sign? ((Digit Digit* DOT? Digit*)|(Digit* DOT? Digit Digit*
Space*))))
不是寥寥几行就能搞定的, 我认为用java的正则表达式靠谱一点

【在 s********x 的大作中提到】
: 我不认为那是valid number,应该是0.33
avatar
s*x
12
if you insist:
public static boolean isNumber(String s) {
if (s == null || s.length() == 0) {
throw new IllegalArgumentException();
}
int start = 0, end = s.length() - 1;
// trim
while ((end-1) >= 0 && isWhiteSpace(s.charAt(end))) {
end--;
}
while ((start+1) <= end && isWhiteSpace(s.charAt(start))) {
start++;
}
// skip beginning + or -
if ((start+1) <= end && s.charAt(start) == '+' || s.charAt(start) == '-') {
start++;
}
start = isInteger(start, end, s);
if (start < 0) {
return false;
}
boolean hasDot = false;
if (start+1 <= end && s.charAt(start) == '.') {
start++; // now it's a double
hasDot = true;
}
start = isInteger(start, end, s);
if (start < 0) {
return false;
}
if (start+1 <= end && s.charAt(start) == 'e') {
start++; // now the rest has to be integer
}
start = isInteger(start, end, s);
if (start < 0) {
return false;
}
if (s.charAt(start) <= '9' && s.charAt(start) >= '0') {
return true;
}
if (!hasDot && s.charAt(start) == '.') {
return true; // dot occurs only once
}
return false;
}
private static int isInteger(int start, int end, String s) {
if (s.charAt(start) == '.' || s.charAt(start) == 'e') {
return start;
}
if (start > end || s.charAt(start) < '0' || s.charAt(start) > '9') {
return -1; // invalid
}
while ((start+1) <= end && s.charAt(start) <= '9' && s.charAt(start) >= '0
') {
start++;
}
return start;
}

【在 A******g 的大作中提到】
: 大牛,
: 我们面试时不能以我们认为为准吧?
: leetcode认为,几乎所有的programming language都认为比如java,python
: 这题各种奇怪的边角情况才是难点
: 比如:
: +.33
: 3.
: .3e.3
: +.3e10
: -3.e.4

avatar
z*3
13
leetcode上不让用Pattern.matches(String,String)
这题就算要用regulare expression
也没有必要跟这个公式死磕
正则表达式写is integer/is double这些方法都超简单,也很好记
拆开,一点一点实现
上来就给一个复杂的公式,那多半就是背题背的

【在 A******g 的大作中提到】
: 大牛,
: 我们面试时不能以我们认为为准吧?
: leetcode认为,几乎所有的programming language都认为比如java,python
: 这题各种奇怪的边角情况才是难点
: 比如:
: +.33
: 3.
: .3e.3
: +.3e10
: -3.e.4

avatar
z*o
14
不错
avatar
A*g
15
大牛,哥们我并不是不会写这题,只是觉得这题要一次bugfree或者几乎bugfree还是有
难度的, 背题不至于,上过编译原理或者自动机和形式语言课的看一眼就能写出这个表
达式,基本功而已

【在 z*******3 的大作中提到】
: leetcode上不让用Pattern.matches(String,String)
: 这题就算要用regulare expression
: 也没有必要跟这个公式死磕
: 正则表达式写is integer/is double这些方法都超简单,也很好记
: 拆开,一点一点实现
: 上来就给一个复杂的公式,那多半就是背题背的

avatar
z*3
16
没有说你不懂啊,只是条条大路通罗马
考察面不一样,这种题目如果出在一般的developer面前
就是实现题
编译原理现在被从核心课中拿掉了
对于一些major比如software engineering来说
对于ce的同学可能还比较重要
形式语言应该一直都是选修课

【在 A******g 的大作中提到】
: 大牛,哥们我并不是不会写这题,只是觉得这题要一次bugfree或者几乎bugfree还是有
: 难度的, 背题不至于,上过编译原理或者自动机和形式语言课的看一眼就能写出这个表
: 达式,基本功而已

avatar
v*d
17
这题俺看了五分钟直接pass了,没有欲望写

【在 z*******3 的大作中提到】
: 五个步骤
: 0)预处理,把输入的string给trim一下,这个适用于任何string作为输入的问题
: 1)写出is unsigned integer的方法
: 2)写出is integer的方法,借用步骤1写好的方法,加一个判断是不是+-号开头
: 3)写出is unsigned double的方法,借用步骤1写好的方法
: 这里有一个很特殊的corner case,就是.单独出现的情况,其实整个流程就这一个
: corner case
: 4)写出is double的方法,借用步骤3写好的方法
: 5)然后valid number根据e做切割
: e后面必需是integer,用步骤2的方法

avatar
d*e
18
抛个砖:
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' && num) {
s++, num = false;
if (*s == '+' || *s == '-') s++;
while (isdigit(*s)) s++, num = true;
}
while (isspace(*s)) s++;
return !*s && num;
}

【在 p*****2 的大作中提到】
: 大牛用C写一个看看?
avatar
A*g
19
所以说这题对我等ds是必杀题,想放我等过也行,不想放也很容易
当然对大牛显然不是问题,绝对秒杀
这题99.9999%的某文明古国的人肯定做不对

【在 z*******3 的大作中提到】
: 没有说你不懂啊,只是条条大路通罗马
: 考察面不一样,这种题目如果出在一般的developer面前
: 就是实现题
: 编译原理现在被从核心课中拿掉了
: 对于一些major比如software engineering来说
: 对于ce的同学可能还比较重要
: 形式语言应该一直都是选修课

avatar
x*0
20
mark
相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。