返回

[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

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

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

#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

Built with Hugo
Theme Stack designed by Jimmy