This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details
preface
The string conversion integer (AToi) is shown below:
MyAtoi (string s) converts a string to a 32-bit signed integer (similar to atoi in C/C++). MyAtoi (string s)
- Read in the string and discard useless leading whitespace
- Checks whether the next character (assuming it has not reached the end of the character) is a plus or minus sign and reads that character (if any). Determine whether the final result is negative or positive. If neither exists, the result is assumed to be positive.
- Read the next character until the next non-numeric character is reached or the end of the input is reached. The rest of the string is ignored.
- Convert the numbers read in the previous steps to integers (that is, “123” -> 123, “0032” -> 32). If no number is read in, the integer is 0. Change symbols as necessary (starting with Step 2).
- If the number of integers exceeds the 32 – bit signed integer range
[- 231, 231-1), you need to truncate the integer to keep it in the range. Specifically, integers less than −231 should be fixed to −231 and integers greater than 231 − 1 to 231 − 1. - Returns an integer as the final result.
Note:
Whitespace characters in this case include only the space character ‘ ‘. Do not omit any characters other than those following a leading space or number.
Example 1:
Example 2
Example 3
A, thinking
This is a long question, so you need to read the question several times. Write algorithm questions is to understand the meaning of the topic, and then combined with the data structure can be expressed
Read a string from left to right, taking consecutive digits (including ‘-‘ and ‘+’). Discard leading whitespace, continuing to the right
With a flow chart, it may be clear!
Second, the implementation
Since leading whitespace only appears before the string, to simplify the code, discard all leading whitespace before starting the loop and use a sliding window to find consecutive numeric strings
Variables are described as follows: left: indicates the left border of the window. Right: indicates the right border of the window. Flag: Indicates whether the value is positive
public int myAtoi(String s) {
// Discard all null characters
int left = 0;
int right;
while (true) {
// Return directly if the boundary is crossed
if (left == s.length())
return 0;
if(s.charAt(left) ! =' ')
break;
left ++;
}
int flag = 1;
/ / plus
if (s.charAt(left) == '+') {
right = ++left;
} else if (s.charAt(left) == The '-') {
flag = -1;
right = ++left;
} else if(s.charAt(left) >= '0' && s.charAt(left) <= '9') {
right = left + 1;
} else {
return 0;
}
// Extract as many numbers as possible
while(right < s.length()) {
if(s.charAt(right) < '0' || s.charAt(right) > '9') {
break;
}
right ++;
}
// There are no numbers
if (left == right)
return 0;
int ret = 0;
for (char c : s.substring(left, right).toCharArray()){
int temp = c-'0';
// 10 * ret + temp < integer.max_value
if (ret > (Integer.MAX_VALUE - temp )/10) {
return flag == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
}
ret = ret * 10 + temp;
}
return ret * flag;
}
Copy the codeThe following information is displayed:
Three, how to improve
After seeing the AC code above, I don’t know if you will agree with me that it is too long and not concise. Even with comments, too much boundary judgment is a big project for later maintenance. So follow me to optimize the code above!
The most complex part of the code above is the many If/Else judgments, so how do you optimize this part? In Java, you can use state machines to solve complex processes and condition judgments.
Note the following points when writing to a state machine:
- Define state
- Define the action
- State to state flow
Here is a reference to the state machine definition in the official solution
State machine description: there are four state lines: start, signed, in_number, and end. For example, start -> in_number indicates that the current state is start, and the state is changed to in_number because of the number read
In practical engineering, state machines usually use interfaces to define behavior. Implementation classes define states and implement interfaces.
public int myAtoi(String str) {
Automaton automaton = new Automaton();
int length = str.length();
for (int i = 0; i < length; ++i) {
// End the loop prematurely
if(! automaton.get(str.charAt(i))) {return (int) (automaton.sign * automaton.ans); }}return (int) (automaton.sign * automaton.ans);
}
/** * state machine */
class Automaton {
public int sign = 1;
public long ans = 0;
// Initial state
private String state = "start";
// Define the state
private Map<String, String[]> table = new HashMap<String, String[]>() {{
put("start".new String[]{"start"."signed"."in_number"."end"});
put("signed".new String[]{"end"."end"."in_number"."end"});
put("in_number".new String[]{"end"."end"."in_number"."end"});
put("end".new String[]{"end"."end"."end"."end"});
}};
public boolean get(char c) {
boolean flag = true;
// Next state
state = table.get(state)[get_col(c)];
if ("in_number".equals(state)) {
ans = ans * 10 + c - '0';
ans = sign == 1 ? Math.min(ans, Integer.MAX_VALUE) : Math.min(ans, -(long) Integer.MIN_VALUE);
} else if ("signed".equals(state)) {
sign = c == '+' ? 1 : -1;
} else if ("end".equals(state)) {
flag = false;
}
return flag;
}
// State flow
private int get_col(char c) {
if (c == ' ') {
return 0;
}
if (c == '+' || c == The '-') {
return 1;
}
if (Character.isDigit(c)) {
return 2;
}
return 3; }}Copy the codeThe following information is displayed:
Four,
You’ll notice that the state machine is slower than If/Else, so it’s a trade-off between maintainability and execution speed. For real projects, a good maintainability is often more important!
Today is the eighth question of the buckle ~ this series will update the 1-10 questions of the buckle for 10 consecutive days! Dig gold coin, I come 😁