z*******3
发帖数: 13709 | 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;i
if(!Character.isDigit(s.charAt(i))) return false;
}
return true;
}
} |
p*****2
发帖数: 21240 | |
z*******3
发帖数: 13709 | 3 “面试用c类语言就是自虐”
--北京二爷
【在 p*****2 的大作中提到】
: 大牛用C写一个看看？
|
s********x
发帖数: 914 | 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的方法
|
A******g
发帖数: 612 | 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的方法
|
u*****o
发帖数: 1224 | |
s********x
发帖数: 914 | 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个字符
|
c********p
发帖数: 1969 | 8 这个id是你的马甲？？
这个题。。。我做的乱七八糟的。。。 |
A******g
发帖数: 612 | 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) {
|
s********x
发帖数: 914 | 10 我不认为那是valid number，应该是0.33
【在 A******g 的大作中提到】
: 大牛，随便看了一眼，至少过不了 +.33 这样的
|
|
|
A******g
发帖数: 612 | 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
|
s********x
发帖数: 914 | 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
|
z*******3
发帖数: 13709 | 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
|
z*******o
发帖数: 4773 | |
A******g
发帖数: 612 | 15 大牛，哥们我并不是不会写这题，只是觉得这题要一次bugfree或者几乎bugfree还是有
难度的, 背题不至于，上过编译原理或者自动机和形式语言课的看一眼就能写出这个表
达式，基本功而已
【在 z*******3 的大作中提到】
: leetcode上不让用Pattern.matches(String,String)
: 这题就算要用regulare expression
: 也没有必要跟这个公式死磕
: 正则表达式写is integer/is double这些方法都超简单，也很好记
: 拆开，一点一点实现
: 上来就给一个复杂的公式，那多半就是背题背的
|
z*******3
发帖数: 13709 | 16 没有说你不懂啊，只是条条大路通罗马
考察面不一样，这种题目如果出在一般的developer面前
就是实现题
编译原理现在被从核心课中拿掉了
对于一些major比如software engineering来说
对于ce的同学可能还比较重要
形式语言应该一直都是选修课
【在 A******g 的大作中提到】
: 大牛，哥们我并不是不会写这题，只是觉得这题要一次bugfree或者几乎bugfree还是有
: 难度的, 背题不至于，上过编译原理或者自动机和形式语言课的看一眼就能写出这个表
: 达式，基本功而已
|
v*****d
发帖数: 348 | 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的方法
|
d******e
发帖数: 164 | 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写一个看看？
|
A******g
发帖数: 612 | 19 所以说这题对我等ds是必杀题，想放我等过也行，不想放也很容易
当然对大牛显然不是问题，绝对秒杀
这题99.9999%的某文明古国的人肯定做不对
【在 z*******3 的大作中提到】
: 没有说你不懂啊，只是条条大路通罗马
: 考察面不一样，这种题目如果出在一般的developer面前
: 就是实现题
: 编译原理现在被从核心课中拿掉了
: 对于一些major比如software engineering来说
: 对于ce的同学可能还比较重要
: 形式语言应该一直都是选修课
|
x*****0
发帖数: 452 | |
