leetcode-8. String to integer (ATOI)

JAVA solution

class Solution {
    public int myAtoi(String s) {
        //  Convert the string passed in to a character array 
        char[] chars = s.toCharArray();
        //  Gets the length of the character array 
        int n = chars.length;
        //  Define the starting position of the global index 
        int idx = 0;
        while (idx < n && chars[idx] == ' ') {
            //  Remove space 
            idx++;
        }
        if (idx == n) {
            // After removing all spaces, stop the program if it reaches the end 
            return 0;
        }
        //  Whether the tag is negative 
        boolean negative = false;
        if (chars[idx] == '-') {
            // Negative sign encountered , Is marked as negative 
            negative = true;
            //  Go on to the next 
            idx++;
        } else if (chars[idx] == '+') {
            //  Encounter a plus sign , Then go straight to the next 
            idx++;
        } else if (!Character.isDigit(chars[idx])) {
            //  If the first one encounters other characters that are not numbers or signs, stop the program 
            return 0;
        }
        //  Define a variable that stores the final result 
        int ans = 0;
        //  When the array subscript does not exceed the bounds and the characters are numbers, the traversal is performed 
        while (idx < n && Character.isDigit(chars[idx])) {
            //  Due to character  '0'  To  '9'  Of  ASCII  Value is continuous , By character  ASCII  Value difference can be cleverly converted to the integer value corresponding to the character 
            int digit = chars[idx] - '0';
            //  Every cycle should prevent overflow caused by too large value , To judge  ans * 10 + digit  Is it greater than  Integer.MAX_VALUE, But directly  ans * 10 + digit  May overflow here directly , So in order to avoid overflow during operation , Shift the equation , Change multiplication into division 
            if (ans > (Integer.MAX_VALUE - digit) / 10) {
                //  If it is judged that the number is negative , return  Integer.MIN_VALUE, If it is positive, it returns ,Integer.MAX_VALUE
                return negative? Integer.MIN_VALUE : Integer.MAX_VALUE;
            }
            //  Because traversal is from left to right , So just use it every time  ans  multiply  10  Add the current value to restore the value corresponding to the number 
            ans = ans * 10 + digit;
            //  next 
            idx++;
        }
        //  Return the final result , If it is regular, it returns a positive number , If it is negative, it returns a negative number 
        return negative? -ans : ans;
    }
}

Copy

Problem analysis

   According to the requirements of the topic , This problem is to extract the number in the string passed in and convert it into its corresponding value , The title tells you that the target number may have positive and negative signs , And there are spaces and other non numeric characters in the string .

   First, we split the incoming string into characters one by one and store them in the character array , And record the array length , Define the starting position of the global index as 0, Then we use while Loop to remove all leading spaces （ skip ）, Determine the position of the global index after removing spaces , If the position of the global index comes to the end of the string , It means that the string is pure space , Terminate program execution .

   If the position of the global index is less than the end position of the string, it will be executed downward , First define a Boolean value to mark whether the target number is negative , The default is false, Is a negative number true Otherwise false. here , Intercept the character of the current global index to determine whether it is a negative sign 、 Plus sign or other non numeric characters , If it is a minus sign , Set the Boolean value to true, And move the global index to the next character position , If it is a positive sign , Then go directly to the next position （ Unsigned defaults to positive ）, Assuming other non numeric characters, the program will be terminated directly .

   First define a variable to store the final result , If the character after the sign bit is a numeric character （ Or the first character is not a sign bit and is a numeric character ）, Then enter the cycle , Within the bounds of the array length , Put all the resulting numeric characters （‘0’-‘9’） Respectively with character 0 namely ‘0’ Make a difference , Due to character '0' To '9' Of ASCII Value is continuous , By character ASCII Value difference can be cleverly converted to the integer value corresponding to the character , Every cycle should prevent overflow caused by too large value , To judge ans * 10 + digit Is it greater than Integer.MAX_VALUE, But directly ans * 10 + digit May overflow here directly , So in order to avoid overflow during operation , Shift the equation , Change multiplication into division .

   If it is greater than the integer maximum value, the integer maximum value or the integer minimum value will be returned according to the positive and negative of the number , If the operation does not exceed the maximum value of an integer , Then continue to accumulate the final result , Because traversal is from left to right , So just use it every time ans multiply 10 Add the current value to restore the value corresponding to the number , Continue to move the global index until it is equal to the length of the array, and jump out of the loop , Return the final result according to the positive or negative of the target number .

leetcode The original title is ：8. String conversion integers (atoi)