Java Solution with 4 steps explanations


  • 120
    L
    public int myAtoi(String str) {
        int index = 0, sign = 1, total = 0;
        //1. Empty string
        if(str.length() == 0) return 0;
    
        //2. Remove Spaces
        while(str.charAt(index) == ' ' && index < str.length())
            index ++;
    
        //3. Handle signs
        if(str.charAt(index) == '+' || str.charAt(index) == '-'){
            sign = str.charAt(index) == '+' ? 1 : -1;
            index ++;
        }
        
        //4. Convert number and avoid overflow
        while(index < str.length()){
            int digit = str.charAt(index) - '0';
            if(digit < 0 || digit > 9) break;
    
            //check if total will be overflow after 10 times and add digit
            if(Integer.MAX_VALUE/10 < total || Integer.MAX_VALUE/10 == total && Integer.MAX_VALUE %10 < digit)
                return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
    
            total = 10 * total + digit;
            index ++;
        }
        return total * sign;
    }

  • 0
    V

    Thanks, this is very helpful


  • 7
    C

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

    can be replaced by str = str.trim();


  • 1
    C

    there is a bug try str = " "


  • 0
    L

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


  • 34

    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;
    }

  • 0
    N

    thanks, very explainable


  • -3
    S
    This post is deleted!

  • 1

    For the overflow checking, I think you could use "if((Integer.MAX_VALUE-digit)/10 < total)", which is more straight forward.


  • 0
    L

    To add in to xietao, the opposite condition if((Integer.MIN_VALUE+digit)/10 > total), i spent half an hour figuring out why my code didn't work, turns out I did MIN_VAL - digit, which underflowed to max value.


  • 0
    M

    No,it can!!! ( Integer.MAX_VALUE %10 < digit ) equals (digit > 7)


  • 2
    A

    if we replace this
    if(Integer.MAX_VALUE/10 < total || Integer.MAX_VALUE/10 == total && Integer.MAX_VALUE %10 < digit) with this statement if(Integer.MAX_VALUE/10 <= total && Integer.MAX_VALUE %10 < digit)..the result differs for the input " -11919730356x".. what is the difference between these two statements?


  • 0
    Z

    there is a little problem here if str=a6 or other num+alphabet,this solution can not work exactly ,so i suggest in step3 ,we can change
    while(i < len && str.charAt(i) >= '0' && str.charAt(i) <= '9'){
    int digit = str.charAt(i++) - '0';
    ...}

    to

    while(i < len){
    if (str.charAt(i) >= '0' && str.charAt(i) <= '9')
    {int digit = str.charAt(i++) - '0';
    ...}else{
    i++;}
    }
    this can effectively avoid such bug

    sorry for my bad english !
    thank you


  • 0
    Y

    @charliema I believe if you do so the interviewer would ask you to implement a trim() function.


  • 0
    S

    int digit = str.charAt(index) - '0'; //what does this sentence mean? str.charAt(index)means getting an char at the index, so why need to-'0' ? What does "-'0'"mean? If the char at index is '9', then what is the result after -'0'? And if the char at index is '0', then what is the result after -'0'?

    Thank you!


  • 0
    Z

    @yavinci i think something is wrong if you input -13&4,the result is -13,but if you change to,that will be correct and the new leetcode i think is hard to use
    while(i < len) {
    int digit = str.charAt(i++) - '0';
    if(digit <= 0 || digit >= 9) continue;
    boolean overlow = (num == bound && digit >= 8) || num > bound;
    if(overlow) return sign > 0 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
    num = num * 10 + digit;
    }


  • 0
    Y

    @stephenxie this step gives the difference of the ASCII value of char At index and '0'. Since you need a int value digit, this difference is what you want. Just use your example, '9' - '0' = 9, so you get the int digit of this index.


  • 0
    R

    what if str is null?


  • 0
    S

    @YaokaiYang I got it! Thank you for your responce!


  • 0
    S

    @redmonpie str=null means no str exists!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.