一、题目
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、代码实现
代码参考：
代码语言：javascript复制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)
只需要常数级别的空间存放变量。
三、总结
当然这道题有更加简便的方法解决。
就是用正则表达式匹配：
代码语言：javascript复制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 用正则表达式记得作为类的静态变量或全局变量，避免重复构造的开销，否则会超时。
