【月度刷题计划同款】常常规规模拟题

题目描述

这是 LeetCode 上的 65. 有效数字 ，难度为 困难。

Tag : 「模拟」

有效数字（按顺序）可以分成以下几个部分：

1. 一个 小数 或者 整数
2. （可选）一个 'e' 或 'E' ，后面跟着一个 整数

小数（按顺序）可以分成以下几个部分：

1. （可选）一个符号字符（'+' 或 '-'）
2. 下述格式之一：
   1. 至少一位数字，后面跟着一个点 '.'
   2. 至少一位数字，后面跟着一个点 '.' ，后面再跟着至少一位数字
   3. 一个点 '.' ，后面跟着至少一位数字

整数（按顺序）可以分成以下几个部分：

1. （可选）一个符号字符（'+' 或 '-'）
2. 至少一位数字

部分有效数字列举如下：

• ["2", "0089", "-0.1", "+3.14", "4.", "-.9", "2e10", "-90E3", "3e+7", "+6e-1", "53.5e93", "-123.456e789"]

部分无效数字列举如下：

• ["abc", "1a", "1e", "e3", "99e2.5", "--6", "-+3", "95a54e53"]

给你一个字符串 s，如果 s 是一个 有效数字 ，请返回 true。

示例 1：

输入：s = "0"

输出：true

示例 2：

输入：s = "e"

输出：false

示例 3：

输入：s = "."

输出：false

示例 4：

输入：s = ".1"

输出：true

提示：

• 1<=s.length<=201 <= s.length <= 201<=s.length<=20
• s 仅含英文字母（大写和小写），数字（0-9），加号 '+' ，减号 '-' ，或者点 '.' 。

模拟

字符串大模拟，根据「有效数字定义」梳理规则即可。

本题有多种解法：「正则」、「DFA」、「模拟」...

「模拟」是在各类场景中最容易实现的方式，只要头脑不发热都能写出来。

将字符串以 e/E 进行分割后，其实规则十分简单：

• 如果存在 e/E ：左侧可以「整数」或「浮点数」，右侧必须是「整数」
• 如果不存在 e/E ：整段可以是「整数」或「浮点数」

关键在于如何实现一个 check 函数用于判断「整数」或「浮点数」：

• +/- 只能出现在头部
• . 最多出现一次
• 至少存在一个数字

代码：

class Solution {
    public boolean isNumber(String s) {
        int n = s.length();
        char[] cs = s.toCharArray();
        int idx = -1;
        for (int i = 0; i < n; i++) {
            if (cs[i] == 'e' || cs[i] == 'E') {
                if (idx == -1) idx = i;
                else return false;
            }
        }
        boolean ans = true;
        if (idx != -1) {
            ans &= check(cs, 0, idx - 1, false);
            ans &= check(cs, idx + 1, n - 1, true);
        } else {
            ans &= check(cs, 0, n - 1, false);
        }
        return ans;
    }
    boolean check(char[] cs, int start, int end, boolean mustInteger) {
        if (start > end) return false;
        if (cs[start] == '+' || cs[start] == '-') start++;
        boolean hasDot = false, hasNum = false;
        for (int i = start; i <= end; i++) {
            if (cs[i] == '.') {
                if (mustInteger || hasDot) return false;
                hasDot = true;
            } else if (cs[i] >= '0' && cs[i] <= '9') {
                hasNum = true;
            } else {
                return false;
            }
        }
        return hasNum;
    }
}

• 时间复杂度：O(n)O(n)O(n)
• 空间复杂度：将 toCharArray 替换为 charAt 为 O(1)O(1)O(1)，否则为 O(n)O(n)O(n)

最后

这是我们「刷穿 LeetCode」系列文章的第 No.65 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地 🎉🎉