数据结构学习 jz67 把字符串转换成整数

关键词：字符串 溢出处理

题目：把字符串转换成整数 (atoi)

这道题要充分了解需求（测试用例）才能顺利做完。

方法一：[ 用时: 34 m 26 s ] 基于测试用例的程序设计 调试了很久 总之就是分类讨论就可以了，为了防止溢出我用了long。

方法二：似乎是不能用long，所以看了题解，学会了如何处理溢出。

?

方法一：

思路：

就是分类讨论。

这里我用了long long

long long res=0;//要long或者long long不然会溢出

a是判断这个数是正数还是负数，默认为正数，1。

?isnum是判断前面的数是否为有效数字。

直接看代码注释吧。

复杂度计算：

时间复杂度O(n)

空间复杂度O(1)

代码：

class Solution {
public:
    int myAtoi(string str) {
        long long res=0;//要long或者long long不然会溢出
        int a =1;//记录正负
        bool isnum=false;//记录前面是否有有效数字
        for(int i=0;i<str.size();i++)
        {
            if(!isnum) //如果前面没有有效数字
            {
                if(str[i]==' ')//是空格，跳过
                {
                    continue;
                }else if(str[i]=='-')//是负号，说明有有效数字
                {
                    isnum=true;//有有效数字
                    a=-1;//改变a的符号
                    continue;
                }else if(str[i]=='+')//是正号，说明有有效数字
                {
                    isnum=true;
                    continue;
                }
                else if(str[i]>='0'&&str[i]<='9')//是数字，这里因为前面没有正负号所以默认正好，a==1
                {
                    isnum=true;
                    res+=str[i]-'0';//注意是从符号装顺序
                }
                else//啥都不是返回空
                {
                    return res;
                }
            }
            else//如果前面有有效数字
            {
                if(str[i]>='0'&&str[i]<='9')//继续接数字
                {
                    res=(str[i]-'0')+res*10;//因为是从高位读到低位，所以乘10（左移）
                    if(res*a>INT_MAX) return INT_MAX;//如果溢出，直接返回
                    if(res*a<INT_MIN) return INT_MIN;
                }
                else//如果是非数字，那么返回结果，别忘了符号
                {
                    return res*a;
                }
            }
        }
        return res*a;
    }
};

方法二：

和方法一相比，改了对溢出的处理，没用long。

思路：

越界处理（有用，值得学习）：

这里我是看了k神的答案：

总之就是，在越界之前防患于未然

int bndry=INT_MAX/10;
    if(res>bndry||(res==bndry&&str[i]-'0'>7))
        return a==1?INT_MAX:INT_MIN;

复杂度计算：

时间复杂度O(n)

空间复杂度O(1)

代码：

class Solution {
public:
    int myAtoi(string str) {
        int res=0;
        int bndry=INT_MAX/10;
        int a =1;
        bool isnum=false;
        for(int i=0;i<str.size();i++)
        {
            if(!isnum) 
            {
                if(str[i]==' ')
                {
                    continue;
                }else if(str[i]=='-')
                {
                    isnum=true;
                    a=-1;
                    continue;
                }else if(str[i]=='+')
                {
                    isnum=true;
                    continue;
                }
                else if(str[i]>='0'&&str[i]<='9')
                {
                    isnum=true;
                    res+=str[i]-'0';
                }
                else
                {
                    return res;
                }
            }
            else
            {
                if(str[i]>='0'&&str[i]<='9')
                {
                    if(res>bndry||(res==bndry&&str[i]-'0'>7))
                        return a==1?INT_MAX:INT_MIN;
                    res=(str[i]-'0')+res*10;
                }
                else
                {
                    return res*a;
                }
            }
        }
        return res*a;
    }
};