题目：

难度：中等

Implement atoi which converts a string to an integer.

The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.

The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.

If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.

If no valid conversion could be performed, a zero value is returned.

Note:

• Only the space character ' ' is considered as whitespace character.
• Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−2^31, 2^31 − 1]. If the numerical value is out of the range of representable values, INT_MAX (2^31 − 1) or INT_MIN (−2^31) is returned.

Example 1:

Input: "42"
Output: 42

Example 2:

Input: " -42"
Output: -42
Explanation: The first non-whitespace character is '-', which is the minus sign.
Then take as many numerical digits as possible, which gets 42.

Example 3:

Input: "4193 with words"
Output: 4193
Explanation: Conversion stops at digit '3' as the next character is not a numerical digit.

Example 4:

Input: "words and 987"
Output: 0
Explanation: The first non-whitespace character is 'w', which is not a numerical
digit or a +/- sign. Therefore no valid conversion could be performed.

Example 5:

Input: "-91283472332"
Output: -2147483648
Explanation: The number "-91283472332" is out of the range of a 32-bit signed integer.
Thefore INT_MIN (−2^31) is returned.

解释下题目，给定一串字符串，按一定的要求转换成一个整数。一定要把所有的要求都看清楚，不然test case 会有很多失败的情况。

1. 从第一个非空格的字符开始算起，也就是前面的空格要trim掉
2. 字符串可能含有任何字符，所以第一个非空字符可以是 +/- 或者数字，遇到其他的则停止
3. 没有有效的转换，要输出0
4. 数字如果不处于 [−2^31, 2^31 − 1] 之间，则要输出最大值或最小值，请参考例子5

个人感觉这道题的问题在于怎么样包含所有可能的情况，有几个重点的边缘测试一定要考虑，其他的问题应该不是太难

Java Solution 1：

本人的办法比较直接，没有过多考虑时间，只是把所有能想到的case都cover住了。

public int myAtoi(String str) {
            final char[] acceptedArray = new char[]{'1','2','3','4','5','6','7','8','9','0'};
            final char[] acceptedSignedArray = new char[]{'1','2','3','4','5','6','7','8','9','0','+','-'};
            final int INT_MIN = Integer.MIN_VALUE;
            final int INT_MAX = Integer.MAX_VALUE;

            int num = 0;
            StringBuilder sb = new StringBuilder();

            //trim white space from str
            String trimedString = str.trim();

            if (trimedString == null || trimedString.length() == 0)
                return 0;

            char[] charArray = trimedString.toCharArray();

            //Retrieve the first char with Sign +/-
            char first = charArray[0];

            for(int i=0; i<acceptedSignedArray.length; i++ ){
                if (first == acceptedSignedArray[i]){
                    sb.append(first);
                    break;
                }
            }

            if(sb.length() == 0)
                return 0;

            for(int i = 1; i< charArray.length; i++){
                boolean bFound = false;
                for(int j=0; j<acceptedArray.length; j++ ){
                    if (charArray[i] == acceptedArray[j]){
                        sb.append(charArray[i]);
                        bFound = true;
                        break;
                    }
                }

                if(bFound == false)
                    break;

            }

        String s = sb.toString();
        //Filter sign only string
        if (s.equals("+") || s.equals("-"))
            return 0;

        //Filter out of int range string
        try {
            num = Integer.valueOf(s);
        }catch(NumberFormatException ex){
            if (s.indexOf("-") >= 0)
                return INT_MIN;

            return INT_MAX;
        }

        return num;
    }

image.png

下面给出别人的解法

划重点：

1.通过运算来生成整数，我是用string转换
2.通过第一位是不是符号来决定是从 0， 还是1 开始循环，而我是单独把第一位取出来

3. 通过 1和-1来觉得 符号的正负，这个想法不错。
4. 判断数字，可以直接用 大小判断， chars[i] < '0' || chars[i] > '9'

public int myAtoi2(String str) {
        if (str == null) return 0;

        str = str.trim();
        if(str.length() == 0) return 0;

        char[] chars = str.toCharArray();

        // check if the 1st character is valid, i.e. must be a sign or a number
        if(chars[0] != '-' && chars[0] != '+' && chars[0] < '0' || chars[0] > '9') return 0;

        long sum = 0;
        int i = (chars[0] == '+' || chars[0] == '-') ? 1 : 0;
        int sign = chars[0] == '-' ? -1 : 1;
        for(; i < chars.length; i++){
            if(chars[i] < '0' || chars[i] > '9') break;
            else sum = sum * 10 + (chars[i] - '0');

            if(sum > Integer.MAX_VALUE && sign == 1)  return Integer.MAX_VALUE;
            if(sum > (long)Integer.MAX_VALUE + 1 && sign == -1) return Integer.MIN_VALUE;
        }

        return (int)sum * sign;

    }

image.png