String to Integer

Question

  1. Implement function atoi to convert a string to an integer.
  3. If no valid conversion could be performed, a zero value is returned.
  5. If the correct value is out of the range of representable values,
  6. INT_MAX (2147483647) or INT_MIN (-2147483648) is returned.
  8. Example
  9. "10" => 10
  11. "-1" => -1
  13. "123123123123123" => 2147483647
  15. "1.0" => 1

題解

經典的字符串轉整數題，邊界條件比較多，比如是否需要考慮小數點，空白及非法字符的處理，正負號的處理，科學計數法等。最先處理的是空白字符，然後是正負號，接下來只要出現非法字符(包含正負號，小數點等，無需對這兩類單獨處理)即退出，否則按照正負號的整數進位加法處理。

Java

  1. public class Solution {
  2.     /**
  3.      * @param str: A string
  4.      * @return An integer
  5.      */
  6.     public int atoi(String str) {
  7.         if (str == null || str.length() == 0) return 0;
  9.         // trim left and right spaces
  10.         String strTrim = str.trim();
  11.         int len = strTrim.length();
  12.         // sign symbol for positive and negative
  13.         int sign = 1;
  14.         // index for iteration
  15.         int i = 0;
  16.         if (strTrim.charAt(i) == '+') {
  17.             i++;
  18.         } else if (strTrim.charAt(i) == '-') {
  19.             sign = -1;
  20.             i++;
  21.         }
  23.         // store the result as long to avoid overflow
  24.         long result = 0;
  25.         while (i < len) {
  26.             if (strTrim.charAt(i) < '0' || strTrim.charAt(i) > '9') {
  27.                 break;
  28.             }
  29.             result = 10 * result + sign * (strTrim.charAt(i) - '0');
  30.             // overflow
  31.             if (result > Integer.MAX_VALUE) {
  32.                 return Integer.MAX_VALUE;
  33.             } else if (result < Integer.MIN_VALUE) {
  34.                 return Integer.MIN_VALUE;
  35.             }
  36.             i++;
  37.         }
  39.         return (int)result;
  40.     }
  41. }

源碼分析

符號位使用整數型表示，便於後期相乘相加。在 while 循環中需要注意判斷是否已經溢位，如果放在 while 循環外面則有可能超過 long 型範圍。

C++

  1. class Solution {
  2. public:
  3.     bool overflow(string str, string help){
  4.         if(str.size() > help.size()) return true;
  5.         else if(str.size() < help.size()) return false;
  6.         for(int i = 0; i < str.size(); i++){
  7.             if(str[i] > help[i]) return true;
  8.             else if(str[i] < help[i]) return false;
  9.         }
  10.         return false;
  11.     }
  12.     int myAtoi(string str) {
  13.         // ans: number, sign: +1 or -1
  14.         int ans = 0;
  15.         int sign = 1;
  16.         int i = 0;
  17.         int N = str.size();
  19.         // eliminate spaces
  20.         while(i < N){
  21.             if(isspace(str[i]))
  22.                 i++;
  23.             else
  24.                 break;
  25.         }
  27.         // if the whole string contains only spaces, return
  28.         if(i == N) return ans;
  31.         if(str[i] == '+') 
  32.             i++;
  33.         else if(str[i] == '-'){
  34.             sign = -1;
  35.             i++;
  36.         }
  38.         // "help" gets the string of valid numbers
  39.         string help;
  40.         while(i < N){
  41.             if('0' <= str[i] and str[i] <= '9')
  42.                 help += str[i++];
  43.             else
  44.                 break;
  45.         }
  47.         const string maxINT = "2147483647";
  48.         const string minINT = "2147483648";
  50.         // test whether overflow, test only number parts with both signs
  52.         if(sign == 1){
  53.             if(overflow(help, maxINT)) return INT_MAX;
  54.         }
  55.         else{
  56.             if(overflow(help, minINT)) return INT_MIN;
  57.         }
  59.         for(int j=0; j<help.size(); j++){
  60.             ans = 10 * ans + int(help[j] - '0');
  61.         }
  63.         return ans*sign;
  64.     }
  65. };

源碼分析

C++解法並沒有假設任何內建的string演算法，因此也適合使用在純C語言的字元陣列上，此外溢位的判斷直接使用字串用一個輔助函數比大小，這樣如果面試官要求改成string to long 也有辦法應付，不過此方法會變成machine-dependent，嚴格來說還需要寫一個輔助小函數把INT_MAX和INT_MIN轉換成字串來使用，這邊就先省略了，有興趣的同學可以自己嘗試練習。

複雜度分析

略

Reference