LeetCode 65 有效数字：python3 题解

题目链接：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 代码实现

1. class Solution:    def isNumber(self, s: str) -> bool:        # 标志位初始化        seen_digit = False   # 是否遇到过数字        seen_dot = False     # 是否遇到过小数点        seen_e = False       # 是否遇到过指数符号 e/E                n = len(s)        for i, char in enumerate(s):            if char.isdigit():                # 1. 如果是数字，标记 seen_digit 为 True                seen_digit = True            elif char in '+-':                # 2. 如果是符号，只能在开头或 e/E 后面                # i > 0 确保不是开头时，前一个字符必须是 e 或 E                if i > 0 and s[i-1] not in 'eE':                    return False            elif char == '.':                # 3. 如果是小数点                # 之前不能有过小数点，也不能有过 e (指数部分必须是整数)                if seen_dot or seen_e:                    return False                seen_dot = True            elif char in 'eE':                # 4. 如果是指数符号                # 之前不能有过 e，且 e 前面必须有数字                if seen_e or not seen_digit:                    return False                seen_e = True                # 重要：e 后面必须跟整数，所以重置 seen_digit，                # 强制要求 e 后面必须再出现至少一个数字                seen_digit = False            else:                # 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 代码实现

为了代码简洁，我们使用一个字典来表示状态转移表。

1. 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 = 0        for 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() 函数可以尝试将字符串转换为浮点数。如果转换失败会抛出异常。

1. class Solution:    def isNumber(self, s: str) -> bool:        if 'inf' in s.lower() or 'nan' in s.lower():            return False        try:            float(s)            return True        except ValueError:            return False

复制代码

⚠️ 注意：
虽然这段代码在 LeetCode 上通常能通过，但在面试中通常不被接受。

• 语义差异：Python 的 float() 支持 "inf", "Infinity", "nan" 等，但本题定义的有效数字不包含这些。
  
• 考察目的：这道题的目的是考察对字符串解析、边界条件处理和逻辑判断的能力，直接调用库函数 bypass 了这些考察点。
  
• 建议：仅作为验证代码逻辑正确性的辅助手段，不要作为正式提交答案。
  

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！