String ----- 6. String conversion integer (atoi)

Day 11: string to integer (atoi)

Title Link: https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnoilh/

Title:

Please implement a myAtoi(string s) function to convert the string into a 32-bit signed integer (similar to the atoi function in C/C + +).

The algorithm of the function myAtoi(string s) is as follows:

  • Read in the string and discard useless leading spaces
  • Check whether the next character (assuming it has not reached the end of the character) is a positive or negative sign, and read the character (if any). Determines whether the final result is negative or positive. If neither exists, the result is assumed to be positive.
  • Reads the next character until the next non numeric character is reached or the end of the input is reached. The rest of the string will be ignored.
  • Convert these numbers read in the previous steps into integers (i.e., "123" - > 123, "0032" - > 32). If no number is read in, the integer is 0. Change the symbol if necessary (starting from step 2).
  • If the number of integers exceeds the range of 32-bit signed integers [− 231, 231 − 1], you need to truncate the integer to keep it within this range. Specifically, integers less than − 231 should be fixed as − 231, and integers greater than 231 − 1 should be fixed as 231 − 1.
  • Returns an integer as the final result.

be careful:

  • The white space character in this question only includes the white space character ''.
  • Do not ignore any characters other than the leading space or the rest of the string after the number.

Example 1:

Input: s = "42"
Output: 42
 Explanation: the bold string is the character that has been read in, and the caret is the character that is currently read.
Step 1:"42"(No characters are currently read in because there are no leading spaces)
         ^
Step 2:"42"(No characters are currently read in because they do not exist here '-' perhaps '+')
         ^
Step 3:"42"(Read in "42")
           ^
The integer 42 is parsed.
because "42" In scope [-231, 231 - 1] The final result was 42.

Example 2:

Input: s = "   -42"
Output:-42
 Explanation:
Step 1:"   -42"(Read leading spaces but ignore them)
            ^
Step 2:"   -42"(Read in '-' Character, so the result should be negative)
             ^
Step 3:"   -42"(Read in "42")
               ^
Parse to get an integer -42 . 
because "-42" In scope [-231, 231 - 1] The final result is -42 . 

Example 3:

Input: s = "4193 with words"
Output: 4193
 Explanation:
Step 1:"4193 with words"(No characters are currently read in because there are no leading spaces)
         ^
Step 2:"4193 with words"(No characters are currently read in because they do not exist here '-' perhaps '+')
         ^
Step 3:"4193 with words"(Read in "4193";Read in stops because the next character is not a number)
             ^
The integer 4193 is parsed.
because "4193" In scope [-231, 231 - 1] The final result was 4193.

Example 4:

Input: s = "words and 987"
Output: 0
 Explanation:
Step 1:"words and 987"(No characters are currently read in because there are no leading spaces)
         ^
Step 2:"words and 987"(No characters are currently read in because they do not exist here '-' perhaps '+')
         ^
Step 3:"words and 987"(Due to the current character 'w' Is not a number, so read in stops)
         ^
The integer 0 was parsed because no number was read in.
Because 0 is in range [-231, 231 - 1] Within, the final result is 0.

Example 5:

Input: s = "-91283472332"
Output:-2147483648
 Explanation:
Step 1:"-91283472332"(No characters are currently read in because there are no leading spaces)
         ^
Step 2:"-91283472332"(Read in '-' Character, so the result should be negative)
          ^
Step 3:"-91283472332"(Read in "91283472332")
                     ^
Parse to get an integer -91283472332 . 
because -91283472332 Less than range [-231, 231 - 1] The final result is truncated to -231 = -2147483648 . 

Tips:

  • 0 <= s.length <= 200
  • s consists of English letters (uppercase and lowercase), numbers (0-9), ',' + ',' - 'and'. '

Related label string

Problem solving:

  1. Pointer traversal

    General idea:

    There are three steps:

    1. Remove the leading space in front. If you encounter letters or other symbols, exit. If you encounter symbols or numbers for the first time, start the second step
    2. Record adjacent numeric strings until the end of a letter or symbol is encountered
    3. Convert to an integer for positive and negative overflow judgment

    The detailed code is as follows:

        public int myAtoi(String s) {
            char[] chars = s.toCharArray();
            int i=0;//Define a subscript
            int sign=1;//1 is positive and 0 is negative
            int left,right;//The subscript range of the numeric part of the record string
            //integer
            int sum=0;int temp;
            while(i<s.length()){
                //If a number is encountered, exit the loop
                if (chars[i]>='0'&&chars[i]<='9')
                    break;
                //When you encounter a space, move the subscript
                if (chars[i]==' '){
                    i++;
                    continue;
                }
                //First symbol encountered
                if (chars[i]=='+'||chars[i]=='-'){
                    if (chars[i]=='-') sign=0;
                    //Move the subscript right to determine whether it is a number
                    i++;
                    //Prevent overflow
                    if (i>=chars.length) return 0;
                    if (chars[i]>='0'&&chars[i]<='9') break;
                }
                return 0;
            }
            left=i;
            //Determines the subscript range of an integer
            while (i<chars.length){
                if(chars[i]>='0'&&chars[i]<='9') i++;
                else break;
            }
            right=i;
            for (int j = left; j < right; j++) {
                temp=sum;
                sum=temp*10+chars[j]-'0';
                //Determine whether overflow occurs and return the edge value
                if (sum/10!=temp){
                    if (sign==1) 
                        return 2147483647;
                    else  return -2147483648;
                }
            }
            if (sign==0) sum=-sum;
            return sum;
        }
    

Keywords: Algorithm leetcode string

Added by getmizanur on Thu, 30 Sep 2021 01:47:45 +0300