[力扣_8] 字符串转换整数 (atoi)

题目入口:点击进入

相关算法:

  • 题目用到了编译原理,但是我看不懂...再琢磨琢磨
  • 字符串操作——时间复杂度O(n),空间复杂度O(1)

思路与算法:

根据题目要求,我们可以知道,我们需要丢弃前导空格字符,到达第一个非空字符上,那么第一步就是让指针走到非空字符的位置

在非空字符的时候,会出现以下情况:

  • 该非空字符为正号或者负号,遇到这种情况,则让指针后移一位,并且标记为正数或负数
  • 该非空字符为字符‘0’到‘9’,遇到这种情况,标记为正数
  • 该非空字符为其它字符,则直接返回0(因为不能转换)

在上述操作完成后,指针已经指向了0到9的字符上,亦或者正负号后面是其他字符,在此这种情况可以和后边的操作并同,无需进行多余的判断

我们定义一个高精度longlong类型的数,让他去存储字符串转化后的整数,转化规则如下:

  • num=num*10+(s[i]-'0')
  • 因为返回的是int类型,则如若转化的数大于了INT_MAX的话,就无需进行下一步转化,直接退出进行判断

由于num初始值为0,所以如若正负号后面的字符不是0到9的话,返回的则直接是0

转化后的数如果等于他的(int)类型的值,则未过界,满足条件,直接输出这个数乘以标记的值

转化后的数如果不等于他的int类型,则过界,根据题目要求,判断标记去返回INT_MAX或者INT_MIN

由于自己菜,只能想出这种臃肿的字符串操作方案,编译原理的自动机琢磨很久也不懂,暂时放着,上述思路时间复杂度测试后超过72.66%

答题代码如下:

int myAtoi(char * s){
    int sign;//标记
    int i=0;//指针
    while(i<strlen(s))
    {
       if(s[i]==' ') 
       {
           i++;
       }
       else if(s[i]=='-'||s[i]=='+')
       {
           if(s[i]=='-')
           {
               i++;
               sign=-1;
           }
           else{
               i++;
               sign=1;
           }
           break;
       }
       else if(s[i]>='0'&&s[i]<='9')
       {
           sign=1;
           break;
       }
       else
       {
           return 0;
       }
    }
    long long ReturnNum=0;
    while(s[i]>='0'&&s[i]<='9'&&ReturnNum<INT_MAX)//边界条件
    {
        ReturnNum=ReturnNum*10+(s[i]-'0');
        i++;
    }
    if(ReturnNum==(int)(ReturnNum))//根据标记判断返回值
    {
        return (ReturnNum*sign);
    }
    else{
        if(sign==1)
        {
            return INT_MAX;
        }
        return INT_MIN;
    }
}

若有大哥看完题解后有优化思路,可评论,采纳后有偿感谢

本文链接:

https://nullcode.fun/54.html
1 + 1 =
快来做第一个评论的人吧~