1. 题目描述

Implement atoi which converts a string to an integer.

The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.

The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.

If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.

If no valid conversion could be performed, a zero value is returned.

Note:

• Only the space character' 'is considered as whitespace character.
• Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231, 231 − 1]. If the numerical value is out of the range of representable values, INT_MAX (231 − 1) or INT_MIN (−231) is returned.

Example 1:

Input: "42"
Output: 42

Example 2:

Input: "   -42"
Output: -42
Explanation: The first non-whitespace character is '-', which is the minus sign.
             Then take as many numerical digits as possible, which gets 42.

Example 3:

Input: "4193 with words"
Output: 4193
Explanation: Conversion stops at digit '3' as the next character is not a numerical digit.

Example 4:

Input: "words and 987"
Output: 0
Explanation: The first non-whitespace character is 'w', which is not a numerical 
             digit or a +/- sign. Therefore no valid conversion could be performed.

Example 5:

Input: "-91283472332"
Output: -2147483648
Explanation: The number "-91283472332" is out of the range of a 32-bit signed integer.
             Thefore INT_MIN (−231) is returned.

2. 分析

在String topic下找题的时候无意间看到这个通过率格外低的题，这道题的通过率只有14.5%，而且我后来发现这是Leetcode下1000道题里第二低的题，第一道题的通过率只有13.9%，haha

这道题其实不考什么特别的算法或者什么思想，只要逻辑清晰一些，再根据题目的条件尽可能地把所有可能的情况都考虑到就可以AC了。

题目是字符串转成对应的数字，但字符串当然不可能是纯数字，当然会有些干扰字符，所以在下手之前先把所有题目中给出的信息罗列出来：

• 字符串开始如果有空格，那么忽略第一个非空格字符之前的所有空格
• 忽略掉开始的空格之后，如果第一个字符不是正负号或者数字，那么说明这个字符串不合法，直接返回0
• 忽略掉开始的空格后，第一个字符只能是正负号或者数字，正负号和后面紧跟的数字串构成一个合法的数据
• 数字串后面紧跟的任何字符都直接忽略
• 我们只能处理4字节的unsigned int数据，如果字符串表示的数据不在这个范围内，那么大于unsigned int最大值的数据返回unsigned int最大值，小于unsigned int最小值的数据返回unsigned int最小值
• 除了越界以外，所有不合法的字符串都返回0

其实只要清晰的把约束条件罗列出来，那么解题过程也就轻而易举了。现在剩下来的唯一一个需要讨论的地方是字符串转int，并且在转换过程中要判断是否越界。

我采取的方法是把字符串从前往后一位一位的处理，我们知道这样处理的话，每读进一位数字，就把之前的数据乘10再加上这一位数据。举个例子"123"，先处理第一位得1，再将1乘10加2得12，再将12乘10加3得123。

然后就是处理越界的问题，已知INT_MAX=2147483647，INT_MIN=-2147483648，那么可以这么想，如果按照上面的方法处理字符串，对于正数来说，如果之前得到的数据是214748364，那么如果有下一位且下一位大于7那么就越界，如果之前得到的数据大于214748364且还有下一位那么也一定越界。对于负数来说同理，如果之前得到的数据等于-214748364且下一位大于8就越界，如果之前得到的数据小于-214748364且还有下一位那么就越界。以这个思想写一个函数 isOutOfRange() ，在处理字符串的时候判断一下就ok了。

3. 代码

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

// 判断是否越界
// INT_MAX = 2147483647
// INT_MIN = -2147483648
// 当正数时，当srcNum = 214748364且addNum > 7，或者srcNum > 214748364时越界
// 当负数时，当srcNum = -214748364且addNum > 8，或者srcNum < -214748364时越界
int isOutOfRange(int sign, int srcNum, int addNum) {
    if (sign == 1) {
        if ((srcNum == 214748364) && (addNum > 7))
            return 1;
        else if (srcNum > 214748364)
            return 1;
    }
    else {
        if ((srcNum == -214748364) && (addNum > 8))
            return 1;
        else if (srcNum < -214748364)
            return 1;
    }
    return 0;
}

int myAtoi(char* str) {
    char* ptr = str;
    int sign = 1;  // 默认如果没有符号则是正数
    int srcNum = 0, addNum = 0;

    printf("Original str:%s\n", ptr);

    // 1. 去空格
    while (*ptr == ' ')
        ptr++;
    if (*ptr == '\0')
        return 0;
    printf("After step one:%s\n", ptr);

    // 2. 如果第一个非空格字符不是正负号或者数字
    if ((*ptr != '+') && (*ptr != '-')) {
        if ((*ptr > '9') || (*ptr < '0')) {
            return 0;
        }
    }
    printf("After step two:%s\n", ptr);

    // 3. 解析这个数字，先判断有没有正负号
    if ((*ptr == '+') || (*ptr == '-'))
        sign = (*ptr++ == '+') ? 1 : -1;

    // 4. 解析数字剩余的部分
    while ((*ptr >= '0') && (*ptr <= '9')) {
        addNum = *ptr - '0';
        printf("sign = %d srcNum = %d addNum = %d\n", sign, srcNum, addNum);
        if (isOutOfRange(sign, srcNum, addNum)) {
            return (sign == 1) ? INT_MAX : INT_MIN;
        }
        else {
            if (sign == 1) {
                srcNum = srcNum * 10 + addNum;
            }
            else {
                srcNum = srcNum * 10 - addNum;
            }
            ptr++;
        }
    }
    return  srcNum;
}

int main() {
    char str[] = "   -91283472332";
    printf("%d\n", myAtoi(str));

    system("pause");
    return 0;
}