程序员社区

剑指Offer系列(java版,详细解析)20.表示数值的字符串

题目描述

剑指 Offer 20. 表示数值的字符串

难度中等159

请实现一个函数用来判断字符串是否表示数值(包括整数和小数)。例如,字符串"+100"、“5e2”、"-123"、“3.1416”、"-1E-16"、“0123"都表示数值,但"12e”、“1a3.14”、“1.2.3”、"±5"及"12e+5.4"都不是。

测试用例

  • 功能测试(正数或者负数;包含或则不包含正数部分的数值;包含或者不包含小数部分的数字;包含或者不包含指数部分的数值;各种不能表达有效数值的字符串)
  • 特殊输入测试(输入字符串是空null或者空字符串)

题目考点

  • 考察应聘者对字符串的编程能力。
  • 考察应聘者分析问题的能力。而面试官希望应聘者能够从不同类型的数值中分析出规律。
  • 考察应聘者思维的全面性。在应聘者写完代码之后,面试官会期待应聘者尽量完备地想出所有可能的测试用例。

解题思路

有限状态自动机

Picture1.png

class Solution {
   
    public boolean isNumber(String s) {
   
        Map[] states = {
   
            new HashMap<>() {
   {
    put(' ', 0); put('s', 1); put('d', 2); put('.', 4); }}, // 0.
            new HashMap<>() {
   {
    put('d', 2); put('.', 4); }},                           // 1.
            new HashMap<>() {
   {
    put('d', 2); put('.', 3); put('e', 5); put(' ', 8); }}, // 2.
            new HashMap<>() {
   {
    put('d', 3); put('e', 5); put(' ', 8); }},              // 3.
            new HashMap<>() {
   {
    put('d', 3); }},                                        // 4.
            new HashMap<>() {
   {
    put('s', 6); put('d', 7); }},                           // 5.
            new HashMap<>() {
   {
    put('d', 7); }},                                        // 6.
            new HashMap<>() {
   {
    put('d', 7); put(' ', 8); }},                           // 7.
            new HashMap<>() {
   {
    put(' ', 8); }}                                         // 8.
        };
        int p = 0;
        char t;
        for(char c : s.toCharArray()) {
   
            if(c >= '0' && c <= '9') t = 'd';
            else if(c == '+' || c == '-') t = 's';
            else if(c == 'e' || c == 'E') t = 'e';
            else if(c == '.' || c == ' ') t = c;
            else t = '?';
            if(!states[p].containsKey(t)) return false;
            p = (int)states[p].get(t);
        }
        return p == 2 || p == 3 || p == 7 || p == 8;
    }
}

非正则表达式解法

首先仔细表示数值的字符串的模式A[.[B]][e|EC]或者.B[e|EC]。其中A为数值的整数部分,B紧跟着小数点为数值的小数部分,C紧跟着’e’或者‘E’为数值的指数部分。在小数里可能没有数值的整数部分。例如,小数.123等于0.123。因此A部分不是必须,如果一个数没有整数部分,那么它的小数部分不能为空。

上诉A和C都是可能以‘+’或者‘-’开头的0-9的数字串;B也是0-9的数位串,单前面不能有正负号。

判断一个字符串是否符合上述模式时,首先尽可能多地扫描0-9的数位(有可能在起始处有‘+’或者‘-’),也就是前面模式中表示数值的A部分,如果遇到小数点‘.’,则开始扫描数值小数部分的B部分。如果遇到’e’或者‘E’,则开始扫描数值指数的C部分。

课本参考解题

非正则表达式解法

/**
 * Author:Viper
 * Data:2021/3/14
 * description:
 */
public class problem20 {
        private int i = 0;
        public boolean isNumber(String s) {
            char[] str=s.trim().toCharArray();
            if (str == null || str.length < 0) {
                return false;
            }
            // 1. 扫描A

            boolean numberic = scanInteger(str);
            // 2. 扫描B
            if (i < str.length && str[i] == '.') {
                i++;
                // 小数后面可以没有数字
                numberic = scanUnSignedInteger(str) || numberic;
            }
            // 3. 扫描C
            if (i < str.length && (str[i] == 'e' || str[i] == 'E')) {
                i++;
                // 出现e/E 后面必须跟数字
                numberic = scanInteger(str) && numberic;
            }

            return numberic && i == str.length;
        }
        private boolean scanInteger(char[] str) {
            if (i < str.length && (str[i] == '+' || str[i] == '-')) {
                i++;
            }
            return scanUnSignedInteger(str);
        }

        /**
         * 扫描无符号整数部分(在起始处不可能有‘+’或者‘-’)
         * @param str
         * @return
         */
        private boolean scanUnSignedInteger(char[] str) {
            // 用于对比是否符合
            int temp = i;
            while (i < str.length && str[i] >= '0' && str[i] <= '9') {
                i++;
            }
            return i > temp;
        }

}

正则表达式解法

/**
 * 表示数值的字符串
 *
 */
public class Solution2 {
    /**
     * 正则表达式解法
     *
     * @param str
     * @return
     */
    public boolean isNumeric(char[] str) {
        // 防止特殊输入
        if (str == null || str.length < 0) {
            return false;
        }
        return new String(str).matches("[+-]?\\d*(\\.\\d+)?([eE][+-]?\\d+)?");
    }
}

补充

字符串选择和判断可以考虑正则表达式

赞(0) 打赏
未经允许不得转载:IDEA激活码 » 剑指Offer系列(java版,详细解析)20.表示数值的字符串

一个分享Java & Python知识的社区