题目描述
题目链接: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
遍历完指定范围字符串后,返回数字是否出现过即可。
当然这里我们也可以循着第一部分的思路,通过小数点的个数和位置将字符串分割成两部分(或无须分割)然后分别判断是否合法整数即可。不过判断合法小数已经足够简单了,所以我没有继续分割。代码如下:
1 |
|
- 时间复杂度: O(n)
- 空间复杂度: O(1)
GitHub 代码同步地址: 65.ValidNumber.cpp
其他题目:
GitHub: Leetcode-C++-Solution
博客: Leetcode-Solutions