leetcode65.Valid Number

发表于 更新于 分类于 ，

题目要求

1
2
3
4
5
6
7
8
9
Validate if a given string is numeric.

Some examples:
"0" => true
" 0.1 " => true
"abc" => false
"1 a" => false
"2e10" => true
Note: It is intended for the problem statement to be ambiguous. You should gather all requirements up front before implementing one.

写一个算法 判断输入的字符串是否是数字。
这道题的需求给的较为模糊，对于什么是数字并没有给出明确的定义。这里我要给出几个特殊的情况来说明数字究竟是什么。

  1. 空值返回false
  2. 字符串前后的空白字符不影响字符串最终的结果
  3. 1.以及.1都是符合标准的小数，但是**.**不符合
  4. e的前后必须有数字，e前的数字可以为整数或是小数，e后的数字必须为正/负整数/0

思路一：正则表达式

关于正则表达式的入门，请参考我的前不久写的一篇博客。在还没有了解正则表达式的时候，我将数字分为三种

  1. 整数
  2. 小数
  3. 包含e

事实上啊，这是极为不合理的一种分类，因为它们之间从数字构成的角度来说相互包含，在判断时会造成代码的冗余。菜鸡版本代码如下： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public boolean isNumber(String s) {
    s = s.trim();
    if(s.contains("e")){
        String firstPart = s.substring(0, s.indexOf("e"));
        String secondPart = s.indexOf("e")+1 >= s.length() ? "" : s.substring(s.indexOf("e")+1);
        return (isInteger(firstPart) || isDouble(firstPart)) && isInteger(secondPart);
    }else if(s.contains(".")){
        return isDouble(s);
    }else{
        return isInteger(s);
    }
    
}

public boolean isDouble(String s){
    if(s.startsWith("-") || s.startsWith("+")){
        s = s.substring(1);
    }
    if(s.length() <= 1){
        return false;
    }
    return s.matches("^([0-9]*)?+\\.([0-9]*)$");
}

public boolean isInteger(String s){
    return s.matches("^(-|\\+)?([0-9]{1,})$");
}

在稍微深入的了解了正则表达式之后，我对于数字的判断有了新的认识，将数字先划分为两类：包含e以及不包含e。鉴于无论包含或是不包含e，e的前面都必须有数字。所以这时候再来分析e前数字的特性。e前数字可以为整数也可以为小数，但这里涉及到小数点时，又要重新考虑，毕竟.不可以单独存在，但是只要前后任何一个位置有数字，就可以称其为小数。这是我决定将小数点后没有数字的那一类字符串也划分到整数的部分，也就简化了我的正则表达式。完整的正则表达式为^ *[+-]?(([0-9]+\\.?)|([0-9]*\\.[0-9]+))(e[+-]?[0-9]+)? *$。
注意！正则表达式的开头和结尾均有空格
代码如下： 

1
2
3
public boolean isNumber2(String s){
    return s.matches("^ *[+-]?(([0-9]+\\.?)|([0-9]*\\.[0-9]+))(e[+-]?[0-9]+)? *$");
}

思路二：flags

一个完美的正则表达式带来的代码虽然只有一行，但是它的效率一般啊，我也很无奈啊。这时我参考了一下高效大神的代码。大神采用的思路就是利用各种flag结合字符串当前位置上的值来判断该字符串是否合理。代码如下： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
/**
 * We start with trimming.
 * If we see [0-9] we reset the number flags.
 * We can only see . if we didn't see e or ..
 * We can only see e if we didn't see e but we did see a number. We reset numberAfterE flag.
 * We can only see + and - in the beginning and after an e
 * any other character break the validation.
 * At the end it is only valid if there was at least 1 number and if we did see an e then a number after it as well.
 * So basically the number should match this regular expression:
 * [-+]?(([0-9]+(.[0-9]*)?)|.[0-9]+)(e[-+]?[0-9]+)?
 *
 *翻译：
 *如果我们看到数字，就将numberFlag设为true
 *如果看到小数点，则判断是否已有小数点或是e，因为e后只能有整数
 *e只能遇到一次，如果第一次遇到e但是没有遇到数字，则返回错误。遇到第一个e后，将numberAfterE flag标注为否以便判断后序是否有数字
 *正负号的位置只能位于最开始和e紧邻着右边那个位置
 */
public boolean isNumber3(String s){
    s = s.trim();
    boolean pointSeen = false;
    boolean eSeen = false;
    boolean numberSeen = false;
    boolean numberAfterE = true;
    for(int i=0; i<s.length(); i++) {
        //当前值为数字
        if('0' <= s.charAt(i) && s.charAt(i) <= '9') {
            numberSeen = true;
            numberAfterE = true;
        //遇到小数点
        } else if(s.charAt(i) == '.') {
            //已经遇到小数点或是e，则出错
            if(eSeen || pointSeen) {
                return false;
            }
            pointSeen = true;
        //遇到e
        } else if(s.charAt(i) == 'e') {
            //已经遇到e或是尚未遇到数字
            if(eSeen || !numberSeen) {
                return false;
            }
            numberAfterE = false;
            eSeen = true;
        //遇到正负号，只能在首位或是e后面
        } else if(s.charAt(i) == '-' || s.charAt(i) == '+') {
            if(i != 0 && s.charAt(i-1) != 'e') {
                return false;
            }
        //遇到其它符号一定是错的
        } else {
            return false;
        }
    }   
    //是否遇到小数点或是e均不重要
    return numberSeen && numberAfterE;
}

这里运用的flags的方法其实非常考验对需求的有效分类，尤其是对字符串中存在e的情况的判断。这种方式使用O(n)的时间复杂度实现判断。而在遇到存疑情况时，往往比正常的正则表达式更有效。