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:
2.     def isNumber(self, s: str) -> bool:
3.         # 标志位初始化
4.         seen_digit = False   # 是否遇到过数字
5.         seen_dot = False     # 是否遇到过小数点
6.         seen_e = False       # 是否遇到过指数符号 e/E
7.         
8.         n = len(s)
9.         for i, char in enumerate(s):
10.             if char.isdigit():
11.                 # 1. 如果是数字，标记 seen_digit 为 True
12.                 seen_digit = True
13.             elif char in '+-':
14.                 # 2. 如果是符号，只能在开头或 e/E 后面
15.                 # i > 0 确保不是开头时，前一个字符必须是 e 或 E
16.                 if i > 0 and s[i-1] not in 'eE':
17.                     return False
18.             elif char == '.':
19.                 # 3. 如果是小数点
20.                 # 之前不能有过小数点，也不能有过 e (指数部分必须是整数)
21.                 if seen_dot or seen_e:
22.                     return False
23.                 seen_dot = True
24.             elif char in 'eE':
25.                 # 4. 如果是指数符号
26.                 # 之前不能有过 e，且 e 前面必须有数字
27.                 if seen_e or not seen_digit:
28.                     return False
29.                 seen_e = True
30.                 # 重要：e 后面必须跟整数，所以重置 seen_digit，
31.                 # 强制要求 e 后面必须再出现至少一个数字
32.                 seen_digit = False
33.             else:
34.                 # 5. 其他非法字符
35.                 return False
36.         
37.         # 最后检查是否至少有一个数字
38.         # 这能排除 ".", "e", "+", "-1e" 等情况
39.         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:
2.     def isNumber(self, s: str) -> bool:
3.         # 定义状态转移表
4.         # key: 当前状态, value: {输入类型：下一状态}
5.         # 输入类型分类：'d': 数字，'s': 符号，'e': 指数，'.': 小数点，'?': 其他
6.         states = [
7.             { 's': 1, 'd': 2, '.': 3 },            # 0. 初始状态
8.             { 'd': 2, '.': 3 },                    # 1. 符号位后
9.             { 'd': 2, '.': 4, 'e': 6 },    # 2. 整数部分 (接受状态)
10.             { 'd': 5 },                            # 3. 小数点 (无前导数字)
11.             { 'd': 5, 'e': 6 },            # 4. 小数点 (有前导数字) (接受状态)
12.             { 'd': 5, 'e': 6 },            # 5. 小数部分 (接受状态)
13.             { 's': 7, 'd': 8 },                    # 6. 指数符号后
14.             { 'd': 8 },                            # 7. 指数符号位后
15.             { 'd': 8, '?': 9 }                     # 8. 指数数字 (接受状态)
16.         ]
17.         
18.         current_state = 0
19.         for char in s:
20.             if char.isdigit():
21.                 input_type = 'd'
22.             elif char in '+-':
23.                 input_type = 's'
24.             elif char in 'eE':
25.                 input_type = 'e'
26.             elif char == '.':
27.                 input_type = '.'
28.             else:
29.                 input_type = '?'
30.             
31.             # 如果当前状态没有定义该输入类型的转移，说明非法
32.             if input_type not in states[current_state]:
33.                 return False
34.             
35.             # 转移到下一状态
36.             current_state = states[current_state][input_type]
37.             
38.         # 只有处于接受状态 (2, 4, 5, 8) 才算有效
39.         return current_state in [2, 4, 5, 8]

复制代码

3.3 优缺点

• 优点: 逻辑非常精密，容易扩展，运行服从高。
  
• 缺点: 状态表计划算复杂，口试时容易写错状态转移关系，代码可读性不如标记位法。
  

4. 解法三：调用内置函数 (口试慎用)

Python 的 float() 函数可以实验将字符串转换为浮点数。假如转换失败会抛出非常。

1. class Solution:
2.     def isNumber(self, s: str) -> bool:
3.         if 'inf' in s.lower() or 'nan' in s.lower():
4.             return False
5.         try:
6.             float(s)
7.             return True
8.         except ValueError:
9.             return False

复制代码

⚠️ 留意：
固然这段代码在 LeetCode 上通常能通过，但在口试中通常不被担当。

• 语义差异：Python 的 float() 支持 "inf", "Infinity", "nan" 等，但本题界说的有用数字不包罗这些。
  
• 观察目标：这道题的目标是观察对字符串剖析、边界条件处理处罚和逻辑判定的本领，直接调用库函数 bypass 了这些观察点。
  
• 发起：仅作为验证代码逻辑准确性的辅助本领，不要作为正式提交答案。