XTAO's Tech Blog
0%

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

发表于 更新于 分类于 ， 评论数：
3k 3 分钟

题目描述

题目链接：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
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

推荐文章