文档章节

LeetCode:Valid Number - 判断字符串中内容是否为数字

北风其凉
 北风其凉
发布于 2015/09/19 13:51
字数 1166
阅读 595
收藏 0

1、题目名称

Valid Number(判断字符串中内容是否为数字)

2、题目地址

https://leetcode.com/problems/valid-number/

3、题目内容

英文:Validate if a given string is numeric.

中文:给出一个字符串,检查这个字符串中内容是否是一个数字

例如:“0”、“ 0.1”、“2e10”是数字,“abc”、“1 a”不是数字

4、解题方法1

使用正则表达式检查字符串是一个比较好的方法,正则表达式的结构如下图所示:

对应的正则表达式为:^([+-])?((\d+)(\.)?(\d+)?|(\d+)?(\.)?(\d+))(e([+-])?(\d+))?$

Java代码如下,注意为了让编译器不把字符“\”识别为转义字符,须将“\”转换为“\\”使用。

import java.util.regex.Matcher;
import java.util.regex.Pattern;

/**
 * 功能说明:LeetCode 65 - Valid Number
 * 开发人员:Tsybius2014
 * 开发时间:2015年9月18日
 */
public class Solution {
    
    /**
     * 判断指定字符串是否为数字
     * @param s 字符串
     * @return true:是数字 false:不是数字
     */
    public boolean isNumber(String s) {
        
        s = s.trim();
        if (s.isEmpty()) {
            return false;
        }

        //正则匹配
        Pattern p = Pattern.compile(
            "^([+-])?((\\d+)(\\.)?(\\d+)?|(\\d+)?(\\.)?(\\d+))(e([+-])?(\\d+))?$");   
        Matcher m = p.matcher(s);   
        if (m.find()) {
            return true;
        }
        
        return false;
    }
}

5、解题方法2

上面的方法我在OJ上运行花了484ms,虽然代码很清晰,代码长度也控制在很短的范围,但使用时间比较长。如果希望提高速度,可以使用有限状态机来处理这个问题。

状态机各状态图如下:

(其中每个状态接收到额外输入时都会跳转到FAILURE状态)

一段实现此功能的Java代码如下,这段代码在OJ上的效率为316ms。

/**
 * 功能说明:LeetCode 65 - Valid Number
 * 开发人员:Tsybius2014
 * 开发时间:2015年9月19日
 */
public class Solution {
    
    /**
     * 判断指定字符串是否为数字
     * @param s 字符串
     * @return true:是数字 false:不是数字
     */
    public boolean isNumber(String s) {
        
        s = s.trim(); 
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == 'x') {
                return false;
            }
        }
        s = s + 'x'; //x为标记字符串结束的字符
        
        State curState = State.STATE_BEGIN;
        for (int i = 0; i < s.length(); i++) {
            curState = getNextState(curState, s.charAt(i));
            if (curState == State.STATE_SUCCESS) {
                return true;
            } else if (curState == State.STATE_FAILURE) {
                return false;
            }
        }
        
        return false;
    }
    
    //状态枚举
    private enum State {

        //启动
        STATE_BEGIN,
        //正负号
        STATE_SIGN,
        //整数部分
        STATE_NUM_INT,
        //小数点1
        STATE_DOT1,
        //小数点2
        STATE_DOT2,
        //小数部分
        STATE_NUM_DEC,
        //指数符号e
        STATE_E,
        //指数正负号
        STATE_SIGN_E,
        //指数数字
        STATE_NUM_E,
        //正常结束
        STATE_SUCCESS,
        //异常结束
        STATE_FAILURE
        
    };
    
    /**
     * 根据当前字符与当前状态获取下一个状态
     * @param state
     * @param ch
     * @return
     */
    private State getNextState(State state, char ch) {
        
        switch (state) {
        case STATE_BEGIN: 
            return getNextStateBegin(ch);
        case STATE_SIGN:
            return getNextStateSign(ch);
        case STATE_NUM_INT:
            return getNextStateNumInt(ch);
        case STATE_DOT1:
            return getNextStateDot1(ch);
        case STATE_DOT2:
            return getNextStateDot2(ch);
        case STATE_NUM_DEC:
            return getNextStateNumDec(ch);
        case STATE_E:
            return getNextStateE(ch);
        case STATE_SIGN_E:
            return getNextStateSignE(ch);
        case STATE_NUM_E:
            return getNextStateNumE(ch);
        case STATE_SUCCESS:
            return State.STATE_SUCCESS;
        case STATE_FAILURE:
            return State.STATE_FAILURE;
        default:
            break;
        }
        
        return State.STATE_FAILURE;
    }
    
    /**
     * 初始状态
     * @param ch 输入字符
     * @return 下一个状态
     */
    private State getNextStateBegin(char ch) {
        switch (ch) {
        case '0':
        case '1':
        case '2':
        case '3':
        case '4':
        case '5':
        case '6':
        case '7':
        case '8':
        case '9':
            return State.STATE_NUM_INT;
        case '+':
        case '-':
            return State.STATE_SIGN;
        case '.':
            return State.STATE_DOT1;
        default:
            return State.STATE_FAILURE;
        }
    }

    /**
     * 正负号
     * @param ch 输入字符
     * @return 下一个状态
     */
    private State getNextStateSign(char ch) {
        switch (ch) {
        case '0':
        case '1':
        case '2':
        case '3':
        case '4':
        case '5':
        case '6':
        case '7':
        case '8':
        case '9':
            return State.STATE_NUM_INT;
        case '.':
            return State.STATE_DOT1;
        default:
            return State.STATE_FAILURE;
        }
    }

    /**
     * 整数部分
     * @param ch 输入字符
     * @return 下一个状态
     */
    private State getNextStateNumInt(char ch) {
        switch (ch) {
        case '0':
        case '1':
        case '2':
        case '3':
        case '4':
        case '5':
        case '6':
        case '7':
        case '8':
        case '9':
            return State.STATE_NUM_INT;
        case '.':
            return State.STATE_DOT2;
        case 'e':
            return State.STATE_E;
        case 'x':
            return State.STATE_SUCCESS;
        default:
            return State.STATE_FAILURE;
        }
    }

    /**
     * 小数点1
     * @param ch 输入字符
     * @return 下一个状态
     */
    private State getNextStateDot1(char ch) {
        switch (ch) {
        case '0':
        case '1':
        case '2':
        case '3':
        case '4':
        case '5':
        case '6':
        case '7':
        case '8':
        case '9':
            return State.STATE_NUM_DEC;
        default:
            return State.STATE_FAILURE;
        }
    }

    /**
     * 小数点2
     * @param ch 输入字符
     * @return 下一个状态
     */
    private State getNextStateDot2(char ch) {
        switch (ch) {
        case '0':
        case '1':
        case '2':
        case '3':
        case '4':
        case '5':
        case '6':
        case '7':
        case '8':
        case '9':
            return State.STATE_NUM_DEC;
        case 'e':
            return State.STATE_E;
        case 'x':
            return State.STATE_SUCCESS;
        default:
            return State.STATE_FAILURE;
        }
    }

    /**
     * 小数部分
     * @param ch 输入字符
     * @return 下一个状态
     */
    private State getNextStateNumDec(char ch) {
        switch (ch) {
        case '0':
        case '1':
        case '2':
        case '3':
        case '4':
        case '5':
        case '6':
        case '7':
        case '8':
        case '9':
            return State.STATE_NUM_DEC;
        case 'e':
            return State.STATE_E;
        case 'x':
            return State.STATE_SUCCESS;
        default:
            return State.STATE_FAILURE;
        }
    }

    /**
     * 指数符号e
     * @param ch 输入字符
     * @return 下一个状态
     */
    private State getNextStateE(char ch) {
        switch (ch) {
        case '0':
        case '1':
        case '2':
        case '3':
        case '4':
        case '5':
        case '6':
        case '7':
        case '8':
        case '9':
            return State.STATE_NUM_E;
        case '+':
        case '-':
            return State.STATE_SIGN_E;
        default:
            return State.STATE_FAILURE;
        }
    }

    /**
     * 指数正负号
     * @param ch 输入字符
     * @return 下一个状态
     */
    private State getNextStateSignE(char ch) {
        switch (ch) {
        case '0':
        case '1':
        case '2':
        case '3':
        case '4':
        case '5':
        case '6':
        case '7':
        case '8':
        case '9':
            return State.STATE_NUM_E;
        default:
            return State.STATE_FAILURE;
        }
    }

    /**
     * 指数数字
     * @param ch 输入字符
     * @return 下一个状态
     */
    private State getNextStateNumE(char ch) {
        switch (ch) {
        case '0':
        case '1':
        case '2':
        case '3':
        case '4':
        case '5':
        case '6':
        case '7':
        case '8':
        case '9':
            return State.STATE_NUM_E;
        case 'x':
            return State.STATE_SUCCESS;
        default:
            return State.STATE_FAILURE;
        }
    }
}

END

© 著作权归作者所有

北风其凉

北风其凉

粉丝 118
博文 498
码字总数 463468
作品 4
朝阳
程序员
私信 提问
每日算法之LeetCode 125:Valid Palindrome(有效回文)

LeetCode 125:Valid Palindrome(有效回文) Q:Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases. Note: For the purpose ......

錦小白
2018/08/18
0
0
LeetCode日记2

LeetCode-5 思路: (1)最后用子字符串操作返回string。 return s.substr(startpos, maxlength); (2)回文串的判断: 1)首先找出回文串中间连续的重复的字符。 2)再向两边进行判断 (3...

fxdhdu
2015/10/19
53
0
LeetCode:Palindrome Number - 回文数

1、题目名称 Palindrome Number(回文数) 2、题目地址 https://leetcode.com/problems/palindrome-number 3、题目内容 英文:Determine whether an integer is a palindrome. Do this witho......

北风其凉
2015/09/24
109
0
LeetCode:Valid Palindrome - 回文字符串

1、题目名称 Valid Palindrome(回文字符串) 2、题目地址 https://leetcode.com/problems/valid-palindrome/ 3、题目内容 英文:Given a string, determine if it is a palindrome, consid......

北风其凉
2015/08/05
0
0
Leetcode日记6

(2015/11/28) LeetCode 303 Range Sum Query - Immutable:(Easy) 1)超时的算法:每次调用sumRange函数进行一次累加运算。 2)不超时的算法:改变数组的内容,存储从0下标到当前下标所有...

fxdhdu
2015/11/28
73
0

没有更多内容

加载失败,请刷新页面

加载更多

RS-232、RS422和RS-485的区别和各自的实现方式

一、殊途同归 RS-232、RS422和RS-485 均属于UART是通用异步收发传输器(Universal Asynchronous Receiver/Transmitter),仅用两根信号线(Rx 和Tx)就可以完成通信过程; 而由于各自使用的电...

rainbowcode
43分钟前
0
0
spring 本类中方法调用另外一个方法事务不生效

1、在spring配置文件中添加 <aop:aspectj-autoproxy expose-proxy="true" proxy-target-class="true" />声明自动代理 <!-- 标识通过aop框架暴露该代理,aopContext能够访问. --> proxy-targe......

重城重楼
49分钟前
5
0
项目 banner 乱弹

------------------------------------------ 村上春树 ------------------------------------- 如果我爱你,而你也正巧爱我,你头发乱了的时候,我会笑笑地替你拨一拨,然后手还留恋地在你...

宿小帅
今天
3
0
PHP获取未来七天的日期和星期

php获取未来七天的日期和星期代码 第一步:获取需要天数的日期,然后调用函数 //获取未来七天的日期 for($i=1;$i<8;$i++){ $dateArray[$i]=date('Y-m-d',strtotime(d...

一只懒猫-
今天
2
0
总结:IO模型

分类 多路复用 参考文章: https://www.jianshu.com/p/6a6845464770 https://www.cnblogs.com/zingp/p/6863170.html https://blog.csdn.net/sehanlingfeng/article/details/78920423......

浮躁的码农
今天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部