8. String to Integer (atoi)

1.問題

2.想法

• 提問

  • 是不是只會輸出一個數字-> 不須轉換每個substring

  • 正負號

• function header, parameter

• test input

  • 空白 + 數字

  • integer overflow

• 說明想法

  • invalidate的情形:

    • 字串 + 數字

    • 兩個正負號 + 數字

  • 忽略空白, 遇到正負號讀取後index + 1

  • 處理overflow

    • 加之前與加之後必須數值相同

backup = sum;
sum = sum * 10 + ans;
            
if (sum < 0 || backup != (sum - ans) / 10) {
   return sign > 0 ? INT_MAX : INT_MIN;
}

• 測試

• 計算複雜度: O(n)?

3.程式碼

class Solution {
public:
    int myAtoi(string str) {
        if (str.empty()) {
            return 0;
        }
        int size = str.length(), i = 0, sign = 1, sum = 0, backup = 0;
        
        //如果碰到空白就往後移
        while (i < size && str[i] == ' ') {
            i++;
        }
        
        //判斷符號
        if (str[i] == '+') {
            sign = 1;
            i++;
        } else if (str[i] == '-') {
            sign = -1;
            i++;
        }
        
        while (i < size && isdigit(str[i])) {
           
            int ans = int(str[i] - '0');
            backup = sum;
            sum = sum * 10 + ans;
            
            if (sum < 0 || backup != (sum - ans) / 10) {
                return sign > 0 ? INT_MAX : INT_MIN;
            }
            i++;
        }
        
        
        return sum * sign;
    }
};