题目链接：65. 有效数字
目录
- 1. 题目分析
- 1.1 有效数字的结构
- 1.2 举例说明
- 2. 解法一：标志位遍历法
- 2.1 核心思路
- 2.2 代码实现
- 2.3 复杂度分析
- 3. 解法二：有限状态自动机 (DFA)
- 3.1 状态定义
- 3.2 代码实现
- 3.3 优缺点
- 4. 解法三：调用内置函数 (面试慎用)
1. 题目分析
这道题要求我们判断一个字符串 s 是否表示一个有效的数字。这不仅仅是一个简单的类型转换问题，因为题目对“有效数字”的格式有非常严格的定义。
1.1 有效数字的结构
我们可以把一个有效数字拆解为三个部分：
[符号] [底数部分] [指数部分]
-
符号 (
+/-)：- 可以出现在字符串的最开头。
- 也可以出现在指数符号 (
e/E) 的后面。 - 其他位置出现符号都是非法的。
-
底数部分 (整数或小数)：
- 必须包含至少一个数字。
- 可以包含一个小数点
.。 - 如果有小数点，小数点前或后至少有一边有数字（例如
1.,.1,1.1都是合法的，但单独的.是非法的）。 - 底数部分不能包含指数符号
e/E。
-
指数部分 (
e/E+ 整数)：- 如果出现
e或E，它后面必须跟着一个整数。 - 这个整数可以带符号（如
e+10,e-5），也可以不带（如e10）。 - 指数部分不能包含小数点。
- 指数部分必须至少有一个数字（例如
1e是非法的，因为e后面没有数字）。
- 如果出现
1.2 举例说明
- 合法:
"2","-0.1","+3.14","4.","-.9","2e10","-90E3","3e+7" - 非法:
"abc"(含字母),"1a"(含字母),"1e"(e 后无数字),"e3"(e 前无数字),"99e2.5"(指数不能是小数),"--6"(符号重复),"."(无数字)
2. 解法一：标志位遍历法
这是最直观、最容易理解的方法。我们只需要遍历字符串一次，同时维护几个“标志位”（Flag），记录我们在遍历过程中是否遇到了某些关键字符。
2.1 核心思路
我们需要维护三个布尔变量：
seen_digit: 是否已经遇到过数字？seen_dot: 是否已经遇到过小数点？seen_e: 是否已经遇到过指数符号 (e或E)？
在遍历每个字符时，我们根据字符类型更新这些标志位，并检查是否违反了规则：
- 如果是数字 (
0-9):- 标记
seen_digit = True。
- 标记
- 如果是符号 (
+或-):- 它只能出现在两个位置：
- 字符串的开头（索引
0）。 - 紧跟在指数符号
e或E之后。
- 字符串的开头（索引
- 其他位置出现符号直接返回
False。
- 它只能出现在两个位置：
- 如果是小数点 (
.):- 之前不能出现过小数点 (
not seen_dot)。 - 之前不能出现过指数符号 (
not seen_e)，因为指数后面必须是整数。 - 标记
seen_dot = True。
- 之前不能出现过小数点 (
- 如果是指数符号 (
e或E):- 之前不能出现过指数符号 (
not seen_e)。 - 关键点：在
e出现之前，必须已经遇到过数字 (seen_digit必须为True)。因为e前面必须有底数。 - 标记
seen_e = True。 - 重置
seen_digit = False。为什么？因为e后面必须紧跟一个新的整数，我们需要重新检测e后面是否有数字。
- 之前不能出现过指数符号 (
- 如果是其他字符:
- 直接返回
False。
- 直接返回
遍历结束后的检查：
- 最后必须返回
seen_digit。这意味着整个字符串（包括指数部分）必须至少包含一个数字。例如.或1e都会导致最后seen_digit为False。
2.2 代码实现
class Solution:def isNumber(self, s: str) -> bool:# 标志位初始化seen_digit = False # 是否遇到过数字seen_dot = False # 是否遇到过小数点seen_e = False # 是否遇到过指数符号 e/En = len(s)for i, char in enumerate(s):if char.isdigit():# 1. 如果是数字，标记 seen_digit 为 Trueseen_digit = Trueelif char in '+-':# 2. 如果是符号，只能在开头或 e/E 后面# i > 0 确保不是开头时，前一个字符必须是 e 或 Eif i > 0 and s[i-1] not in 'eE':return Falseelif char == '.':# 3. 如果是小数点# 之前不能有过小数点，也不能有过 e (指数部分必须是整数)if seen_dot or seen_e:return Falseseen_dot = Trueelif char in 'eE':# 4. 如果是指数符号# 之前不能有过 e，且 e 前面必须有数字if seen_e or not seen_digit:return Falseseen_e = True# 重要：e 后面必须跟整数，所以重置 seen_digit，# 强制要求 e 后面必须再出现至少一个数字seen_digit = Falseelse:# 5. 其他非法字符return False# 最后检查是否至少有一个数字# 这能排除 ".", "e", "+", "-1e" 等情况return seen_digit
2.3 复杂度分析
- 时间复杂度: \(O(N)\)，其中 \(N\) 是字符串长度。我们只遍历了一次字符串。
- 空间复杂度: \(O(1)\)，只使用了几个布尔变量，不随输入规模变化。
3. 解法二：有限状态自动机 (DFA)
这是一种更“计算机科学”的解法。我们将解析过程看作是一个状态机，字符串的每个字符都会驱动状态机从一个状态转移到另一个状态。如果遍历完字符串后，状态机处于“接受状态”，则字符串有效。
3.1 状态定义
我们可以定义以下几种状态：
0. 初始状态 (Start)
- 符号位 (Sign, 如
+,-) - 整数部分 (Digit, 如
1,23) - 小数点 (无前导数字) (Dot, 如
.) - 小数点 (有前导数字) (Dot with digits, 如
1.) - 小数部分 (Decimal, 如
1.2,.2) - 指数符号 (Exponent, 如
e,E) - 指数符号位 (Exp Sign, 如
e+,e-) - 指数数字 (Exp Digit, 如
e1,e23)
接受状态（遍历结束后如果是这些状态，则返回 True）：
- 整数部分 (2)
- 小数点 (有前导数字) (4)
- 小数部分 (5)
- 指数数字 (8)
3.2 代码实现
为了代码简洁，我们使用一个字典来表示状态转移表。
class Solution:def isNumber(self, s: str) -> bool:# 定义状态转移表# key: 当前状态, value: {输入类型：下一状态}# 输入类型分类：'d': 数字，'s': 符号，'e': 指数，'.': 小数点，'?': 其他states = [{ 's': 1, 'd': 2, '.': 3 }, # 0. 初始状态{ 'd': 2, '.': 3 }, # 1. 符号位后{ 'd': 2, '.': 4, 'e': 6 }, # 2. 整数部分 (接受状态){ 'd': 5 }, # 3. 小数点 (无前导数字){ 'd': 5, 'e': 6 }, # 4. 小数点 (有前导数字) (接受状态){ 'd': 5, 'e': 6 }, # 5. 小数部分 (接受状态){ 's': 7, 'd': 8 }, # 6. 指数符号后{ 'd': 8 }, # 7. 指数符号位后{ 'd': 8, '?': 9 } # 8. 指数数字 (接受状态)]current_state = 0for char in s:if char.isdigit():input_type = 'd'elif char in '+-':input_type = 's'elif char in 'eE':input_type = 'e'elif char == '.':input_type = '.'else:input_type = '?'# 如果当前状态没有定义该输入类型的转移，说明非法if input_type not in states[current_state]:return False# 转移到下一状态current_state = states[current_state][input_type]# 只有处于接受状态 (2, 4, 5, 8) 才算有效return current_state in [2, 4, 5, 8]
3.3 优缺点
- 优点: 逻辑非常严密，容易扩展，运行效率高。
- 缺点: 状态表设计较复杂，面试时容易写错状态转移关系，代码可读性不如标志位法。
4. 解法三：调用内置函数 (面试慎用)
Python 的 float() 函数可以尝试将字符串转换为浮点数。如果转换失败会抛出异常。
class Solution:def isNumber(self, s: str) -> bool:if 'inf' in s.lower() or 'nan' in s.lower():return Falsetry:float(s)return Trueexcept ValueError:return False
⚠️ 注意：
虽然这段代码在 LeetCode 上通常能通过，但在面试中通常不被接受。
- 语义差异：Python 的
float()支持"inf","Infinity","nan"等，但本题定义的有效数字不包含这些。 - 考察目的：这道题的目的是考察对字符串解析、边界条件处理和逻辑判断的能力，直接调用库函数 bypass 了这些考察点。
- 建议：仅作为验证代码逻辑正确性的辅助手段，不要作为正式提交答案。