一、题目
1、算法题目
“给定一个字符串，判断是否是有效数字。”
题目链接：
来源：力扣（LeetCode）
链接：65. 有效数字 - 力扣（LeetCode） (leetcode-cn.com)
2、题目描述
有效数字（按顺序）可以分成以下几个部分：
- 1.一个 小数 或者 整数
- 2.（可选）一个 'e' 或 'E' ，后面跟着一个 整数
小数（按顺序）可以分成以下几个部分：
（可选）一个符号字符（'+' 或 '-'） 下述格式之一：
- 1.至少一位数字，后面跟着一个点 '.'
- 2.至少一位数字，后面跟着一个点 '.' ，后面再跟着至少一位数字
- 3.一个点 '.' ，后面跟着至少一位数字
整数（按顺序）可以分成以下几个部分：
（可选）一个符号字符（'+' 或 '-'） 至少一位数字 部分有效数字列举如下：
- ["2", "0089", "-0.1", "+3.14", "4.", "-.9", "2e10", "-90E3", "3e+7", "+6e-1", "53.5e93", "-123.456e789"]
部分无效数字列举如下：
- ["abc", "1a", "1e", "e3", "99e2.5", "--6", "-+3", "95a54e53"]
给你一个字符串 s ，如果 s 是一个 有效数字 ，请返回 true 。
示例 1： 输入： s = "0" 输出： true 复制代码
示例 2： 输入： s = "e" 输出： false 复制代码
二、解题
1、思路分析
这道题可以使用有限状态机的思路解决问题，有限状态机是一种计算模型，包含一系列的状态，然后根据不同的状态进行切换。
然后，就按顺序去读取字符串中的每一个字符，如果是实现约定好的庄毅规则，就从当前状态转移到下一个状态，状态转移完成后，就读取下一个字符。
当所有的字符串读取完毕，如果状态机处于正确状态就说明该字符串正确，否则，不正确。
2、代码实现
代码参考：
public class Solution { public bool IsNumber(string s) { Dictionary<State, Dictionary<CharType, State>> transfer = new Dictionary<State, Dictionary<CharType, State>>(); Dictionary<CharType, State> initialDictionary = new Dictionary<CharType, State> { {CharType.CHAR_NUMBER, State.STATE_INTEGER}, {CharType.CHAR_POINT, State.STATE_POINT_WITHOUT_INT}, {CharType.CHAR_SIGN, State.STATE_INT_SIGN} }; transfer.Add(State.STATE_INITIAL, initialDictionary); Dictionary<CharType, State> intSignDictionary = new Dictionary<CharType, State> { {CharType.CHAR_NUMBER, State.STATE_INTEGER}, {CharType.CHAR_POINT, State.STATE_POINT_WITHOUT_INT} }; transfer.Add(State.STATE_INT_SIGN, intSignDictionary); Dictionary<CharType, State> integerDictionary = new Dictionary<CharType, State> { {CharType.CHAR_NUMBER, State.STATE_INTEGER}, {CharType.CHAR_EXP, State.STATE_EXP}, {CharType.CHAR_POINT, State.STATE_POINT} }; transfer.Add(State.STATE_INTEGER, integerDictionary); Dictionary<CharType, State> pointDictionary = new Dictionary<CharType, State> { {CharType.CHAR_NUMBER, State.STATE_FRACTION}, {CharType.CHAR_EXP, State.STATE_EXP} }; transfer.Add(State.STATE_POINT, pointDictionary); Dictionary<CharType, State> pointWithoutIntDictionary = new Dictionary<CharType, State> { {CharType.CHAR_NUMBER, State.STATE_FRACTION} }; transfer.Add(State.STATE_POINT_WITHOUT_INT, pointWithoutIntDictionary); Dictionary<CharType, State> fractionDictionary = new Dictionary<CharType, State> { {CharType.CHAR_NUMBER, State.STATE_FRACTION}, {CharType.CHAR_EXP, State.STATE_EXP} }; transfer.Add(State.STATE_FRACTION, fractionDictionary); Dictionary<CharType, State> expDictionary = new Dictionary<CharType, State> { {CharType.CHAR_NUMBER, State.STATE_EXP_NUMBER}, {CharType.CHAR_SIGN, State.STATE_EXP_SIGN} }; transfer.Add(State.STATE_EXP, expDictionary); Dictionary<CharType, State> expSignDictionary = new Dictionary<CharType, State> { {CharType.CHAR_NUMBER, State.STATE_EXP_NUMBER} }; transfer.Add(State.STATE_EXP_SIGN, expSignDictionary); Dictionary<CharType, State> expNumberDictionary = new Dictionary<CharType, State> { {CharType.CHAR_NUMBER, State.STATE_EXP_NUMBER} }; transfer.Add(State.STATE_EXP_NUMBER, expNumberDictionary); int length = s.Length; State state = State.STATE_INITIAL; for (int i = 0; i < length; i++) { CharType type = ToCharType(s[i]); if (!transfer[state].ContainsKey(type)) { return false; } else { state = transfer[state][type]; } } return state == State.STATE_INTEGER || state == State.STATE_POINT || state == State.STATE_FRACTION || state == State.STATE_EXP_NUMBER || state == State.STATE_END; } CharType ToCharType(char ch) { if (ch >= '0' && ch <= '9') { return CharType.CHAR_NUMBER; } else if (ch == 'e' || ch == 'E') { return CharType.CHAR_EXP; } else if (ch == '.') { return CharType.CHAR_POINT; } else if (ch == '+' || ch == '-') { return CharType.CHAR_SIGN; } else { return CharType.CHAR_ILLEGAL; } } enum State { STATE_INITIAL, STATE_INT_SIGN, STATE_INTEGER, STATE_POINT, STATE_POINT_WITHOUT_INT, STATE_FRACTION, STATE_EXP, STATE_EXP_SIGN, STATE_EXP_NUMBER, STATE_END } enum CharType { CHAR_NUMBER, CHAR_EXP, CHAR_POINT, CHAR_SIGN, CHAR_ILLEGAL } } 复制代码
网络异常，图片无法展示
|
3、时间复杂度
时间复杂度 ： O(n)
其中n是数组的长度，只需要遍历一遍数组即可求得答案。
空间复杂度： O(1)
只需要常数级别的空间存放变量。
三、总结
当然这道题有更加简便的方法解决。
就是用正则表达式匹配：
class Solution { public: static const regex pattern; bool isNumber(string str) { return regex_match(str, pattern); } }; const regex Solution::pattern("[+-]?(?:\d+\.?\d*|\.\d+)(?:[Ee][+-]?\d+)?"); 复制代码
但是要注意，c++ 用正则表达式记得作为类的静态变量或全局变量，避免重复构造的开销，否则会超时。
