LeetCode 65. 有效数字

2025-10-24 HGNULB 约 11 分钟

文章信息 9 个分类 1 个标签

分类

题目描述

✅ 65. 有效数字

题意分析

给定字符串 s，判断它是否是一个「有效数字」。题目用一组文法把有效数字定义得非常明确：它由一个整数或一个小数，后面可选地跟上一个 e/E 加一个整数组成。整数是「可选的正负号 + 至少一位数字」；小数是「可选的正负号 + 后面三种之一：至少一位数字加一个点、至少一位数字加点再加至少一位数字、点加至少一位数字」。

把这段文法拆开看，能提炼出四条彼此独立的约束，它们就是整道题的全部内容。第一，字符集只有数字、+、-、.、e、E 六类，出现任何其他字符（包括空格）立即非法。第二，e/E 最多一个，它把字符串切成底数与指数两段。第三，. 只能出现在底数段且最多一个——指数必须是整数，所以 e 之后不允许有点。第四，符号位只能出现在字符串最开头或紧跟在 e/E 之后。

还有一条不在字符层面、而在「段」层面的约束，也是本题最容易漏的：每一段都必须至少含有一位数字。底数段没数字则 e 之前是空的（如 "e9"）；指数段没数字则 e 之后是空的（如 "3e"、"4e+"）。两种都非法。

约束的形态给出了很强的算法信号：所有规则都只取决于「到目前为止看到过什么」和「当前是什么字符」，不需要回看任意远的历史，也不需要往前看。这说明可以用常数个布尔量概括全部历史，一次从左到右扫描就能判定，不必分段切割、不必递归、更不必上正则——正则虽然一行能写完，但它把考点整个绕过去了，面试里等于没答。

数据规模上字符串长度不超过 20，效率完全不是考点。这题的难度全在规则枚举是否完备：它是典型的「细节题」，考的是能否把边界情形列全并组织成不重不漏的分支。

边界主要有：单独一个 "."、单独一个 "e"、单独一个 "+"；"3." 与 ".8" 都合法（点的一侧有数字即可）；"46.e3" 合法（底数是 46.，指数是 3）；"+-3"、"--6" 这类连续符号非法。

解法：一次遍历状态判断

核心思路

一个直觉做法是按 e 把字符串切成两段，分别写「是否合法小数」和「是否合法整数」两个校验函数。这条路能走通，但要处理 e 不存在、e 出现多次、切出空串等一堆情况，函数间还有重复逻辑，写起来又长又容易漏。

瓶颈在于「切分」这个动作本身是多余的。回头看那四条约束会发现，每一条都能在扫描到某个字符的当下就判定，判定所需的全部信息只有三件事：之前是否出现过数字、之前是否出现过小数点、之前是否出现过 e。既然历史可以被三个布尔量完全概括，就没有必要真的把字符串切开——只要在扫描过程中维护这三个量，每读一个字符就地检查它是否与当前状态相容即可。

于是三个状态变量的语义定死如下：seenDigit 表示「在当前所处的这一段里是否已经出现过数字」，seenDot 表示「整个字符串里是否出现过小数点」，seenExp 表示「整个字符串里是否出现过 e/E」。注意 seenDigit 的作用域是「当前段」而另外两个是「全局」，这个差异正是解法的精髓所在。

为什么 seenDigit 必须是段内的？因为「每段至少一位数字」这条约束要对底数和指数各检查一次。做法是：遇到 e 时先用 seenDigit 检查底数段是否有数字，检查通过后立刻把 seenDigit 重置为 false，让它转而承担指数段的计数职责；扫描结束时再返回 seenDigit，这一次它检查的就是指数段（若没有 e，则仍是底数段）。同一个变量在 e 前后被复用于两段，靠一次重置完成语义交接——这是全题最巧妙也最容易写错的一步。

需要维持的不变量是：每处理完一个字符，三个布尔量都准确反映「已扫描前缀」的状态，且已扫描的前缀本身是某个合法数字的前缀。任何一个字符只要与当前状态冲突，就立即返回 false，不变量因此永远成立；扫描到末尾还没返回，说明整串每一处局部都合法，此时只剩「最后一段有没有数字」这一个全局条件没验，恰好由返回 seenDigit 补上。

分支上要覆盖六类字符加一个兜底：数字、.、e/E、+/-，以及「其他一律非法」。兜底分支不能省，否则字母、空格这些字符会被静默放过。

解题步骤

初始化 seenDigit = seenDot = seenExp = false，对应「已扫描前缀为空」。三个都从 false 起步，让空串自然走到最后返回 false——空串不是有效数字，无需特判。

从左到右逐字符扫描，同时保留下标 i。下标是必须的：判断符号位是否合法要看它的前一个字符是什么，只有拿到 i 才能回看 s[i-1]。

遇到数字：置 seenDigit = true。数字在任何位置都不会破坏规则，只需登记「本段有数字了」，不需要任何检查。

遇到 .：若 seenDot || seenExp 则返回 false，否则置 seenDot = true。两个条件缺一不可——seenDot 挡住第二个小数点（"1.2.3"），seenExp 挡住指数段里的小数点（"1e2.3"，因为指数必须是整数）。注意这里不检查 seenDigit，因为 ".8" 是合法的，点可以出现在任何数字之前。

遇到 e/E：若 seenExp || !seenDigit 则返回 false；否则置 seenExp = true 并把 seenDigit 重置为 false。seenExp 挡住第二个指数符号；!seenDigit 落实「底数段至少一位数字」，它挡掉 "e9"、".e1"、"+e3"。重置 seenDigit 是为了让它接着去统计指数段，漏掉这一行，"3e" 会被误判为合法。

遇到 +/-：若 i > 0 且 s[i-1] 既不是 e 也不是 E，返回 false；否则什么都不做。i > 0 放行开头的符号位；回看前一字符是否为 e 放行指数的符号位。这里刻意不修改任何状态——符号本身既不提供数字，也不影响点和指数的计数，登记它反而会引入多余的状态。

其他任何字符：直接返回 false。这是兜底分支，负责字母、空格、逗号等一切非法字符。

扫描结束返回 seenDigit。此时它代表「最后一段（有 e 就是指数段，没有就是底数段）里出现过数字」，是唯一一个无法在扫描途中判定、必须留到最后的条件。返回 true 常量是错的，返回 seenDigit && seenDot 之类也是错的。

以 s = "-90E3" 走一遍。

初始 seenDigit = false、seenDot = false、seenExp = false。

i = 0，字符 -：走符号分支，i == 0 成立，直接放行，三个状态不变。

i = 1，字符 9：数字分支，seenDigit = true。

i = 2，字符 0：数字分支，seenDigit 已是 true，保持。

i = 3，字符 E：指数分支，seenExp 为 false、seenDigit 为 true，两个检查都通过。置 seenExp = true，并把 seenDigit 重置为 false——从这里开始它统计的是指数段。

i = 4，字符 3：数字分支，seenDigit = true（指数段有数字了）。

扫描结束，返回 seenDigit = true。正确。

再以 s = "4e+" 走一遍：4 使 seenDigit = true；e 通过检查后 seenExp = true、seenDigit 重置为 false；+ 在 i = 2，前一字符是 e，放行。扫描结束返回 seenDigit = false——指数段只有符号没有数字，正确判为非法。

最后以 s = "46.e3" 走一遍：4、6 使 seenDigit = true；. 时 seenDot 与 seenExp 均为 false，通过并置 seenDot = true；e 时 seenDigit 为 true，通过并重置 seenDigit = false；3 使 seenDigit = true。返回 true，与题目认定的合法一致。

若漏掉 e 分支里的 seenDigit = false 这一行，"3e" 会一路走到末尾返回底数段留下的 true，被错判为合法数字。

代码实现

class Solution {
    // 小数点只能出现在底数部分，且最多出现一次。
    public boolean isNumber(String s) {
        boolean seenDigit = false;
        boolean seenDot = false;
        boolean seenExp = false;

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c >= '0' && c <= '9') {
                seenDigit = true;
            } else if (c == '.') {
                if (seenDot || seenExp) {
                    return false;
                }
                seenDot = true;
            } else if (c == 'e' || c == 'E') {
                if (seenExp || !seenDigit) {
                    return false;
                }
                seenExp = true;
                seenDigit = false;
            } else if (c == '+' || c == '-') {
                if (i > 0 && s.charAt(i - 1) != 'e' && s.charAt(i - 1) != 'E') {
                    return false;
                }
            } else {
                return false;
            }
        }

        return seenDigit;
    }
}

func isNumber(s string) bool {
    // 小数点只能出现在底数部分，且最多出现一次。
    seenDigit := false
    seenDot := false
    seenExp := false

    for i := 0; i < len(s); i++ {
        c := s[i]
        if c >= '0' && c <= '9' {
            seenDigit = true
        } else if c == '.' {
            if seenDot || seenExp {
                return false
            }
            seenDot = true
        } else if c == 'e' || c == 'E' {
            if seenExp || !seenDigit {
                return false
            }
            seenExp = true
            seenDigit = false
        } else if c == '+' || c == '-' {
            if i > 0 && s[i-1] != 'e' && s[i-1] != 'E' {
                return false
            }
        } else {
            return false
        }
    }

    return seenDigit
}

复杂度分析

时间复杂度：$O(n)$，$n$ 为字符串长度。每个字符只被访问一次，落进某一个 if 分支后做的都是常数次布尔比较与赋值，没有回溯、没有子串截取、没有嵌套循环。

空间复杂度：$O(1)$。全程只有 seenDigit、seenDot、seenExp 三个布尔量和一个下标，与输入长度无关。凭的是「历史可以被常数个布尔量完全概括」这一观察——正因为不需要保存任何前缀，才省掉了切分字符串或建表的开销。

关键点总结

当所有约束都只依赖「已看过什么」和「当前字符是什么」时，就可以用常数个状态量替代分段与回看，把校验压成一次线性扫描。这是识别「可用有限状态判定」的通用信号，也是同类字符串校验题的统一解法框架。

状态变量的作用域要和它承担的约束对齐：seenDot、seenExp 管的是全局唯一性，所以一旦置真就不再复位；seenDigit 管的是「每段至少一位数字」，所以必须在段切换处复位。想不清作用域，就必然写出「3e 判为合法」这类错误。

有些条件天然无法在扫描途中判定，只能留到末尾结算——本题的「最后一段有没有数字」就是。写这类题时应当先把条件分成「就地可判」和「收尾才判」两类，返回值写什么由后者决定。

兜底的 else return false 分支不是可有可无的收尾，而是字符集约束的唯一落点；缺了它，任何未列举的字符都会被静默放行。

面试视角：这题面试官几乎一定会先问「能不能不用正则」——用 Pattern.matches 一行确实能 AC，但考点正是规则的完备枚举与状态设计，上正则等于交白卷。稳妥的答法是先口头把四条约束列出来，说明「历史只需三个布尔量」，再写扫描；写完主动补几组刁钻用例（"."、".8"、"3."、"46.e3"、"4e+"、"+-3"）当场对着代码走一遍。能主动列出边界用例，比写得快更能拿分。

易错点总结

e 分支忘记重置 seenDigit：输入 "3e" 会带着底数段留下的 seenDigit = true 走到末尾，返回 true；正确答案是 false，因为指数段没有数字。

. 分支漏掉 seenExp 判断：输入 "1e2.3" 会放过指数里的小数点返回 true；指数必须是整数，正确答案是 false。

. 分支多加了 !seenDigit 判断：输入 ".8" 会因为点之前没有数字被判非法返回 false；而它是合法小数，正确答案是 true。

e 分支漏掉 !seenDigit 判断：输入 "e9" 会返回 true；底数段是空的，正确答案是 false。

符号分支只判 i == 0 而不看前一字符：输入 "-90E3" 中 E 后若跟符号（如 "-90E-3"），i != 0 会被直接判非法返回 false；而它是合法的。

符号分支只回看是否为 e 而漏掉大写 E：输入 "1E-5" 会在 - 处返回 false，正确答案是 true。题目里 e 与 E 完全等价，两处判断都要成对写。

符号分支顺手置了状态：例如在符号分支里写 seenDigit = true，输入 "+" 会返回 true；单独一个符号不是数字，正确答案是 false。

缺少兜底的 else return false：输入 "1a" 中的 a 不落入任何已写分支而被跳过，返回 true；正确答案是 false。同理 " 1"、"1,000" 也会被误放行。

末尾直接 return true：输入 "." 会走完 . 分支后返回 true；单独的点不含任何数字，正确答案是 false。

误以为连续符号合法："--6" 中第二个 - 在 i = 1，前一字符是 - 而非 e，必须返回 false；若把条件写成「只要 i 很小就放行」，会错判为 true。

Java 里用 s.charAt(i) == 'e' || 'E'：这是编译错误而非逻辑错误，但在白板上很常见；必须写全 c == 'e' || c == 'E'。

改用 Double.parseDouble 试错：输入 "Infinity"、"0x1p3"、"3d" 都能被 Java 解析成功从而返回 true，而题目认定它们非法；库函数的接受集与本题文法并不一致。

相似题目

题目	难度	考察点
剑指 Offer 20. 表示数值的字符串	中等	与本题同一文法，但额外允许首尾空格，需先做双端裁剪再套同一套状态扫描
8. 字符串转换整数 (atoi)	中等	从「判定合法」变成「解析取值」，遇非法字符是截断而非报错，还要处理 32 位溢容截断
剑指 Offer 67. 把字符串转换成整数	中等	与 8 题同题，可用来对照「判定型」与「解析型」扫描在返回值设计上的差别
468. 验证IP地址	中等	同为多规则字符串校验，但要先按分隔符切段再逐段验，且需在两种格式间做三值判定
393. UTF-8 编码验证	中等	校验对象换成字节序列，状态是「还欠几个后续字节」这一计数器而非布尔量
20. 有效的括号	简单	约束需要记住任意深的嵌套历史，常数个状态量不够用，必须上栈
227. 基本计算器 II	中等	在扫描的同时求值而非判定，符号与数字的边界处理思路可直接沿用本题
166. 分数到小数	中等	反向构造数值字符串，正负号、小数点的摆放规则与本题的校验规则互为镜像