[数据结构与算法]leecode-C语言实现-8. 字符串转换整数 (atoi)

一、题目




二、解题思路
（1）思路一
此题开始的时候一定要多读几遍题目，可以少绕一些弯路，我是通过解题错误来分析leecode是想要什么的样的结果的，总结为leecode想从一个空格+正负号+数字字符+字母字符中把数字字符转换成数字，我的思路是：

1、例如字符串为：“w o r d s a n d 0 0 a 0 9 8 7”，遍历元素到第一个数字字符，得到第一个数组的下标，再进行前推前面这一段字符串（指的是0-w反推）是否合规，如果有点、a-z直接返回0并退出程序，如果没有w o r d s a n d字符串，可以继续下走。

2、例如字符串为：" 0 0 a 0 9 8 7"，会检查0前面一位是正号还是负号还是无符号。再判断0-9之间是否有除0以外的其它字符，有的话直接返回0并退出程序，如果没有a字符串，可以继续下走。

3、例如字符串为：" 0 0 0 9 8 7"，筛选出987三个字符，判断其是否的字符个数
如果大于10，因为结果在范围 [-2 ^31, 2 ^31 - 1] 内， 2 ^31 - 1 等于2147483647，正好10位，超出直接返回极值退出程序。

如果小于10，前面记录有效位数的变量就用上了，987三位，变量的值为三
9 x 10^(3-1)=900
8 x 10^(2-1)=80
7 x 10^(1-1)=7
相加等于987返回结果。

如果等于10，我会定义一个数组记录极值除最后一位{2,1,4,7,4,8,3,6,4}，少一个7或8，先逐一比较，大于直接返回极值，等于的话一定要判断到最后一位是否相等，小于的话一直累加。

建议大家看着代码，再就着上面的文字描述结合起来看，多动手多练就一定没错的。

三、虚机测试代码

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>

void main()
{
    void PrintfArr(void *arr, int size ,int elementsize);

    int myAtoi(char * s);
    int res;
    char s[] = "    +1234567890 savreve";
    PrintfArr(s,sizeof(s) / sizeof(char),sizeof(char));
    res = myAtoi(s);
    printf("res : %d\n",res);
}

int myAtoi(char * s)
{
    int StrLens = strlen(s);
    if(StrLens == 0)
    {
        return 0;
    }
    else if(StrLens == 1)
    {
        if(s[0] < '0' || s[0] > '9')
        {
            return 0;
        }
    }
    int CharNum2IntNum(char c);
    void PrintfArr(void *arr, int size ,int elementsize);
    int CheckNumValid(int *arr,int character,int validlen);

    int i;
    int res = 0;
    int ArrSize = 20;
    int ValidArrLen = 0;
    int character;//1 : + , -1 : -
    int *IntArr = malloc(sizeof(int) * ArrSize);

    for(i=0; i<ArrSize; i++)
    {
        IntArr[i] = -1;
    }

    //作用：取数字前的正负号
    //第零位是数字为正号
    //零之后的索引位，判断前一位是正还是负
    //上述情况都不符合为正

    for(i=0; (s[i]<'0' || s[i]>'9') && i < StrLens; i++)
    {
    }

    //判断0-9数字之前的字符是否合规    
    for(int j=i-1; j>=0; j--)
    {
        if(j <= i-2 && (s[j] == '+' || s[j] == '-' ||  s[j] == '0'))
        {
            return 0;
        }
        else if(s[j] >= 'a' && s[j] <= 'z' || s[j] == '.')
        {
            return 0;
        }
    }

    if(i == 0)
    {
        character = 1;
    }
    else if(s[i-1] == '+')
    {
        character = 1;
    }
    else if(s[i-1] == '-')
    {
        character = -1;
    }
    else
    {
        character = 1;
    }

    for(; (s[i]<'1' || s[i]>'9') && i < StrLens; i++)
    {
        if(s[i] != '0')
        {
            return 0;
        }
    }
    printf("s[%d] : %c\n",i,s[i]);

    //将字符数字转换成整形数字
    for(;s[i]>='0' && s[i]<='9'; i++)
    {
        IntArr[ValidArrLen] = CharNum2IntNum(s[i]);;
        ValidArrLen++;
        if(ValidArrLen > 10 && character == 1)
        {
            return 2147483647;
        }
        else if(ValidArrLen > 10 && character == -1)
        {
            return -2147483648;
        }        
    }
    printf("ValidArrLen : %d\n",ValidArrLen);
    PrintfArr(IntArr,ArrSize,sizeof(int));
    return CheckNumValid(IntArr,character,ValidArrLen);;
}

/**
 * 参数介绍：
 * arr:数组。
 * chararcter:正负号，1正，-1负。
 * validlen:数组中有效数字的个数。
 *
 * 函数功能：
 * 检查数字是否超过[?2^31,  2^31 ? 1]这个范围，超过取两侧极值。
 * 2147483647 , -2147483648
 *
 * 判断逻辑：
 * 如果validlen大于10，直接返回极值,注释此段，前面已有类似判断，排除此情况。
 * 如果validlen小于10，返回数字带上正负号。
 * 如果validlen等于10，从高位开始逐一判断。
*/
int CheckNumValid(int *arr,int character,int validlen)
{
    int IntArr2Int(int *arr,int character,int validlen);
    int JudgeNumValid(int *arr,int character,int validlen);
    /*
    if(validlen > 10 && character == 1)
    {
        return 2147483647;
    }
    else if(validlen > 10 && character == -1)
    {
        return -2147483648;
    }
    */
    if(validlen < 10 && character == -1)
    {
        return IntArr2Int(arr,character,validlen) * character;
    }
    else if(validlen < 10 && character == 1)
    {
        return IntArr2Int(arr,character,validlen) * character;
    }
    else if(validlen == 10)
    {
        return JudgeNumValid(arr,character,validlen);
    }
    return -1;
}

/**
 * 函数功能：
 * 数组有效数字长度为10时，检查其是否超过Int的范围。
*/
int JudgeNumValid(int *arr,int character,int validlen)
{
    int i;
    int res = 0;
    int flg = 1;
    int tmpArr[] = {2,1,4,7,4,8,3,6,4};
    for(i=0; i<validlen-1; i++)
    {
        if(arr[i] > tmpArr[i] && character == 1 && flg)
        {
            return 2147483647;
        } 
        else if(arr[i] > tmpArr[i] && character == -1 && flg)
        {
            return -2147483648;
        }
        else if(arr[i] == tmpArr[i] && character == 1)
        {   
            res = res + arr[i] * pow(10,validlen-1-i);
        }
        else if(arr[i] == tmpArr[i] && character == -1)
        {   
            res = res + arr[i] * pow(10,validlen-1-i) * (-1);
        }
        else if(character == 1)
        {
            res = res + arr[i] * pow(10,validlen-1-i);
            flg = 0;
        }
        else if(character == -1)
        {   
            res = res + arr[i] * pow(10,validlen-1-i) * (-1);
            flg = 0;
        }
        printf("arr[%d] : %d, tmpArr[%d] : %d, res : %d\n",i,arr[i],i,tmpArr[i],res);
    }
    if(character == 1 && arr[i] > 7 && flg)
    {
        return 2147483647;
    }
    else if(character == -1 && arr[i] > 8 && flg)
    {
        return -2147483648;
    }
    else if(character == 1)
    {
        res = res + arr[i];
    }
    else if(character == -1)
    {
        res = res + arr[i] * (-1);
    }
    return res;
}

/**
 * 函数功能：
 * 将数组中的数字拼接成一个整形数字。
*/
int IntArr2Int(int *arr,int character,int validlen)
{
    int i;
    int tmp = validlen - 1;
    int res = 0;
    for(i=0; i<validlen; i++)
    {
        res = res + arr[i] * pow(10,tmp);
        tmp--;
    }
    return res;
}

//各位字符数字转整形数字
int CharNum2IntNum(char c)
{
    switch(c)
    {
        case '0' : return 0;
        case '1' : return 1;
        case '2' : return 2;
        case '3' : return 3;
        case '4' : return 4;
        case '5' : return 5;
        case '6' : return 6;
        case '7' : return 7;
        case '8' : return 8;
        case '9' : return 9;
    }
    return -1;
}

void PrintfArr(void *arr, int size ,int elementsize)
{
    if(elementsize == sizeof(int))
    {
        int *tmparr = (int*)arr;
        int i;
        for(i=0; i<size; i++)
        {
            printf("%d ",tmparr[i]);
        }
    }
    else if(elementsize == sizeof(char))
    {
        char *tmparr = (char*)arr;
        int i;
        for(i=0; i<size; i++)
        {
            printf("%c ",tmparr[i]);
        }
    }
    printf("\n========================\n");
}

四、虚机测试截图

五、leecode提交代码

int myAtoi(char * s)
{
    int StrLens = strlen(s);
    if(StrLens == 0)
    {
        return 0;
    }
    else if(StrLens == 1)
    {
        if(s[0] < '0' || s[0] > '9')
        {
            return 0;
        }
    }
    int CharNum2IntNum(char c);
    void PrintfArr(void *arr, int size ,int elementsize);
    int CheckNumValid(int *arr,int character,int validlen);

    int i;
    int res = 0;
    int ArrSize = 20;
    int ValidArrLen = 0;
    int character;//1 : + , -1 : -
    int *IntArr = malloc(sizeof(int) * ArrSize);

    for(i=0; i<ArrSize; i++)
    {
        IntArr[i] = -1;
    }

    //作用：取数字前的正负号
    //第零位是数字为正号
    //零之后的索引位，判断前一位是正还是负
    //上述情况都不符合为正

    for(i=0; (s[i]<'0' || s[i]>'9') && i < StrLens; i++)
    {
    }

    //判断0-9数字之前的字符是否合规    
    for(int j=i-1; j>=0; j--)
    {
        if(j <= i-2 && (s[j] == '+' || s[j] == '-' ||  s[j] == '0'))
        {
            return 0;
        }
        else if(s[j] >= 'a' && s[j] <= 'z' || s[j] == '.')
        {
            return 0;
        }
    }

    if(i == 0)
    {
        character = 1;
    }
    else if(s[i-1] == '+')
    {
        character = 1;
    }
    else if(s[i-1] == '-')
    {
        character = -1;
    }
    else
    {
        character = 1;
    }

    for(; (s[i]<'1' || s[i]>'9') && i < StrLens; i++)
    {
        if(s[i] != '0')
        {
            return 0;
        }
    }
    //printf("s[%d] : %c\n",i,s[i]);

    //将字符数字转换成整形数字
    for(;s[i]>='0' && s[i]<='9'; i++)
    {
        IntArr[ValidArrLen] = CharNum2IntNum(s[i]);;
        ValidArrLen++;
        if(ValidArrLen > 10 && character == 1)
        {
            return 2147483647;
        }
        else if(ValidArrLen > 10 && character == -1)
        {
            return -2147483648;
        }        
    }
    //printf("ValidArrLen : %d\n",ValidArrLen);
    //PrintfArr(IntArr,ArrSize,sizeof(int));
    return CheckNumValid(IntArr,character,ValidArrLen);;
}

/**
 * 参数介绍：
 * arr:数组。
 * chararcter:正负号，1正，-1负。
 * validlen:数组中有效数字的个数。
 *
 * 函数功能：
 * 检查数字是否超过[?2^31,  2^31 ? 1]这个范围，超过取两侧极值。
 * 2147483647 , -2147483648
 *
 * 判断逻辑：
 * 如果validlen大于10，直接返回极值,注释此段，前面已有类似判断，排除此情况。
 * 如果validlen小于10，返回数字带上正负号。
 * 如果validlen等于10，从高位开始逐一判断。
*/
int CheckNumValid(int *arr,int character,int validlen)
{
    int IntArr2Int(int *arr,int character,int validlen);
    int JudgeNumValid(int *arr,int character,int validlen);
    if(validlen < 10 && character == -1)
    {
        return IntArr2Int(arr,character,validlen) * character;
    }
    else if(validlen < 10 && character == 1)
    {
        return IntArr2Int(arr,character,validlen) * character;
    }
    else if(validlen == 10)
    {
        return JudgeNumValid(arr,character,validlen);
    }
    return -1;
}

/**
 * 函数功能：
 * 数组有效数字长度为10时，检查其是否超过Int的范围。
*/
int JudgeNumValid(int *arr,int character,int validlen)
{
    int i;
    int res = 0;
    int flg = 1;
    int tmpArr[] = {2,1,4,7,4,8,3,6,4};
    for(i=0; i<validlen-1; i++)
    {
        if(arr[i] > tmpArr[i] && character == 1 && flg)
        {
            return 2147483647;
        } 
        else if(arr[i] > tmpArr[i] && character == -1 && flg)
        {
            return -2147483648;
        }
        else if(arr[i] == tmpArr[i] && character == 1)
        {   
            res = res + arr[i] * pow(10,validlen-1-i);
        }
        else if(arr[i] == tmpArr[i] && character == -1)
        {   
            res = res + arr[i] * pow(10,validlen-1-i) * (-1);
        }
        else if(character == 1)
        {
            res = res + arr[i] * pow(10,validlen-1-i);
            flg = 0;
        }
        else if(character == -1)
        {   
            res = res + arr[i] * pow(10,validlen-1-i) * (-1);
            flg = 0;
        }
        //printf("arr[%d] : %d, tmpArr[%d] : %d, res : %d\n",i,arr[i],i,tmpArr[i],res);
    }
    if(character == 1 && arr[i] > 7 && flg)
    {
        return 2147483647;
    }
    else if(character == -1 && arr[i] > 8 && flg)
    {
        return -2147483648;
    }
    else if(character == 1)
    {
        res = res + arr[i];
    }
    else if(character == -1)
    {
        res = res + arr[i] * (-1);
    }
    return res;
}

/**
 * 函数功能：
 * 将数组中的数字拼接成一个整形数字。
*/
int IntArr2Int(int *arr,int character,int validlen)
{
    int i;
    int tmp = validlen - 1;
    int res = 0;
    for(i=0; i<validlen; i++)
    {
        res = res + arr[i] * pow(10,tmp);
        tmp--;
    }
    return res;
}

//各位字符数字转整形数字
int CharNum2IntNum(char c)
{
    switch(c)
    {
        case '0' : return 0;
        case '1' : return 1;
        case '2' : return 2;
        case '3' : return 3;
        case '4' : return 4;
        case '5' : return 5;
        case '6' : return 6;
        case '7' : return 7;
        case '8' : return 8;
        case '9' : return 9;
    }
    return -1;
}

六、leecode代码提交截图