LeetCode#8 String to Integer (atoi)

分析

原題連結

這題歷史悠久，早在 30 年前 K&R C 語言 習題裡就出現過了，但小弟 submit n 次才成功。因為這題有個陷阱是解題系統會傳入超過 INT_MAX(2147483647)，小於 INT_MIN(-2147483648) 的數值字串，系統希望「參數 > INT_MAX」 時傳回 INT_MAX，「參數 < INT_MIN」時傳回 INT_MIN，如果傻傻的照抄 K&C 習題解答，得到的是 overflow 的結果，當然就被 reject 了。

個人採用的策略很簡單，既然傳入的是 int，那我用 long long (64bits) 運算不就避開超過 INT_MAX 或小於 INT_MIN 時無法判別的情形了嗎？

Source Code

int myAtoi(char* str) {
    if(str == 0)
        return 0;

    while(*str == ' ')
        ++str;

    if(*str == 0)
        return 0;

    char prefix = 0;
    if(*str == '-' || *str == '+'){
        prefix = *str++;
    }

    long long result = 0;
    for(; *str != 0; ++str){
        if(*str >= '0' && *str <= '9'){
            result = result*10 + (*str - '0');
            if(prefix != '-'){
                if(result > 2147483647) return 2147483647;
            }else{
                if(result > 2147483648) return -2147483648;
            }
        }else{
            break;
        }
    }

    return (prefix == '-' ? -result : result);       
}

另外一種策略是每次運算前(上述程式 Line#19)，先判斷這次是不是會爆掉，這樣可以避免使用 64bits 整數，但缺點是效能上會大打折扣。

//https://github.com/soulmachine/leetcode
int myAtoi(const char *str) {
    int num = 0;
    int sign = 1;
    const int n = strlen(str);
    int i = 0;
    while (str[i] == ' ' && i < n) i++;
    if (str[i] == '+') {
        i++;
    } else if (str[i] == '-') {
        sign = -1;
        i++;
    }
    for (; i < n; i++) {
        if (str[i] < '0' || str[i] > '9')
            break;
        if (num > INT_MAX / 10 || (num == INT_MAX / 10 && (str[i] - '0') > INT_MAX % 10)) {
            return sign == -1 ? INT_MIN : INT_MAX;
    }
        num = num * 10 + str[i] - '0';
    }
    
    return num * sign;
}