题目描述
题目链接:65. Valid Number
Validate if a given string can be interpreted as a decimal number.
例子
"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.
解题思路
这道题看上去规则很不明确,尤其是通过 +/-
,.
,e
三种字符不同顺序组合可能会有很多种情况,比较难理清思路。这里我用了一种比较取巧的做法。先将复杂问题简单化,首先通过双指针从两侧将空格的部分收窄确认实际数字范围。在该范围中先搜索 e
的个数,分为以下情况:
- 0 个
e
:这个时候数字只可能是一个简单的小数,我们只需判断该数字是否合法小数即可: - 1 个
e
:数字是科学计数法法形式记录的,我们可以通过e
的位置将数字分成两部分,对第一部分判断是否为合法小数,对第二部分判断是否为合法整数(科学计数法第二部分不能为小数) - 2 个
e
:数字不合法
通过上述做法,我们将原先的问题简化为:只需要判断一个字符串是否为合法小数(或整数即可),从前往后遍历字符串,对每一个字符分别判断:
- 如果是
+/-
:判断是否在字符串最开头,如果不是则不合法 - 如果是
.
:判断小数点是否已出现过,否则不合法(小数点理论上可以出现在任何地方,例如.1
,1.
,1.1
) - 如果是
0~9
,我们则记录已出现过数字(合法小数必须有至少一个数字) - 其他情况直接返回
false
遍历完指定范围字符串后,返回数字是否出现过即可。
当然这里我们也可以循着第一部分的思路,通过小数点的个数和位置将字符串分割成两部分(或无须分割)然后分别判断是否合法整数即可。不过判断合法小数已经足够简单了,所以我没有继续分割。代码如下:
#include <string>
#include <unordered_set>
#include <cctype>
class Solution {
public:
bool isNumber(std::string s) {
int front = 0, back = s.length(); // 前闭后开区间
while (front < back && s[front] == ' ') front++;
while (front < back && s[back - 1] == ' ') back--;
if (front == back) return false;
int med = -1;
for (int i = front; i < back; i++) {
if (s[i] == 'e') {
if (med != -1) return false; // find 2 e!
else med = i;
}
}
if (med == -1) { // find no e!
return isValidNumber(s, front, back, true);
}
else {
bool is_valid = isValidNumber(s, front, med, true); // the first part can be decimal
if (!is_valid) return false;
is_valid = isValidNumber(s, med + 1, back, false); // the second part can't be decimal
return is_valid;
}
return true;
}
private:
bool isValidNumber(const std::string& s, int front, int back, bool can_be_decimal) {
if (front == back) {
return false;
}
if (back == front + 1) {
return std::isdigit(s[front]);
}
std::unordered_set<char> symbols_record;
for (int i = front; i < back; i++) {
char symbol = s[i];
if (symbol == '+' || symbol == '-') { // if we find a sign, it must be at the begin
if (i != front) return false;
} else if (symbol == '.') { // if we find a '.'
if (!can_be_decimal || // can't be decimal
symbols_record.count('.')) return false; // or find two '.'
else {
symbols_record.insert('.');
}
} else if (std::isdigit(symbol)) { // a valid number at least have 1 digit
symbols_record.insert('0'); // use '0' represent digit
continue;
} else {
return false;
}
}
return symbols_record.count('0');
}
};
- 时间复杂度: O(n)
- 空间复杂度: O(1)
GitHub 代码同步地址: 65.ValidNumber.cpp
其他题目: GitHub: Leetcode-C++-Solution 博客: Leetcode-Solutions