LeetCode #8. String to Integer (atoi)　プログラミング練習

問題：

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 (−231) is returned.

難易度:　medium
入力:　String
目的: 入力された文字列を整数にして返せ
出力:　Int
注意:　ボーダーケースが非常に多い

一見簡単に見えますがボーダーケースが非常に多い為処理に困る問題です。
某有名外資企業日本支部の面接で出された事があると言う記事を見たことがあります。
面接でこう言った問題が出た場合、必ず面接官に入力可能ケースを聞き、ケース毎に対応して書いていきましょう。

注意すべき事:　

マイナスの数字が入力された場合

Integer の範囲が-2^31 ~ 2^31-1まで。オーバーフローに注意

" 321"　は　321

"3 21" はアウト

"文字列の中で"+", "-", " " 以外が入力されている場合はアウト

"++321"とかもあるので注意

int型でオーバーフローした場合はMAX_VALUEを返す

私も最初はすべてのケースを考える事が出来ず、試行錯誤で書いた結果なので少し汚いコードになってしまいました。
以下回答です。

class Solution {
    public int myAtoi(String str) {
        int len = str.length();
        int sign = 1;
        int result = 0;
        int i=0;
        if (len == 0) return 0;
        while(i<len && str.charAt(i) == ' ') i++;
        if (len <= i) return 0;
        if (str.charAt(i) == '+') {
            sign = 1;
            i++;
        }
        else if (str.charAt(i) == '-') {
            sign = -1;
            i++;
        }
        for(; i<len; i++) {
            if ( str.charAt(i) >= '0' && str.charAt(i) <= '9' ) {
                if (sign != -1) {
                    if (result > Integer.MAX_VALUE/10 || result == Integer.MAX_VALUE/10 && str.charAt(i) - '0' > 7) {
                        result = Integer.MAX_VALUE;
                        break;
                    }
                }
                else {
                    if (result > Integer.MAX_VALUE/10 || result == Integer.MAX_VALUE/10 && str.charAt(i) - '0' > 8) {
                        result = -Integer.MIN_VALUE;
                        break;
                    }
                }
            }
            if (str.charAt(i) >= '0' && str.charAt(i) <= '9') {
                result = result*10 + (int)str.charAt(i)-'0';
            }
            else break;
        }
        return result*sign;
    }
}

マイナスプラスは頭文字のみ、頭のスペースも可。オーバーフローに気を付ければ問題なく処理できます。
少しめんどくさい問題ですが、いかにも面接官が好きそうな、どこまで入力範囲を考え抜けるかが試される問題ですね。
Time ComplexityはO(n)です。

ではでは