0%

[Leetcode]65. Valid Number(C++)

题目描述

题目链接: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:数字不合法

通过上述做法,我们将原先的问题简化为:只需要判断一个字符串是否为合法小数(或整数即可),从前往后遍历字符串,对每一个字符分别判断:

  • 如果是 +/-:判断是否在字符串最开头,如果不是则不合法
  • 如果是 .:判断小数点是否已出现过,否则不合法(小数点理论上可以出现在任何地方,例如 .11., 1.1
  • 如果是 0~9,我们则记录已出现过数字(合法小数必须有至少一个数字)
  • 其他情况直接返回 false

遍历完指定范围字符串后,返回数字是否出现过即可。

当然这里我们也可以循着第一部分的思路,通过小数点的个数和位置将字符串分割成两部分(或无须分割)然后分别判断是否合法整数即可。不过判断合法小数已经足够简单了,所以我没有继续分割。代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#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