【力扣算法11】之 8. 字符串转换整数 (atoi) python

简介: 【力扣算法11】之 8. 字符串转换整数 (atoi) python

问题描述

请你来实现一个 myAtoi(string s) 函数,使其能将字符串转换成一个 32 位有符号整数(类似 C/C++ 中的 atoi 函数)。

函数 myAtoi(string s) 的算法如下:

  1. 读入字符串并丢弃无用的前导空格
  2. 检查下一个字符(假设还未到字符末尾)为正还是负号,读取该字符(如果有)。 确定最终结果是负数还是正数。 如果两者都不存在,则假定结果为正。
  3. 读入下一个字符,直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。
  4. 将前面步骤读入的这些数字转换为整数(即,“123” -> 123, “0032” -> 32)。如果没有读入数字,则整数为 0 。必要时更改符号(从步骤 2 开始)。
  5. 如果整数数超过 32 位有符号整数范围 [−231, 231 − 1] ,需要截断这个整数,使其保持在这个范围内。具体来说,小于 −231 的整数应该被固定为 −231 ,大于 231 − 1 的整数应该被固定为 231 − 1 。
  6. 返回整数作为最终结果。注意:
  • 本题中的空白字符只包括空格字符 ’ ’ 。
  • 除前导空格或数字后的其余字符串外,请勿忽略 任何其他字符。

示例1

输入:s = "42"
输出:42
解释:加粗的字符串为已经读入的字符,插入符号是当前读取的字符。
第 1 步:"42"(当前没有读入字符,因为没有前导空格)
         ^
第 2 步:"42"(当前没有读入字符,因为这里不存在 '-' 或者 '+')
         ^
第 3 步:"42"(读入 "42")
           ^
解析得到整数 42 。
由于 "42" 在范围 [-231, 231 - 1] 内,最终结果为 42 。

示例2

输入:s = "   -42"
输出:-42
解释:
第 1 步:"   -42"(读入前导空格,但忽视掉)
            ^
第 2 步:"   -42"(读入 '-' 字符,所以结果应该是负数)
             ^
第 3 步:"   -42"(读入 "42")
               ^
解析得到整数 -42 。
由于 "-42" 在范围 [-231, 231 - 1] 内,最终结果为 -42 。

示例3

输入:s = "4193 with words"
输出:4193
解释:
第 1 步:"4193 with words"(当前没有读入字符,因为没有前导空格)
         ^
第 2 步:"4193 with words"(当前没有读入字符,因为这里不存在 '-' 或者 '+')
         ^
第 3 步:"4193 with words"(读入 "4193";由于下一个字符不是一个数字,所以读入停止)
             ^
解析得到整数 4193 。
由于 "4193" 在范围 [-231, 231 - 1] 内,最终结果为 4193 。

提示

  • 0 <= s.length <= 200
  • s 由英文字母(大写和小写)、数字(0-9)、’ ‘、’+‘、’-’ 和 ‘.’ 组成

思路分析

  1. 去除无用的前导空格:使用strip()函数去除字符串前后的空格。
  2. 检查符号位:判断第一个字符是否为正号或负号,若是则记录正负号,并将剩下的字符串赋给变量s。
  3. 读取数字字符并转换为整数:遍历字符串s的每个字符,判断是否为数字字符,如果是则将其转换为整数并累加到result中;如果遇到非数字字符,则跳出循环。
  4. 处理溢出情况:根据符号位判断最终结果的正负,并判断是否超出32位有符号整数范围[-2^31, 2^31-1],如果超出则返回范围边界值,否则返回result作为最终结果。

代码分析

  1. 读入字符串并丢弃无用的前导空格:使用 strip() 函数去除字符串前后的空格,将处理后的结果重新赋值给变量 s。这样可以消除输入字符串头部和尾部的空格。
  2. 检查符号:定义变量 sign 并初始化为 1(正号)。如果字符串 s 非空,并且第一个字符是正号或负号,则根据符号字符决定 sign 的值。如果第一个字符是负号,则将 sign 赋值为 -1,并将剩下的字符串赋给变量 s。这样可以确定最终结果的正负。
  3. 读取数字字符并转换为整数:定义变量 result 并初始化为 0。使用循环遍历变量 s 的每个字符 c,判断字符 c 是否是数字字符。如果是,将其转换为整数并累加到 result 上,通过乘以 10 来实现每次累加位数的增加。如果遇到非数字字符,跳出循环。这样可以逐个读取字符串中的数字字符,并计算出对应的整数值。
  4. 处理溢出情况:将 result 乘以符号位 sign,得到处理后的结果。然后进行溢出判断,如果结果小于下界 -2^31,则返回下界值 -2^31。如果结果大于上界 2^31-1,则返回上界值 2^31-1。否则,返回结果 result 作为最终结果。

完整代码

class Solution(object):
    def myAtoi(self, s):
        """
        :type s: str
        :rtype: int
        """ 
        # 1. 读入字符串并丢弃无用的前导空格
        s = s.strip()  # 去除字符串首尾的空格
        # 2. 检查符号
        sign = 1  # 符号,默认为正号
        if s and (s[0] == '+' or s[0] == '-'):  # 判断第一个字符是否为正号或负号
            if s[0] == '-':  # 如果为负号
                sign = -1  # 将符号设置为负号
            s = s[1:]  # 去除字符串中的符号部分,更新字符串 s
        # 3. 读取数字字符并转换为整数
        result = 0  # 用于记录最终结果的变量
        for c in s:  # 遍历字符串中的每个字符
            if not c.isdigit():  # 如果字符不是数字字符
                break  # 跳出循环
            result = result * 10 + int(c)  # 将字符转换为整数,并累加到结果中
        # 4. 处理溢出情况
        result = sign * result  # 根据符号位确定最终结果的正负
        if result < -2**31:  # 判断是否小于下界
            return -2**31  # 返回下界值
        elif result > 2**31 - 1:  # 判断是否大于上界
            return 2**31 - 1  # 返回上界值
        else:
            return result  # 返回计算得到的结果作为最终结果

详细分析


  • s = s.strip(): 去除字符串首尾的空格。strip() 方法用于移除字符串中指定字符,默认为空格。
  • sign = 1: 初始化符号变量为正号。符号用于表示最终整数是正数还是负数。
  • if s and (s[0] == '+' or s[0] == '-'):: 判断第一个字符是否为正号或负号。
  • 判断条件中的 s 是一个非空字符串,因此判断 s 是否为真意味着检查字符串是否为空。
  • 如果第一个字符是 -,将符号变量 sign 设置为负号。
  • 无论第一个字符是 + 还是 -,都需要去除字符串中的符号部分,所以将字符串 s 更新为去除了第一个字符的子串。
  • result = 0: 初始化用于记录最终结果的变量。默认情况下,结果为0。
  • for c in s:: 遍历字符串中的每个字符。
  • 对于遍历到的每个字符c
  • if not c.isdigit():: 如果字符不是数字字符(即不是0-9的数字),则跳出循环。
  • 否则,将字符转换为整数,并将其累加到结果变量 result 中。通过将 result 乘以10,可以将当前字符添加到 result 的个位数位置。
  • result = sign * result: 根据符号变量 sign 确定最终结果的正负。如果 sign 为1,则结果为正数;如果 sign 为-1,则结果为负数。
  • if result < -2**31:: 判断是否小于下界-2**31(即 -2147483648)。
  • 如果结果小于下界,表示整数溢出,因此返回下界值 -2**31
  • elif result > 2**31 - 1:: 判断是否大于上界2**31 - 1(即 2147483647)。
  • 如果结果大于上界,表示整数溢出,因此返回上界值 2**31 - 1
  • else:: 如果结果没有溢出,返回计算得到的结果作为最终结果。

这个代码段用于将给定的字符串 s 转换为整数。它处理了输入字符串的空格、符号和非数字字符,以及整数溢出的情况,并返回相应的结果。


运行效果截图

调用示例


solution = Solution()
s = "42"
s1 = "   -42"
s2 = "4193 with words"
print(solution.myAtoi(s))
print(solution.myAtoi(s1))
print(solution.myAtoi(s2))

运行结果

完结

相关文章
|
11天前
|
机器学习/深度学习 人工智能 算法
猫狗宠物识别系统Python+TensorFlow+人工智能+深度学习+卷积网络算法
宠物识别系统使用Python和TensorFlow搭建卷积神经网络,基于37种常见猫狗数据集训练高精度模型,并保存为h5格式。通过Django框架搭建Web平台,用户上传宠物图片即可识别其名称,提供便捷的宠物识别服务。
142 55
|
26天前
|
搜索推荐 Python
利用Python内置函数实现的冒泡排序算法
在上述代码中,`bubble_sort` 函数接受一个列表 `arr` 作为输入。通过两层循环,外层循环控制排序的轮数,内层循环用于比较相邻的元素并进行交换。如果前一个元素大于后一个元素,就将它们交换位置。
126 67
|
26天前
|
存储 搜索推荐 Python
用 Python 实现快速排序算法。
快速排序的平均时间复杂度为$O(nlogn)$,空间复杂度为$O(logn)$。它在大多数情况下表现良好,但在某些特殊情况下可能会退化为最坏情况,时间复杂度为$O(n^2)$。你可以根据实际需求对代码进行调整和修改,或者尝试使用其他优化策略来提高快速排序的性能
118 61
|
20天前
|
机器学习/深度学习 人工智能 算法
【宠物识别系统】Python+卷积神经网络算法+深度学习+人工智能+TensorFlow+图像识别
宠物识别系统,本系统使用Python作为主要开发语言,基于TensorFlow搭建卷积神经网络算法,并收集了37种常见的猫狗宠物种类数据集【'阿比西尼亚猫(Abyssinian)', '孟加拉猫(Bengal)', '暹罗猫(Birman)', '孟买猫(Bombay)', '英国短毛猫(British Shorthair)', '埃及猫(Egyptian Mau)', '缅因猫(Maine Coon)', '波斯猫(Persian)', '布偶猫(Ragdoll)', '俄罗斯蓝猫(Russian Blue)', '暹罗猫(Siamese)', '斯芬克斯猫(Sphynx)', '美国斗牛犬
110 29
【宠物识别系统】Python+卷积神经网络算法+深度学习+人工智能+TensorFlow+图像识别
|
1天前
|
存储 算法 Python
文件管理系统中基于 Python 语言的二叉树查找算法探秘
在数字化时代,文件管理系统至关重要。本文探讨了二叉树查找算法在文件管理中的应用,并通过Python代码展示了其实现过程。二叉树是一种非线性数据结构,每个节点最多有两个子节点。通过文件名的字典序构建和查找二叉树,能高效地管理和检索文件。相较于顺序查找,二叉树查找每次比较可排除一半子树,极大提升了查找效率,尤其适用于海量文件管理。Python代码示例包括定义节点类、插入和查找函数,展示了如何快速定位目标文件。二叉树查找算法为文件管理系统的优化提供了有效途径。
33 5
|
21小时前
|
算法 容器
【算法】——双指针算法合集(力扣)
移动零,复写零,快乐数,盛最多水的容器,有效三角形的个数,和为s的两个数(查找总价格为目标值的两个商品 ),三数之和,四数之和
|
1天前
|
存储 缓存 算法
探索企业文件管理软件:Python中的哈希表算法应用
企业文件管理软件依赖哈希表实现高效的数据管理和安全保障。哈希表通过键值映射,提供平均O(1)时间复杂度的快速访问,适用于海量文件处理。在Python中,字典类型基于哈希表实现,可用于管理文件元数据、缓存机制、版本控制及快速搜索等功能,极大提升工作效率和数据安全性。
19 0
|
1天前
|
机器学习/深度学习 算法
基于改进遗传优化的BP神经网络金融序列预测算法matlab仿真
本项目基于改进遗传优化的BP神经网络进行金融序列预测,使用MATLAB2022A实现。通过对比BP神经网络、遗传优化BP神经网络及改进遗传优化BP神经网络,展示了三者的误差和预测曲线差异。核心程序结合遗传算法(GA)与BP神经网络,利用GA优化BP网络的初始权重和阈值,提高预测精度。GA通过选择、交叉、变异操作迭代优化,防止局部收敛,增强模型对金融市场复杂性和不确定性的适应能力。
103 80
|
20天前
|
算法
基于WOA算法的SVDD参数寻优matlab仿真
该程序利用鲸鱼优化算法(WOA)对支持向量数据描述(SVDD)模型的参数进行优化,以提高数据分类的准确性。通过MATLAB2022A实现,展示了不同信噪比(SNR)下模型的分类误差。WOA通过模拟鲸鱼捕食行为,动态调整SVDD参数,如惩罚因子C和核函数参数γ,以寻找最优参数组合,增强模型的鲁棒性和泛化能力。
|
6天前
|
供应链 算法 调度
排队算法的matlab仿真,带GUI界面
该程序使用MATLAB 2022A版本实现排队算法的仿真,并带有GUI界面。程序支持单队列单服务台、单队列多服务台和多队列多服务台三种排队方式。核心函数`func_mms2`通过模拟到达时间和服务时间,计算阻塞率和利用率。排队论研究系统中顾客和服务台的交互行为,广泛应用于通信网络、生产调度和服务行业等领域,旨在优化系统性能,减少等待时间,提高资源利用率。