LeetCode 0065 - Valid Number
# Hints
- 模拟
# 题面
Difficulty | Time Complexity Limit | Extra-Memory Complexity Limit |
---|---|---|
Hard |
Validate if a given string can be interpreted as a decimal number.
Some examples:
"0" => true
" 0.1 " => true
"abc" => false
"1 a" => false
"2e10" => true
" -90e3 " => true
" 1e" => false
"e3" => false
" 6e-1" => true
" 99e2.5 " => false
"53.5e93" => true
" --6 " => false
"-+3" => false
"95a54e53" => false
Note:
It is intended for the problem statement to be ambiguous. You should gather all requirements up front before implementing one. However, here is a list of characters that can be in a valid decimal number:
Numbers
0-9
Exponent
e
Positive/negative sign
+
/-
Decimal point
.
Of course, the context of these characters also matters in the input.
# 题意
给定一个字符串,判断该串是否符合题意的十进制数格式。
# 题解
按题意模拟即可。本来是很简单的题,但是这道题太毒瘤了,有两个堪称是莫名其妙的规则,搞不懂为什么这么规定,还不在题面里写清楚:
莫名其妙的浮点数规则:形如
x.
和.y
的格式是合法的。莫名其妙的幂级数规则:对于
xey
,其中的y
不能是浮点数。
我的代码实现是,先将前后缀的空格处理掉,然后处理 xey
的情况,将其分割并分别判断 x
和 y
是否合法。这样实现可以较为清晰地处理本题中的各种特殊情况,最大限度地减少代码冗余。实现的时间复杂度为 。
细节问题:
- 注意处理以下这些题目样例中未给出的、特殊的非法输入格式,其中
x
表示一个不含正负号的数值表达式,+
可等价替换为-
:
"."; "x."; ".x"
"+"; ".+"; "+."; "+.+"
"e"; "+e"; "e+"; "+e+"; ".e"; "e."; ".e.";
" "
# AC代码
class Solution {
public:
bool isNumber(const string & s) {
// 特判
if (s.empty()) {
return false;
}
// 处理前后缀空格
int left = 0;
while (left < s.length() && s[left] == ' ') {
left ++;
}
int right = s.length() - 1;
while (right >= 0 && s[right] == ' ') {
right --;
}
// 处理 xey 的情况
size_t pos = s.find('e');
if (pos != string::npos) {
int mid = pos;
bool flag_x = is_number(s, left, mid - 1, true);
bool flag_y = is_number(s, mid + 1, right, false);
return (flag_x && flag_y);
}
// 返回
return is_number(s, left, right, true);
}
// 判断是否为数字
bool is_number(const string & s, int left, int right, bool allow_float) {
// 处理符号
if (s[left] == '+' || s[left] == '-') {
left ++;
}
// 特判
if (left > right || (left == right && s[left] == '.')) {
return false;
}
// 遍历
bool has_float = false;
for (int i = left; i <= right; i ++) {
// 处理浮点
if (s[i] == '.') {
if (allow_float && !has_float) {
has_float = true;
} else {
return false;
}
}
// 处理非法字符
else if (!isdigit(s[i])) {
return false;
}
}
// 返回
return true;
}
};
- 01
- Reading Papers - Kernel Concurrency06-01
- 02
- Linux Kernel - Source Code Overview05-01
- 03
- Linux Kernel - Per-CPU Storage05-01