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:
-
Pointer traversal
General idea:
There are three steps:
- 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
- Record adjacent numeric strings until the end of a letter or symbol is encountered
- 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; }