35.8. string conversion integer (ATOI)

The first 20 God

8. String conversion integers (atoi)

Medium difficulty 1164 Switch to English to receive dynamic feedback

Please come to realize a myAtoi(string s) function , Enable it to convert a string to a 32 Bit signed integer （ similar C/C++ Medium atoi function ）.

function myAtoi(string s) The algorithm is as follows ：

• Read in strings and discard useless leading spaces
• Check the next character （ Suppose you haven't reached the end of the character yet ） Positive or negative , Read the character （ If there is ）. Determine whether the final result is negative or positive . If neither exists , Suppose the result is positive .
• Read in the next character , Until you reach the next non numeric character or the end of the input . The rest of the string will be ignored .
• Convert the numbers read in the previous steps into integers （ namely ,“123” -> 123, “0032” -> 32）. If you don't read in the numbers , Then the integer is 0 . Change the symbol if necessary （ From step 2 Start ）.
• If the number of integers exceeds 32 Bit signed integer range [−231, 231 − 1] , You need to truncate this integer , Keep it in this range . say concretely , Less than −231 The integer of should be fixed to −231 , Greater than 231 − 1 The integer of should be fixed to 231 − 1 .
• Returns an integer as the final result .

Be careful ：

• The white space character in this question only includes the space character ' ' .
• Except for the leading space or the rest of the string after the number , Do not ignore Any other character .

Example 1：

 Input ：s = "42"
 Output ：42
 explain ： The bold string is the character that has been read in , The caret is the character currently read .
 The first  1  Step ："42"（ No characters are currently read in , Because there are no leading spaces ）
         ^
 The first  2  Step ："42"（ No characters are currently read in , Because it doesn't exist here  '-'  perhaps  '+'）
         ^
 The first  3  Step ："42"（ Read in  "42"）
           ^
 Parse to get an integer  42 .
 because  "42"  In scope  [-231, 231 - 1]  Inside , The final result is  42 .

Example 2：

 Input ：s = "   -42"
 Output ：-42
 explain ：
 The first  1  Step ："   -42"（ Read in leading space , But ignore ）
            ^
 The first  2  Step ："   -42"（ Read in  '-'  character , So the result should be negative ）
             ^
 The first  3  Step ："   -42"（ Read in  "42"）
               ^
 Parse to get an integer  -42 .
 because  "-42"  In scope  [-231, 231 - 1]  Inside , The final result is  -42 .

Example 3：

 Input ：s = "4193 with words"
 Output ：4193
 explain ：
 The first  1  Step ："4193 with words"（ No characters are currently read in , Because there are no leading spaces ）
         ^
 The first  2  Step ："4193 with words"（ No characters are currently read in , Because it doesn't exist here  '-'  perhaps  '+'）
         ^
 The first  3  Step ："4193 with words"（ Read in  "4193"; Because the next character is not a number , So read in stop ）
             ^
 Parse to get an integer  4193 .
 because  "4193"  In scope  [-231, 231 - 1]  Inside , The final result is  4193 .

Example 4：

 Input ：s = "words and 987"
 Output ：0
 explain ：
 The first  1  Step ："words and 987"（ No characters are currently read in , Because there are no leading spaces ）
         ^
 The first  2  Step ："words and 987"（ No characters are currently read in , Because it doesn't exist here  '-'  perhaps  '+'）
         ^
 The first  3  Step ："words and 987"（ Because of the current character  'w'  It's not a number , So read in stop ）
         ^
 Parse to get an integer  0 , Because I didn't read in any numbers .
 because  0  In scope  [-231, 231 - 1]  Inside , The final result is  0 .

Example 5：

 Input ：s = "-91283472332"
 Output ：-2147483648
 explain ：
 The first  1  Step ："-91283472332"（ No characters are currently read in , Because there are no leading spaces ）
         ^
 The first  2  Step ："-91283472332"（ Read in  '-'  character , So the result should be negative ）
          ^
 The first  3  Step ："-91283472332"（ Read in  "91283472332"）
                     ^
 Parse to get an integer  -91283472332 .
 because  -91283472332  Less than range  [-231, 231 - 1]  Lower bound of , The final result is truncated to  -231 = -2147483648 .

Tips ：

• 0 <= s.length <= 200
• s By the English letters （ Uppercase and lowercase ）、 Numbers （0-9）、' '、'+'、'-' and '.' form

Java Basic data type maximum limit and minimum limit

public static void main(String[] args)
{
    
  System.out.println("Integer.MIN_VALUE = " + Integer.MIN_VALUE);
  System.out.println("Integer.MAX_VALUE = " + Integer.MAX_VALUE);

  System.out.println("Long.MIN_VALUE = " + Long.MIN_VALUE);
  System.out.println("Long.MAX_VALUE = " + Long.MAX_VALUE);

  System.out.println("Float.MIN_VALUE = " + Float.MIN_VALUE);
  System.out.println("Float.MIN_NORMAL = " + Float.MIN_NORMAL);
  System.out.println("Float.MAX_VALUE = " + Float.MAX_VALUE);

  System.out.println("Double.MAX_VALUE = " + Double.MAX_VALUE);
  System.out.println("Double.MIN_VALUE = " + Double.MIN_VALUE);
}


 The input results are as follows ： See for yourselves ：

Integer.MIN_VALUE = -2147483648
Integer.MAX_VALUE = 2147483647
Long.MIN_VALUE = -9223372036854775808
Long.MAX_VALUE = 9223372036854775807
Float.MIN_VALUE = 1.4E-45
Float.MIN_NORMAL = 1.17549435E-38
Float.MAX_VALUE = 3.4028235E38
Double.MAX_VALUE = 1.7976931348623157E308
Double.MIN_VALUE = 4.9E-324

use long Record

1、 Find the first non empty character position k, if k == n Indicates that all characters are empty , Go straight back to 0

2、op Record the positive and negative of the truncated integer ,1 A positive sign ,-1 A minus sign

3、 Use long Type of res To store the truncated integer （ It must be a positive integer , Because the brackets haven't included ）, At a certain moment, if res > INT_MAX, be break, It means that

4、 Intercept to res after , Enclosed op The symbol of , if res > INT_MAX perhaps res < INT_MIN Then return... Respectively INF_MAX perhaps INT_MIN

class Solution {
    
    public int myAtoi(String str) {
    
        int n = str.length();
        int k = 0;
        while(k < n && str.charAt(k) == ' ') k ++;
        if(k == n) return 0;

        int op = 1;// Assume a positive sign 
        if(str.charAt(k) == '-') 
        {
    
            op = -1;
            k ++;
        }
        else if(str.charAt(k) == '+') k ++;

        long res = 0;
        while(k < n && str.charAt(k) >= '0' && str.charAt(k) <= '9')
        {
    
            res = res * 10 + str.charAt(k) - '0';
            k ++;

            if(res > Integer.MAX_VALUE) break;
        }

        res = res * op;
        if(res > Integer.MAX_VALUE) res = Integer.MAX_VALUE;
        if(res < Integer.MIN_VALUE) res = Integer.MIN_VALUE;

        return (int)res;
    }
}

use int Record

1、 Find the first non empty character position k, if k == n Indicates that all characters are empty , Go straight back to 0

2、op Record the positive and negative of the truncated integer ,1 A positive sign ,-1 A minus sign

3、 Use int Type of res To store the truncated integer （ It must be a positive integer , Because the brackets haven't included ）,
At a certain moment, if op Positive number ,(res * 10 + x) * op > INT_MAX, namely res * op > (INT_MAX - x ) / 10, Then return to INF_MAX, It means that （ among x Positive number ）
At a certain moment, if op It's a negative number ,(res * 10 + x) * op < INT_MIN, namely res * op > (INT_MIN - x * (-1)) / 10, Then return to INF_MIN, It means that （ among x It's a negative number ）

4、 Intercept to res after , Enclosed op The symbol of , if res > INT_MAX perhaps res < INT_MIN Then return... Respectively INF_MAX perhaps INT_MIN
5、 Finally back to res

class Solution {
    
    public int myAtoi(String str) {
    
        int n = str.length();
        int k = 0;
        while(k < n && str.charAt(k) == ' ') k ++;
        if(k == n) return 0;// Did not find 

        int op = 1;// Assume a positive sign 
        if(str.charAt(k) == '-') 
        {
    
            op = -1;
            k ++;
        }
        else if(str.charAt(k) == '+') k ++;

        int res = 0;
        while(k < n && str.charAt(k) >= '0' && str.charAt(k) <= '9')
        {
    
            int x = str.charAt(k) - '0';
            if(op > 0 && res * op > (Integer.MAX_VALUE - x ) / 10) 
            {
    
                res = Integer.MAX_VALUE; break;
            }
            if(op < 0 && res * op < (Integer.MIN_VALUE - x * (-1)) / 10) 
            {
    
                res = Integer.MIN_VALUE; break;
            }
            res = res * 10 + str.charAt(k) - '0';
            k ++;
        }
        return res * op;
    }
}