欢迎访问LeetCode题解合集
题目描述
有效数字(按顺序)可以分成以下几个部分:
- 一个 小数 或者 整数
- (可选)一个
'e'
或'E'
,后面跟着一个 整数
小数(按顺序)可以分成以下几个部分:
- (可选)一个符号字符(
'+'
或'-'
) - 下述格式之一:
- 至少一位数字,后面跟着一个点
'.'
- 至少一位数字,后面跟着一个点
'.'
,后面再跟着至少一位数字 - 一个点
'.'
,后面跟着至少一位数字
整数(按顺序)可以分成以下几个部分:
- (可选)一个符号字符(
'+'
或'-'
) - 至少一位数字
部分有效数字列举如下:
["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
示例 3:
输入:s = "."
输出:false
示例 4:
输入:s = ".1"
输出:true
提示:
- $1 \le s.length \le 20$
s
仅含英文字母(大写和小写),数字(0-9
),加号'+'
,减号'-'
,或者点'.'
。
题解:
法一:
正则表达式。
有效数字模式为: A[.[B]][[e|E]C]
或者 .B[[e|E]C]
,其中,A、B、C
都是整数,A、C
可以是有符号整数, B
是无符号整数。[]
表示可以出现 0/1
次。
于是按照上述模式判断即可:
-
首先处理
s
的首尾空格,很神奇的测试数据。。。 -
假设存在
A
部分,先判断A
那部分(该部分可以使用两个函数来表示,后面的B
和C
部分都能用上)
bool integer( string& s, int& p ) { // 处理有符号整数
if ( s[p] == '+' || s[p] == '-' ) ++p;
return unsignedInteger(s, p);
}
bool unsignedInteger( string& s, int& p ) { // 处理无符号整数
int k = p;
while ( p < s.size() && isdigit(s[p]) ) ++p;
return p > k;
}
-
在把
A
部分遍历完后,若当前位为.
,需要判断B
是否存在。假设我们使用
numeric
表示前面是否合法,如果前面合法,那么unsignedInteger( s, ++i ) | numeric
应该为true
,使用|
操作是因为小数包含了三种情况:
1. 没有整数部分,比如.123
等于0.123
2. 没有小数部分,比如233.
等于233.0
3. 小数点前后都有数字 -
小数部分遍历结束后,若当前位为
e/E
,需要判断C
是否存在,如果前面合法,那么integer( s, ++i ) & numeric
应该为true
,因为e/E
前后必须有数字,所以使用&
操作。
最后,如果 numeric
为 true
且遍历完 s
所有字符,则说明 s
是有效的数字。
时间复杂度:$O(n)$
额外空间复杂度:$O(1)$
法一代码:
class Solution {
public:
bool integer( string& s, int& p ) {
if ( s[p] == '+' || s[p] == '-' ) ++p;
return unsignedInteger(s, p);
}
bool unsignedInteger( string& s, int& p ) {
int k = p;
while ( p < s.size() && isdigit(s[p]) ) ++p;
return p > k;
}
bool isNumber(string s) {
int n = s.length();
int i = 0;
while ( i < n && s[i] == ' ' ) ++i;
if ( i == n ) return false;
bool numeric = integer( s, i );
if ( s[i] == '.' ) numeric = unsignedInteger( s, ++i ) | numeric;
if ( !numeric ) return false;
if ( s[i] == 'e' || s[i] == 'E' ) numeric = integer( s, ++i ) & numeric;
if ( !numeric ) return false;
while ( i < n && s[i] == ' ' ) ++i;
return numeric && i == n;
}
};
/*
时间:0ms,击败:100.00%
内存:5.8MB,击败:98.05%
*/
法二:
直接模拟。
有两种写法,一种是设置几个标志位来判断当前是否 合法
,我们设置三个标志位 num(数字)
、point(小数点)
和 nume(e/E)
。
有一些不合法的情况:
- 若当前为
.
,前面出现了e/E
或.
,非法 - 若当前为
e/E
,前面出现了e/E
或没有出现数字,非法 - 若当前为
+/-
,不是第一位,且前面没有e/E
,非法 - 若是其它字符(空格除外),非法
剩下的,就很容易判断了,见代码:
class Solution {
public:
bool isNumber(string s) {
int n = s.length();
int i = 0;
while ( i < n && s[i] == ' ' ) ++i;
if ( i == n ) return false;
bool num = false, point = false, nume = false;
int k = i;
while ( i < n ) {
if ( isdigit(s[i]) ) num = true;
else if ( s[i] == '.' ) {
if ( nume || point ) return false;
point = true;
} else if ( s[i] == 'e' || s[i] == 'E' ) {
if ( nume || !num ) return false;
num = false; // 置为 false 是为了判断 e/E 后面是否出现数字
nume = true;
} else if ( s[i] == '+' || s[i] == '-' ) {
if ( i != k && !(s[i - 1] == 'e' || s[i - 1] == 'E') )
return false;
} else if ( s[i] != ' ' ) return false;
++i;
}
return num && i == n;
}
};
/*
时间:0ms,击败:100.00%
内存:5.7MB,击败:99.84%
*/
还有另外一种写法,在遍历过程中,遇到非法的情况返回 false
,到达末尾返回 true
。
class Solution {
public:
bool isNumber(string s) {
int n = s.length();
int i = 0;
while ( i < n && s[i] == ' ' ) ++i;
if ( i == n ) return false;
if ( s[i] == '+' || s[i] == '-' ) ++i;
int n_pt = 0, n_nm = 0;
while ( i < n && (isdigit(s[i]) || s[i] == '.') ) {
if ( s[i] == '.' ) ++n_pt;
else ++n_nm;
++i;
}
if ( n_pt > 1 || n_nm < 1 ) return false;
if ( i == n ) return true;
if ( s[i] == 'e' || s[i] == 'E' ) {
if ( ++i == n ) return false;
if ( s[i] == '+' || s[i] == '-' )
if ( ++i == n ) return false;
n_nm = 0;
while ( i < n && isdigit(s[i]) ) ++n_nm, ++i;
if ( n_nm < 1 ) return false;
}
while ( i < n && s[i] == ' ' ) ++i;
return i == n;
}
};
/*
时间:0ms,击败:100.00%
内存:5.8MB,击败:98.54%
*/
法三:
自动机。
总共 9
个状态。橙色
代表合法状态,输入分为四大类,数字、小数点、e/E、+/-
。开始在状态 0
,我们根据类别进行状态转移。
最终的合法状态在:2、3、8、5
这四个状态。
class Solution {
public:
bool isNumber(string s) {
int n = s.length();
int i = 0;
while ( i < n && s[i] == ' ' ) ++i;
if ( i == n ) return false;
int k = n - 1;
while ( k >= i && s[k] == ' ' ) --k;
int state = 0;
for ( ; i <= k; ++i ) {
if ( s[i] == '+' || s[i] == '-' ) {
if ( !state ) state = 1;
else if ( state == 4 ) state = 6;
else return false;
} else if ( isdigit(s[i]) ) {
if ( state < 3 ) state = 2;
else if ( state == 3 ) continue;
else if ( state <= 6 ) state = 5;
else state = 8;
} else if ( s[i] == '.' ) {
if ( state < 2 ) state = 7;
else if ( state == 2 ) state = 3;
else return false;
} else if ( s[i] == 'e' || s[i] == 'E' ) {
if ( state == 2 || state == 3 || state == 8 ) state = 4;
else return false;
} else return false;
}
return state == 2 || state == 3 || state == 5 || state == 8;
}
};
/*
时间:0ms,击败:100.00%
内存:5.9MB,击败:94.15%
*/