StringToIntegerAtoi [source code]

public class StringToIntegerAtoi {
static
/******************************************************************************/
class Solution {
    public int myAtoi(String str) {
        String[] tokens = str.split ("\\s+");
        String num_str = tokens[0];
        if (num_str.length () == 0) {
            if (tokens.length < 2)
                return 0;
            num_str = tokens[1];
        }
        char[] digits = num_str.toCharArray ();
        boolean neg = digits[0] == '-';
        int pos = (digits[0] == '-' || digits[0] == '+' ? 1 : 0);
        long res = 0;
        while (pos < digits.length) {
            if (!Character.isDigit (digits[pos]))
                break;
            res *= 10;
            res += Character.digit (digits[pos], 10);
            if (res > Integer.MAX_VALUE)
                break;
            pos++;
        }
        res *= neg ? -1 : 1;
        if (res > Integer.MAX_VALUE)
            return Integer.MAX_VALUE;
        if (res < Integer.MIN_VALUE)
            return Integer.MIN_VALUE;
        return (int) res;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        StringToIntegerAtoi.Solution tester = new StringToIntegerAtoi.Solution();
        String[] inputs = {
            "    +123a2", "123",
            "2147483648", "2147483647",
            "9223372036854775809", "2147483647",
        };
        for (int i = 0; i < inputs.length / 2; i++) {
            String str = inputs[2 * i];
            int ans = Integer.parseInt (inputs[2 * i + 1]);
            System.out.println (Printer.separator ());
            int output = tester.myAtoi (str);
            System.out.printf ("[%s] -> %s, expected: %d\n", 
                str, Printer.wrapColor (output + "", output == ans ? "green" : "red"), ans
            );
        }
    }
}

这题好像难点就是自己找到实际的转换规则, 但是看了提示之后知道转换规则之后, 就不是很难了; 不过这个题目被downvote的很严重, 可能就是大部分人跟我一样, 这种什么都没有说清楚的题目做起来很烦人;

果然是很多corner case, 不过最后好歹是按时完成了, 最后的速度是73ms (4%), 不知道哪里出了问题? 感觉其实没有多少特别expensive的操作;

另外, 既然又用到了split, 正好顺带复习一下, split的一些Corner Case:

java> "  1".split ("\\s+")  
java.lang.String[] res0 = ["", "1"]  
java> "1".split ("\\s+")  
java.lang.String[] res1 = ["1"]  
java> "".split ("\\s+")  
java.lang.String[] res4 = [""]  
java> "1".split ("")  
java.lang.String[] res2 = ["1"]  
java> "  1".split ("")  
java.lang.String[] res3 = [" ", " ", "1"]

几个注意的地方: 首先, split的结果array长度至少是1; 其次, 始终理解这种regex的东西, 操作的基本单位是letter, 也就是char; 而split的作用, 可以这样简单粗暴的记忆: 就是把所有符合regex的char, 都transduce成"", 也就是Null; 然后加一个poster filtering: Null之间可以合并, 成为一个null, 也就是token之间的隔断, 然后non-null的char之间也可以合并, 成为一个token; 用这个准则来记忆上面这些Corner Case, 应该能解释的通;

另外, 这题读题的时候, 有点偏差, 比如" +123a2"这个string, 我一开始认为应该判为不合法, 然后直接返回0; 但是试了一下, 好像他们认为你只要走到123结束就行了; 我一开始以为题目里面的additional characters after those that form the integral number指的是要和123之间有一个空格分割, 但是这里看来, 是没有这个分割的;

另外, 这题的超界处理, 也不是那么trivial; 一开始我以为, 直接把sum换成一个long应该就行了, 但是结果发现有case最后把long也break掉了; 解决的办法其实也很简单, 因为我们现在的sum是long, 所以可以放心的和integer的正负无穷进行比较. 所以直接一旦超了integer的界(而不是long的)就直接break掉, 这样就不用担心long超界了;

没有editorial;

@yuruofeifei said in My simple solution:

int atoi(const char *str) {  
    int sign = 1, base = 0, i = 0;  
    while (str[i] == ' ') { i++; }  
    if (str[i] == '-' || str[i] == '+') {  
        sign = 1 - 2 * (str[i++] == '-');   
    }  
    while (str[i] >= '0' && str[i] <= '9') {  
        if (base >  INT_MAX / 10 || (base == INT_MAX / 10 && str[i] - '0' > 7)) {  
            if (sign == 1) return INT_MAX;  
            else return INT_MIN;  
        }  
        base  = 10 * base + (str[i++] - '0');  
    }  
    return base * sign;  
}

反正最后的思路都是类似的, 不过这个方法有一点不一样, 他没有用long来处理出界; 而是直接用一个类似pre leaf的位置, 进行判断; 注意他这里不仅要判断高9位, 还可能要判断最低位跟7的关系; 我当时实际上是想到了这个方法, 不过感觉看起来有点恶心(过分依赖对于正无穷实际的value的knowledge), 所以没有用, 不过实际上看起来他这个代码实际上比我的要简练很多;

这个观点不错:

@monaziyi said in My simple solution:

I don't like the magic number '7' , it's better to substitute it to INT_MAX%10

当时也没想到, 你要强调的其实只是你知道MAX的个位是多少而已;

@yavinci said in Java Solution with 4 steps explanations:

I've refactored the above code to avoid several bugs: str1 = " + ", str2 = " " will throw index exception. We should always check i < len otherwise index may be out of range.

---

Overflow explanation: Integer.MAX_VALUE = 2147483647 and Integer.MIN_VALUE = -2147483648 is the largest/smallest value that an int primitive can contain.

Let's simplify this problem. Suppose str1 = " -a649b ", st2 = " a652b ", max = 647, min = -648. So if atoi(str) > 647 || atoi(str) < -648 atoi will overflow. In other words, when we've parsed num == 64 and the next char is also digit, max / min can directly be returned if the next digit >= 8; or we've parsed num > 64, directly return too.

---

    public int myAtoi(String str) {  
        int i = 0;  
        str = str.trim();          
        char[] c = str.toCharArray();  

        int sign = 1;  
        if (i < c.length && (c[i] == '-' || c[i] == '+')) {  
            if (c[i] == '-') {  
                sign = -1;  
            }  
            i++;  
        }        

        int num = 0;  
        int bound = Integer.MAX_VALUE / 10;  
        while (i < c.length && c[i] >= '0' && c[i] <= '9') {  
            int digit = c[i] - '0';  
            if (num > bound || (num == bound && digit > 7)) {  
                return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;  
            }  
            num = num * 10 + digit;  
            i++;  
        }  
        return sign * num;  
    }

写的相对简练, 不过没看出什么特别的地方;

submission基本是波动, 不过中位速度就是上面这种不依赖于long就可以判断超界的写法;

Problem Description

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.

Update (2015-02-10):
The signature of the C++ function had been updated. If you still see your function signature accepts a const char * argument, please click the reload button to reset your code definition.

spoilers alert... click to show requirements for atoi.

Requirements for atoi:
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. If the correct value is out of the range of representable values, INT_MAX (2147483647) or INT_MIN (-2147483648) is returned.

Difficulty:Medium
Total Accepted:208.8K
Total Submissions:1.5M
Contributor:LeetCode
Companies
microsoftamazonbloomberguber
Related Topics
mathstring
Similar Questions
Reverse IntegerValid Number