题解 | #把字符串转换成整数#

描述
        将一个字符串转换成一个整数，要求不能使用字符串转换整数的库函数。 数值为0或者字符串不是一个合法的数值则返回0
输入描述：
        输入一个字符串,包括数字字母符号,可以为空
返回值描述：
        如果是合法的数值表达则返回该数字，否则返回0
示例1
输入："+2147483647"
返回值：2147483647
请在这里输入引用内容
示例2
输入："1a33"
返回值：0

方法一：逐个遍历并将字符转数字
        由题意可知输入的字符串转化为整数，而整数的定义只能是数字。而输入的字符串可能包括数字、符号、空格和英文字符。因此当字符串中存在英文字符则不符合题意；而符号位则表示最后的数字是正数还是负数，这里使用一个标志位记录即可；空格字符可以直接跳过；数字字符需要转化为对应的数字，采用ASCII转化即可。

图解：

核心代码：（C++）

int StrToInt(string str) {
    int index = 0, flag = 1, len = str.size();   //标志位flag=1为正数；flag=-1为负数
    long long result = 0; 
    while (str[index] == ' ')      //过滤掉字符串前面的空格
        index ++;
    if(str[index] == '-' || str[index] == '+') {    //符号位判断，确定数字的正负
        if(str[index] == '-')      //负数的时候更改标志位
            flag = -1;
        index ++;
    } 

    while(index < len && isdigit(str[index])){      //循环转化字符串的每一位
        result = result * 10 + (str[index] - '0');     //计算的时候刚好是反过来的，比如123，则可以逐步分解为1 => 1*10+2 => (1*10+2)*10+3
        if(result >= INT_MAX && flag == 1)        //超过int的最大范围
            return INT_MAX;
        if(result > INT_MAX && flag == -1)      //小于int的最小范围
            return INT_MIN;
        index++;
    }
    if(index == len)
        return flag * result;
    else     //index<len表明字符串中存在英文字符
        return 0;
}

复杂度分析：
        代码使用了循环，循环次数为数组大小，因此该方法的时间复杂度为O(N)。由于没有采用额外的数组空间，空间复杂度为O(1)

时间复杂度O(n)
空间复杂度O(1)

方法二：采用正则匹配
        使用Python语言编写，采用Python里面的正则表达式解决字符判断和匹配的问题。具体步骤如下
1）首先去掉字符串的空格
2）如果是空字符串则直接返回0，否则进一步处理
3）存在+-标志位，则记录该标志位，并清理标志位
4）如果字符串只有空格和标志位，则直接返回0，否则进一步处理
5）匹配字符串中的英文字符，如果匹配上则不符合题意，直接返回0
6）将数字字符转转化为整型数字，同时根据标志位更新整型数字标志位并返回结果

核心代码：（Python）

def StrToInt(self, s):
    import re
    s = s.strip()    #去掉空格
    if len(s) > 0:
        flag = True
        if s[0] == '-':      #判断标志位
            flag = False
        s = s.strip("+-")     #去掉正负标志位
        if len(s) > 0:
            pattern = re.compile(r'[a-zA-Z]')     #匹配英文字符
            result = re.search(pattern, s)    #该方***扫描整个字符串
            if not result:                   #未匹配上英文字符
                result = int(result)    #将数字字符串转化为数字
                if not flag:          #判断并更新标志位
                    result = -result
                return result
    return 0

复杂度分析：
        代码search函数查找字符串数组，即扫描字符串，相当于遍历数组，因此该方法的时间复杂度为O(N)。由于采用了额外的数组空间，空间复杂度为O(N)

时间复杂度O(n)
空间复杂度O(1)