AI 助理
备案控制台
开发者社区 人工智能 文章 正文

LeetCode 题目 66：加一【python5种算法实现】

2024-06-09 42
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： LeetCode 题目 66：加一【python5种算法实现】

作者介绍：10年大厂数据\经营分析经验，现任大厂数据部门负责人。

会一些的技术：数据分析、算法、SQL、大数据相关、python

欢迎加入社区：码上找工作

作者专栏每日更新：

LeetCode解锁1000题: 打怪升级之旅

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）

解题步骤
  1. 定义状态：创建状态转换表，包括接受数字、符号、小数点、指数符号等状态。
  2. 初始化状态：初始状态设定为 start。
  3. 状态转移：根据当前字符和状态转换表更新状态。
  4. 终止检查：最终状态在接受状态集合中，则返回 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))，状态转换表的大小是常数。

方法二：正则表达式

解题步骤
  1. 定义正则表达式：使用正则表达式匹配可能的数字模式。
  2. 模式匹配：使用 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))，正则表达式的空间占用是常数。

方法三：分情况讨论

解题步骤
  1. 逐字符分析：逐个分析字符串中的字符，根据数字、小数点、指数部分、符号等进行分类处理。
  2. 状态标记：使用标志位记录是否出现过数字、小数点、指数等，以正确处理各种情况。
完整的规范代码
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))，只使用了几个辅助变量。### 方法四：逐步细化条件的处理
解题步骤
  1. 初始化变量：定义几个变量来标识数字状态，如是否遇到数字、小数点、指数等。
  2. 遍历字符串：逐字符检查，并根据字符类型（数字、小数点、指数、符号）更新状态。
  3. 后续验证：遍历结束后，根据标记的状态判断字符串是否符合数字格式。
完整的规范代码
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))，使用固定数量的标记变量。

方法五：分割加验证法

解题步骤
  1. 分割处理：首先检查并处理可能的空格，然后分割处理可能的指数部分。
  2. 验证各部分：单独验证整数/小数部分和指数部分的合法性。
  3. 组合结果：确保整数/小数部分和指数部分均合法。
完整的规范代码
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))
优势 明确状态转换，结构清晰 快速匹配，代码简洁 直观易理解，适用于多条件 状态清晰，逻辑简单 灵活处理复杂格式，模块化验证
劣势 状态表较复杂，需要细心设计 正则表达式复杂难以维护 条件多，代码冗长 多条件判断，容易出错 分割处理复杂，容易遗漏情况

应用示例

数据验证系统：

在数据导入和处理系统中，有效数字的验证是常见需求，特别是在处理来自不同来源的大量数据时。通过这些算法，系统能够确保数据的格式正确性，避免在后续的数据分析和计算中出现错误。这些方法可以应用于数据库数据清洗、科学计算输入验证等场景，提高系统的鲁棒性和数据处理的准确性。


欢迎关注微信公众号 数据分析螺丝钉


文章标签：
算法
数据挖掘
Python
数据采集
SQL
关键词：
LeetCode算法
Python算法
LeetCode题目
LeetCode python
leetcode python算法
数据分析螺丝钉
目录
相关文章
糜终
|
1月前
|
算法
Leetcode 初级算法 --- 数组篇
Leetcode 初级算法 --- 数组篇
糜终
38 0
小王老师呀
|
1天前
|
存储 算法 Java
leetcode算法题-有效的括号(简单)
【11月更文挑战第5天】本文介绍了 LeetCode 上“有效的括号”这道题的解法。题目要求判断一个只包含括号字符的字符串是否有效。有效字符串需满足左括号必须用相同类型的右括号闭合，并且左括号必须以正确的顺序闭合。解题思路是使用栈数据结构，遍历字符串时将左括号压入栈中，遇到右括号时检查栈顶元素是否匹配。最后根据栈是否为空来判断字符串中的括号是否有效。示例代码包括 Python 和 Java 版本。
小王老师呀
15 4
zzy的aly
|
28天前
|
存储 机器学习/深度学习 算法
蓝桥杯练习题(三)：Python组之算法训练提高综合五十题
蓝桥杯Python编程练习题的集合，涵盖了从基础到提高的多个算法题目及其解答。
zzy的aly
50 3
蓝桥杯练习题(三)：Python组之算法训练提高综合五十题
子午s
|
12天前
|
机器学习/深度学习 人工智能 算法
【车辆车型识别】Python+卷积神经网络算法+深度学习+人工智能+TensorFlow+算法模型
车辆车型识别，使用Python作为主要编程语言，通过收集多种车辆车型图像数据集，然后基于TensorFlow搭建卷积网络算法模型，并对数据集进行训练，最后得到一个识别精度较高的模型文件。再基于Django搭建web网页端操作界面，实现用户上传一张车辆图片识别其类型。
子午s
49 0
【车辆车型识别】Python+卷积神经网络算法+深度学习+人工智能+TensorFlow+算法模型
汀丶人工智能
|
17天前
|
机器学习/深度学习 算法 Java
机器学习、基础算法、python常见面试题必知必答系列大全：（面试问题持续更新）
机器学习、基础算法、python常见面试题必知必答系列大全：（面试问题持续更新）
汀丶人工智能
40 1
星霜旅人
|
23天前
|
算法
每日一道算法题（Leetcode 20）
每日一道算法题（Leetcode 20）
星霜旅人
21 2
子午s
|
25天前
|
机器学习/深度学习 人工智能 算法
【玉米病害识别】Python+卷积神经网络算法+人工智能+深度学习+计算机课设项目+TensorFlow+模型训练
玉米病害识别系统，本系统使用Python作为主要开发语言，通过收集了8种常见的玉米叶部病害图片数据集（'矮花叶病', '健康', '灰斑病一般', '灰斑病严重', '锈病一般', '锈病严重', '叶斑病一般', '叶斑病严重'），然后基于TensorFlow搭建卷积神经网络算法模型，通过对数据集进行多轮迭代训练，最后得到一个识别精度较高的模型文件。再使用Django搭建Web网页操作平台，实现用户上传一张玉米病害图片识别其名称。
子午s
50 0
【玉米病害识别】Python+卷积神经网络算法+人工智能+深度学习+计算机课设项目+TensorFlow+模型训练
可惜已不在
|
27天前
|
程序员 C语言
【C语言】LeetCode(力扣)上经典题目
【C语言】LeetCode(力扣)上经典题目
可惜已不在
24 1
糜终
|
1月前
|
算法 安全 Go
RSA加密算法详解与Python和Go实现
RSA加密算法详解与Python和Go实现
糜终
83 1
糜终
|
1月前
|
存储 算法 安全
Python 加密算法详解与应用
Python 加密算法详解与应用
糜终
20 1

热门文章

最新文章

  • 1
    【LeetCode从零单排】No88.Merge Sorted Array
  • 2
    # Leetcode 14：Longest Common Prefix 最长公共前缀
  • 3
    LeetCode 191 Number of 1 Bits（1 比特的数字们）
  • 4
    【LeetCode从零单排】No129 Sum Root to Leaf Numbers
  • 5
    LeetCode:Spiral Matrix I II
  • 6
    LeetCode 82 Remove Duplicates from Sorted List II（从已排序链表中移除重复元素）（Linked List）（*）
  • 7
    LeetCode 21：合并两个有序链表 Merge Two Sorted Lists
  • 8
    LeetCode每日一题——824. 山羊拉丁文
  • 9
    leetcode 搜索插入位置
  • 10
    Leetcode 14. 最长公共前缀
  • 1
    python语法错误（SyntaxError）
    155
  • 2
    python缩进错误（IndentationError）
    632
  • 3
    python中常见问题
    69
  • 4
    `certifi`是一个Python包，它提供了一个包含Mozilla证书颁发机构（CA）Bundle的PEM文件。
    296
  • 5
    `bandit`是一个Python静态代码分析工具，专注于查找常见的安全漏洞，如SQL注入、跨站脚本（XSS）等。
    118
  • 6
    `nmap`是一个开源的网络扫描工具，用于发现网络上的设备和服务。Python的`python-nmap`库允许我们在Python脚本中直接使用`nmap`的功能。
    139
  • 7
    `roslibpy`是一个Python库，它允许非ROS（Robot Operating System）环境（如Web浏览器、移动应用等）与ROS环境进行交互。通过使用`roslibpy`，开发者可以编写Python代码来远程控制ROS节点，发布和订阅话题，以及调用服务。
    279
  • 8
    Dask是一个用于并行计算的Python库，它提供了类似于Pandas和NumPy的API，但能够在大型数据集上进行并行计算。
    223
  • 9
    Numba是一个Python库，用于对Python代码进行即时（JIT）编译，以便在硬件上高效执行。
    145
  • 10
    `surprise`是一个用于构建和分析推荐系统的Python库。
    114

    • 相关课程

    更多
  • 高校精品课-华东师范大学 - Python数据科学基础与实践
  • 【科技少年】Python基础语法
  • 【科技少年】Python绘画编程第一课
  • Go语言核心编程 - 数据结构和算法
  • 神经网络概览及算法详解

    • 相关电子书

    更多
  • 数据+算法定义新世界
  • 袋鼠云基于实时计算的反黄牛算法
  • Alink：基于Apache Flink的算法平台

    • 相关实验场景

    更多
  • 推荐系统入门之使用ALS算法实现打分预测
  • Python新手入门
  • Python入门
  • 欧拉图的构造性证明与算法实现
  • Python选择及循环结构
  • RSA非对称加密算法

    • 推荐镜像

    更多
  • python-release
  • nodejs-release
  • golang
    • 下一篇
    DataWorks售前咨询