作者介绍：10年大厂数据\经营分析经验，现任大厂数据部门负责人。
会一些的技术：数据分析、算法、SQL、大数据相关、python
欢迎加入社区：码上找工作
作者专栏每日更新：
备注说明：方便大家阅读，统一使用python，带必要注释，公众号 数据分析螺丝钉 一起打怪升级
题目描述
验证给定的字符串是否可以解释为十进制数字。
例如:
- “0” =>
true - “0.1” =>
true - “abc” =>
false - “1 a” =>
false - “2e10” =>
true - " -90e3 " =>
true - " 1e" =>
false - “e3” =>
false - " 6e-1" =>
true - " 99e2.5 " =>
false - “53.5e93” =>
true - " --6 " =>
false - “-+3” =>
false - “95a54e53” =>
false
说明: 我们考虑在 ASCII 字符集中的空白字符，非负整数和小数。
输入格式
- s：一个字符串。
输出格式
- 返回一个布尔值，表示是否为有效的十进制数字。
方法一：有限状态自动机（Finite State Automaton, FSA）
解题步骤
- 定义状态：创建状态转换表，包括接受数字、符号、小数点、指数符号等状态。
- 初始化状态：初始状态设定为
start。 - 状态转移：根据当前字符和状态转换表更新状态。
- 终止检查：最终状态在接受状态集合中，则返回
true；否则返回false。
完整的规范代码
def isNumber(s): """ 使用有限状态自动机（FSA）方法判断字符串是否为有效的十进制数字 :param s: str, 输入字符串 :return: bool, 是否为有效的十进制数字 """ state = 0 finals = [0, 0, 0, 1, 0, 1, 1, 0, 1] # 有效终止状态 transitionTable = [ [0, 1, 6, 2, -1, -1], # state 0 [-1, -1, 6, 2, -1, -1], # state 1 [-1, -1, 3, -1, -1, -1], # state 2 [8, -1, 3, -1, 4, -1], # state 3 [-1, 7, 5, -1, -1, -1], # state 4 [8, -1, 5, -1, -1, -1], # state 5 [8, -1, 6, 3, 4, -1], # state 6 [-1, -1, 5, -1, -1, -1], # state 7 [8, -1, -1, -1, -1, -1] # state 8 ] # Input classes: [invalid, '+/-', 'number', '.', 'e/E', 'other'] def inputType(c): if c == ' ': return 0 if c in '+-': return 1 if c.isdigit(): return 2 if c == '.': return 3 if c in 'eE': return 4 return 5 for c in s.strip(): state = transitionTable[state][inputType(c)] if state == -1: return False return finals[state] == 1 # 示例调用 print(isNumber("0")) # 输出: True print(isNumber("0.1")) # 输出: True print(isNumber("abc")) # 输出: False print(isNumber("1 a")) # 输出: False print(isNumber("2e10")) # 输出: True print(isNumber(" -90e3 ")) # 输出: True print(isNumber("1e")) # 输出: False print(isNumber("e3")) # 输出: False print(isNumber("6e-1")) # 输出: True print(isNumber("99e2.5")) # 输出: False print(isNumber("53.5e93")) # 输出: True print(isNumber("--6")) # 输出: False print(isNumber("-+3")) # 输出: False print(isNumber("95a54e53")) # 输出: False
算法分析
- 时间复杂度：(O(n))，只需要遍历字符串一次。
- 空间复杂度：(O(1))，状态转换表的大小是常数。
方法二：正则表达式
解题步骤
- 定义正则表达式：使用正则表达式匹配可能的数字模式。
- 模式匹配：使用 Python 的
re模块来检查字符串是否符合定义的正则表达式。
完整的规范代码
import re def isNumber(s): """ 使用正则表达式判断字符串是否为有效的十进制数字 :param s: str, 输入字符串 :return: bool, 是否为有效的十进制数字 """ pattern = r'^[+-]?(\d+(\.\d*)?|\.\d+)([eE][+-]?\d+)?$' return re.match(pattern, s.strip()) is not None # 示例调用 print(isNumber("0")) # 输出: True print(isNumber("0.1")) # 输出: True print(isNumber("abc")) # 输出: False print(isNumber("1 a")) # 输出: False print(isNumber("2e10")) # 输出: True print(isNumber(" -90e3 ")) # 输出: True print(isNumber("1e")) # 输出: False print(isNumber("e3")) # 输出: False print(isNumber("6e-1")) # 输出: True print(isNumber("99e2.5")) # 输出: False print(isNumber("53.5e93")) # 输出: True print(isNumber("--6")) # 输出: False print(isNumber("-+3")) # 输出: False print(isNumber("95a54e53")) # 输出: False
算法分析
- 时间复杂度：(O(n))，正则表达式的匹配时间通常与字符串长度线性相关。
- 空间复杂度：(O(1))，正则表达式的空间占用是常数。
方法三：分情况讨论
解题步骤
- 逐字符分析：逐个分析字符串中的字符，根据数字、小数点、指数部分、符号等进行分类处理。
- 状态标记：使用标志位记录是否出现过数字、小数点、指数等，以正确处理各种情况。
完整的规范代码
def isNumber(s): """ 分情况讨论法判断字符串是否为有效的十进制数字 :param s: str, 输入字符串 :return: bool, 是否为有效的十进制数字 """ s = s.strip() if not s: return False numeric = False decimal = False exponent = False i = 0 # 处理符号 if s[0] in "+-": i += 1 while i < len(s): if s[i].isdigit(): numeric = True elif s[i] == '.': if decimal or exponent: return False decimal = True elif s[i] in "eE": if exponent or not numeric: return False exponent = True numeric = False # 需要在e之后看到数字 decimal = False # 防止e之后出现小数点 if i + 1 < len(s) and s[i+1] in "+-": i += 1 else: return False i += 1 return numeric # 示例调用 print(isNumber("0")) # 输出: True print(isNumber("0.1")) # 输出: True print(isNumber("abc")) # 输出: False print(isNumber("1 a")) # 输出: False print(isNumber("2e10")) # 输出: True print(isNumber(" -90e3 ")) # 输出: True print(isNumber("1e")) # 输出: False print(isNumber("e3")) # 输出: False print(isNumber("6e-1")) # 输出: True print(isNumber("99e2.5")) # 输出: False print(isNumber("53.5e93")) # 输出: True print(isNumber("--6")) # 输出: False print(isNumber("-+3")) # 输出: False print(isNumber("95a54e53")) # 输出: False
算法分析
- 时间复杂度：(O(n))，需要遍历整个字符串。
- 空间复杂度：(O(1))，只使用了几个辅助变量。### 方法四：逐步细化条件的处理
解题步骤
- 初始化变量：定义几个变量来标识数字状态，如是否遇到数字、小数点、指数等。
- 遍历字符串：逐字符检查，并根据字符类型（数字、小数点、指数、符号）更新状态。
- 后续验证：遍历结束后，根据标记的状态判断字符串是否符合数字格式。
完整的规范代码
def isNumber(s): """ 逐步细化条件处理法判断字符串是否为有效的十进制数字 :param s: str, 输入字符串 :return: bool, 是否为有效的十进制数字 """ s = s.strip() num, dot, exp, numAfterE = False, False, False, False for i, char in enumerate(s): if char.isdigit(): num = True numAfterE = True elif char == '.': if dot or exp: return False dot = True elif char in "eE": if exp or not num: return False exp = True numAfterE = False elif char in "+-": if i > 0 and s[i-1] not in "eE": return False else: return False return num and numAfterE # 示例调用 print(isNumber("0")) # 输出: True print(isNumber("0.1")) # 输出: True print(isNumber("abc")) # 输出: False print(isNumber("1 a")) # 输出: False print(isNumber("2e10")) # 输出: True print(isNumber(" -90e3 ")) # 输出: True print(isNumber("1e")) # 输出: False print(isNumber("e3")) # 输出: False print(isNumber("6e-1")) # 输出: True print(isNumber("99e2.5")) # 输出: False print(isNumber("53.5e93")) # 输出: True print(isNumber("--6")) # 输出: False print(isNumber("-+3")) # 输出: False print(isNumber("95a54e53")) # 输出: False
算法分析
- 时间复杂度：(O(n))，需要遍历整个字符串一次。
- 空间复杂度：(O(1))，使用固定数量的标记变量。
方法五：分割加验证法
解题步骤
- 分割处理：首先检查并处理可能的空格，然后分割处理可能的指数部分。
- 验证各部分：单独验证整数/小数部分和指数部分的合法性。
- 组合结果：确保整数/小数部分和指数部分均合法。
完整的规范代码
def isNumber(s): """ 分割加验证法判断字符串是否为有效的十进制数字 :param s: str, 输入字符串 :return: bool, 是否为有效的十进制数字 """ s = s.strip() if 'e' in s or 'E' in s: parts = s.split('e') if 'e' in s else s.split('E') if len(parts) != 2: return False left, right = parts return (isDecimal(left) or isInteger(left)) and isInteger(right) else: return isDecimal(s) or isInteger(s) def isDecimal(part): if not part or (part[0] in '+-' and len(part) == 1): return False part = part[1:] if part[0] in '+-' else part dot_seen = False num_seen = False for char in part: if char.isdigit(): num_seen = True elif char == '.': if dot_seen: return False dot_seen = True else: return False return num_seen def isInteger(part): if not part: return False part = part[1:] if part[0] in '+-' else part return part.isdigit() # 示例调用 print(isNumber("0")) # 输出: True print(isNumber("0.1")) # 输出: True print(isNumber("abc")) # 输出: False print(isNumber("1 a")) # 输出: False print(isNumber("2e10")) # 输出: True print(isNumber(" -90e3 ")) # 输出: True print(isNumber("1e")) # 输出: False print(isNumber("e3")) # 输出: False print(isNumber("6e-1")) # 输出: True print(isNumber("99e2.5")) # 输出: False print(isNumber("53.5e93")) # 输出: True print(isNumber("--6")) # 输出: False print(isNumber("-+3")) # 输出: False print(isNumber("95a54e53")) # 输出: False
算法分析
- 时间复杂度：(O(n))，分割和验证各部分总共需要遍历字符串一次或多次。
- 空间复杂度：(O(1))，除了输入字符串外，使用了有限的额外空间。
不同算法的优劣势对比
| 特征 | 方法一: FSA | 方法二: 正则表达式 | 方法三: 分情况讨论 | 方法四: 逐步细化 | 方法五: 分割加验证 |
| 时间复杂度 | (O(n)) | (O(n)) | (O(n)) | (O(n)) | (O(n)) |
| 空间复杂度 | (O(1)) | (O(1)) | (O(1)) | (O(1)) | (O(1)) |
| 优势 | 明确状态转换，结构清晰 | 快速匹配，代码简洁 | 直观易理解，适用于多条件 | 状态清晰，逻辑简单 | 灵活处理复杂格式，模块化验证 |
| 劣势 | 状态表较复杂，需要细心设计 | 正则表达式复杂难以维护 | 条件多，代码冗长 | 多条件判断，容易出错 | 分割处理复杂，容易遗漏情况 |
应用示例
数据验证系统：
在数据导入和处理系统中，有效数字的验证是常见需求，特别是在处理来自不同来源的大量数据时。通过这些算法，系统能够确保数据的格式正确性，避免在后续的数据分析和计算中出现错误。这些方法可以应用于数据库数据清洗、科学计算输入验证等场景，提高系统的鲁棒性和数据处理的准确性。
欢迎关注微信公众号 数据分析螺丝钉
