8. String to Integer (atoi)
   Implement atoi to convert a string to an integer.
   Hint: Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input cases.
   Notes: It is intended for this problem to be specified vaguely (ie, no given input specs). You are responsible to gather all the input requirements up front.

Solution1：按位转换加权累加，并注意invalid case和溢出

思路：
(1) check non-empty, spaces, signs
(2) for every valid digits from most significant digit to least significant digit:
a. check if next step(3)会乘爆或加爆, if so, sign==+? return MAX_VALUE: MIN_VALUE
b. total = total * 10 + digit;
(3) return sign * total;

Time Complexity: O(str.length())
Space Complexity: O(1)

Solution2: Round1 套路判断overflow

见：http://www.jianshu.com/p/07f7e7a2dd3d

Solution1：

public class Solution {
    public int myAtoi(String str) {

        // 1. ckeck Empty string
        if (str.isEmpty()) return 0;

        // 2. Remove Spaces
        int start = 0;
        while (str.charAt(start) == ' ' && start < str.length()) start++;

        // 3. Handle signs
        int sign = 1; // +1, -1
        if (str.charAt(start) == '-' || str.charAt(start) == '+') {
            sign = str.charAt(start) == '+' ? 1 : -1;
            start++;
        }
        
        // main method
        int total = 0;
        for (int i = start; i < str.length() && str.charAt(i) >= '0' && str.charAt(i) <= '9'; i++) {
            int digit = str.charAt(i) - '0';

            // check if the total will be overflow for next step to exe result = result * 10 + digit;
            if (total > Integer.MAX_VALUE / 10 || (total == Integer.MAX_VALUE / 10 && digit > Integer.MAX_VALUE % 10))
                return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;

            total = total * 10 + digit;
        }
        return sign * total;
    }
}

Solution2：

class Solution {
    public int myAtoi(String str) {
        if(str.isEmpty() || str.length() == 0) return 0;
        
        // delete space
        int start = 0;
        while(start < str.length() && str.charAt(start) == ' ') start++;
        
        // handle sign
        int sign = 1;
        if(start < str.length() && (str.charAt(start) == '+' || str.charAt(start) == '-')){
            if(str.charAt(start) == '-') {
                sign = -1;
            }
            start++;
        }
        
        int result = 0;
        for(int i = start; i < str.length(); i++) {
            int digit = str.charAt(i) - '0';
            if(digit > 9 || digit < 0) break;

            if(sign > 0 && result > (Integer.MAX_VALUE - digit) / 10) {
                return Integer.MAX_VALUE; 
            }
            else if(sign < 0 && -1 * result < (Integer.MIN_VALUE + digit) / 10) {
                return Integer.MIN_VALUE;
            }
            
            result = result * 10 + digit;
        }
        
        return sign * result;
        
    }
}