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差很多