+关注
已关注

分类  

暂无分类

标签  

暂无标签

日期归档  

2019-07(2)

2019-08(100)

2019-09(94)

2019-10(12)

2019-11(4)

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

发布于2020-02-10 17:34     阅读(734)     评论(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万+


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

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

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

来源: python黑洞网

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

10 0
收藏该文
已收藏

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