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

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

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 整數，但缺點是效能上會大打折扣。

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

//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; }