剑指Offer系列（java版，详细解析）20.表示数值的字符串

Bertha 。 2022-11-09 01:27 138阅读 0赞

# 题目描述 #

#### [剑指 Offer 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+)?");
        }
    }

# 补充 #

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

[Offer 20.]: https://leetcode-cn.com/problems/biao-shi-shu-zhi-de-zi-fu-chuan-lcof/
[Picture1.png]: /images/20221023/0afdc2220bb0402284f8bbce9b99b49f.png