+关注
已关注

分类  

暂无分类

标签  

暂无标签

日期归档  

2019-07(2)

2019-08(100)

2019-09(94)

2019-10(12)

2019-11(4)

2019-12(12)

2020-01(19)

2020-02(22)

每日LeetCode之Math类--8. 字符串转换整数 (atoi)(C, Python)

发布于2020-02-10 17:34     阅读(639)     评论(0)     点赞(10)     收藏(3)


1. 问题描述与分析

问题描述:
在这里插入图片描述
在这里插入图片描述
问题分析:
该算法题难度属于medium,需要注意的点有以下几个:

  • 只去掉字符串第一个非空字符前面的空格字符,中间的空格字符和末尾的不用去掉
  • 正负号‘-’‘+’只有在第一个非空格字符时才有效,而且后面必须是数字
  • 数字必须是连续的才可以,比如‘ 123 98’的输出应该是‘123’
  • 需要对输出的数字进行上下界限的判断

2. C语言实现

C语言实现的过程为:
① 清除字符串首的空格字符,直到遇到非空格字符为止
② 设立标志位记录字符串是否有“+”“-” 以及输出结果的正负
③ 寻找之后的连续数字并判断是否在界限范围内
具体实现代码为:

int myAtoi(char * str){
    // 移除开头的空格
    while(*str == ' ')
        ++str;

    // 记录正负性
    int flag = 1;
    if (*str == '-') {
        flag = -1;
        ++str;
    }
    else if (*str == '+')
        ++str;

    int ret = 0;
    // 因为只能使用 32 位 int,因此将 ret 乘 10 后再与 INT_MAX 比较可能会溢出
    // 因此使用 ret 与 INT_MAX/10 比较
    int div = INT_MAX / 10;
    while (*str <= '9' && *str >= '0') {
        int dig = *str - '0';
        // 若 ret 比 div 小,则 ret * 10 + dig 也一定小于 INT_MAX,不会溢出
        // 若 ret 与 div 相等,只有 dig 比 8 小时不会溢出
        // 此处本来需要正负分开讨论,INT_MAX 个位是 7,INT_MIN 个位是 8
        // -INT_MIN 在 int 中会溢出,当 dig == 8 时直接当作溢出处理
        if (ret < div || (ret == div && dig < 8)) {
            ret = ret * 10 + dig;
            ++str;
        }
        // 溢出,根据正负性返回值
        else
            return (flag == 1? INT_MAX: INT_MIN);
    }
    return flag * ret;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34

运行结果为:
在这里插入图片描述

3. Python实现

3.1 普通判断法

python实现的思路与C一致,只是实现的代码有些许不同,具体代码为:

class Solution:
    def myAtoi(self, str: str) -> int:
    	# 变量初始化
        INT_MAX = 2147483647
        INT_MIN = -2147483648
        sign = ['-', '+']
        num = [ '1', '2', '3', '4', '5', '6', '7', '8', '9', '0']
        flag = 1
        # 清楚字符串首的空格字符
        str_new = str.lstrip()
        str_output = ''
        # 如果新生成的字符串为空,返回0
        if str_new == '':
            return 0
        # 如果第一个非空格字符不在 sign 或者 num 中,返回0
        elif str_new[0] not in sign and str_new[0] not in num:
            return 0
        # 如果第一个非空格字符是正负号且字符串长度为1,返回0
        elif str_new[0] in sign and len(str_new)==1:
            return 0
        # 如果第一个是正负号,第二个不是数字,返回0
        elif str_new[0] in sign and str_new[1] not in num:
            return 0
        else:
            # 遍历新生成的字符串,将连续的数字存储在str_output中
            str_output += str_new[0]
            for i in range(1,len(str_new)):
                if str_new[i] in num and flag == i:
                    str_output += str_new[i]
                    flag += 1
                else:
                	# 输出在界限内的值
                    return max(min(int(str_output),INT_MAX),INT_MIN)
        # 输出在界限内的值
        return max(min(int(str_output),INT_MAX),INT_MIN)
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35

运行结果为:
在这里插入图片描述

3.2 正则表达式法

正则表达式就是为解决这种问题而生的,是非常简洁和高效地,我们来看一下具体的实现代码:

class Solution:
    def myAtoi(self, str: str) -> int:
        INT_MAX = 2147483647    
        INT_MIN = -2147483648
        str = str.lstrip()      #清除左边多余的空格
        num_re = re.compile(r'^[\+\-]?\d+')   #设置正则规则
        num = num_re.findall(str)   #查找匹配的内容
        num = int(*num) #由于返回的是个列表,解包并且转换成整数
        return max(min(num,INT_MAX),INT_MIN)    #返回值
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

运行结果为:
在这里插入图片描述
更简洁的代码可以写成:

class Solution:
    def myAtoi(self, s: str) -> int:
        return max(min(int(*re.findall('^[\+\-]?\d+', s.lstrip())), 2**31 - 1), -2**31)
  • 1
  • 2
  • 3

运行结果为:
在这里插入图片描述
心得:虽然python写起来比较简单,但是在runtime上还是和C差很多

发布了117 篇原创文章 · 获赞 179 · 访问量 10万+


所属网站分类: 技术文章 > python文章

作者:爸爸去挣钱我去幼儿园

链接: http://www.pythonheidong.com/blog/article/231024/

来源:python黑洞网 www.pythonheidong.com

任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任

10 0

赞一赞 or 踩一踩

收藏该文
已收藏

评论内容:(最多支持255个字符)

相似文章

  5171. 最接近的因数

  Python实现生成西瓜数据集的Excel文件

  Leetcode - 删除排序数组中的重复项

  python第五天-字符串

  数据结构|LeetCode(力扣)经典题:队列

  python学习笔记(3)

  TYD_初识python数据可视化库-Matplotlib

  Scrapy安装与应用教程

  python实现修改文件中的内容

  mac环境下python3.6安装pyhanlp工具包

优质资源排行榜

 python经典电子书大合集下载 下载次数 8138

 零基础java开发工程师视频教程全套,基础+进阶+项目实战(152G) 下载次数 7550

 零基础前端开发工程师视频教程全套,基础+进阶+项目实战(共120G) 下载次数 7442

 零基础大数据全套视频400G 下载次数 7006

 零基础php开发工程师视频教程全套,基础+进阶+项目实战(80G) 下载次数 6893

 零基础软件测试全套系统教程 下载次数 6506

 全套人工智能视频+pdf 下载次数 6443

 IOS全套视频教程 基础班+就业班 下载次数 4680

 编程小白的第一本python入门书(高清版)PDF下载 下载次数 3648

10  effective python编写高质量Python代码的59个有效方法 pdf下载 下载次数 3361

11  Python深度学习 pdf下载 下载次数 3156

12  笨办法学python pdf下载 下载次数 3087

13  Python Cookbook第三版中文PDF下载高清完整扫描原版 下载次数 3024

14  树莓派Python编程指南 pdf下载 下载次数 3011

15  python从入门到精通视频(全60集)python视频教程下载 下载次数 3009

16  python项目开发视频 下载次数 3002

17  使用python+pygame开发的小游戏《嗷大喵快跑》源码下载 下载次数 3000

18  黑马2017年java就业班全套视频教程 下载次数 2992

19  Python基础教程 pdf下载 下载次数 2988

20  python实战项目 平铺图像板系统源码下载,适用于想要保存,标记和共享图像,视频和网页的用户 下载次数 2987

21  利用python实现程序内存监控脚本 下载次数 2987

22  老男孩python自动化视频 下载次数 2983

23  老王python基础+进阶+项目视频教程 下载次数 2974

24  尚硅谷Go学科全套视频 下载次数 2972

25  某硅谷Python项目+AI课程+核心基础视频教程 下载次数 2968

26  Web前端实战精品课程 下载次数 2967

27  Python算法教程_中文版 pdf下载 下载次数 2966

28  tron python小游戏 下载次数 2963

29  [小甲鱼]零基础入门学习Python 下载次数 2962

30  老男孩python全栈开发15期 下载次数 2958

31  2017最新web前端开发完整视频教程附源码 下载次数 2948

32  最新全套完整JAVAWEB2018开发视频 下载次数 2926

33  流畅的Python PDF下载高清完整扫描原版 下载次数 2919

34  Spring boot实战视频6套下载 下载次数 2910

35  python全套视频十五期(116G) 下载次数 2908

36  Python高性能编程 pdf下载 下载次数 2906

37  Python项目实战 下载次数 2887

38  30个小时搞定Python网络爬虫 含源码 下载次数 2884

39  简明python教程 (A Byte of Python)pdf下载 下载次数 2884

40  利用Python进行数据分析 pdf下载 下载次数 2884

41  python全自动抢火车票教程-python视频教程下载 下载次数 2883

42  尚硅谷大数据之Hadoop视频 下载次数 2876

43  Python A~B~C~ python视频教程下载 下载次数 2866

44  数据结构与算法视频(小甲鱼讲解-全) 下载次数 2864

45  web小程序表白天数倒计时源码下载 下载次数 2863

46  python基础视频教程 下载次数 2862

47  go语言全套视频 下载次数 2855

48  清华学霸尹成Python爬虫视频-ok 下载次数 2846

49  黑马前端36期最全视频和代码 下载次数 2843

50  2018最新全套web前端视频教程+源码下载 下载次数 2841