Description:
Implement
atoi
to convert a string to an integer.
Hint: Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input cases.
Notes: It is intended for this problem to be specified vaguely (ie, no given input specs). You are responsible to gather all the input requirements up front.
Update (2015-02-10):
The signature of theC++
function had been updated. If you still see your function signature accepts aconst char *
argument, please click the reload button to reset your code definition.
Requirements for atoi:
The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.
The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.
If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.
If no valid conversion could be performed, a zero value is returned. If the correct value is out of the range of representable values, INT_MAX (2147483647) or INT_MIN (-2147483648) is returned.
Solutions:
Approach 1: Use long
to handle the overflow
We need to deal with 4 issues[[1]]:
- trim leading white spaces
- number sign
- overflow
- invalid input
[1]:https://discuss.leetcode.com/topic/2666/my-simple-solution?page=1
The 1st problem can be handled in 2 ways:
1.use trim()
method of String
object or 2. use a pointer to skip all the leading spaces and end up at the first non-whitespace character
The 2nd problem is easy to solve. We just need to see if the first non-whitespace character is '+' or '-'.
The 3rd problem can be handled by using a long
variable, once we find the overflow happens, we break the loop and return the max_int
or min_int
.
The 4th problem is easy, too. Once we meet the non-digit character, we just stop our calculation process.
Here is the solution:
public class Solution {
public int myAtoi(String str) {
String s = str.trim();
if (s.length() == 0 || s == null) return 0;
boolean positive = true;
int i = 0;
if (s.charAt(0) == '-') {
positive = false;
i++;
} else if (s.charAt(0) == '+') {
i++;
}
long res = 0;
while (i < s.length() && (s.charAt(i) >= '0' && s.charAt(i) <= '9')) {
res = res*10 + s.charAt(i) - '0';
i++;
System.out.println("---" + i);
// Note: you cannot use res > int_max+1
// becuase int_max+1 will overflow to be int_min
// why we use res-1 > int_max but not res > int
// is because we need to handle both int_max and int_min
if (res-1 > Integer.MAX_VALUE) break;
}
if (positive) {
if (res > Integer.MAX_VALUE) return Integer.MAX_VALUE;
return (int)res;
} else {
if (res-1 > Integer.MAX_VALUE) return Integer.MIN_VALUE;
return ((int)res)*(-1);
}
}
}
Approach 2: Use int
to handle the overflow
In Approach 1, we check if the overflow happens after each calculation. However, we can "predict" if the overflow will happen before calculation.
As in Approach 1, the calculation process is res = res*10 + s.charAt(i)
and the res
is always positive through the process. However, when we are going to "add" the next digit character to res
, we can check if res
is going to overflow by checking:
res > Integer.MAX_VALUE / 10 || (res == Integer.MAX_VALUE / 10 && str.charAt(i) - '0' > 7)
Explanation:
- If
res > Integer.MAX_VALUE/10
, this will causeres*10 > Integer.MAX_VALUE
in the next calculation, so ifres > Integer.MAX_VALUE/10
, the overflow must happen. - If
res == Integer.MAX_VALUE/10
, the overflow may not necessarily happen because if the next digit character is7
or even small.res*10 + 7
is still can be presented by anint
variable. But if the next digit character is greater than7
, it only can be8
or9
. Then we should take the number sign into consideration. However, if we think it over carefully: - if the number is positive: whether the next is
8
or9
,res
overflows, so we should returnInteger.MAX_VALUE
immediately. - if the number is negative: if the next is
8
,res
does not overflow but would beInteger.MAX_VALUE
, at this point we don't have to see if the next character is digit and "add" it tores
because the overflow will happen so we should returnInteger.MIN_VALUE
; if the next is9
,res
overflows and we should returnInteger.MIN_VALUE
. As a result, whether it is8
or9
, we should returnInteger.MIN_VALUE
.
So only res == Integer.MAX_VALUE/10
is not enough to say that overflow will happen but res == Integer.MAX_VALUE/10 && s.charAt(i- > '7'
will handle it.
The solution is:
public class Solution {
public int myAtoi(String str) {
if (str == null || str.isEmpty()) return 0;
int sign = 1, base = 0, i = 0, n = str.length();
while (i < n && s.charAt(i) == ' ') i++;
if (i < n && (str.charAt(i) == '-' || str.charAt(i) == '+'))
sign = str.charAt(i++) == '-' ? -1 : 1;
while (i < n && str.charAt(i) >= '0' && str.charAt(i) <= '9') {
if (res > Integer.MAX_VALUE / 10 || (res == Integer.MAX_VALUE / 10 && str.charAt(i) - '0' > 7)) {
return (sign == 1) ? Integer.MAX_VALUE : Integer.MIN_VALUE;
}
res = 10 * res + (str.charAt(i++) - '0');
}
return res * sign;
}
}
Note: every time we call s.charAt(i)
we should check if i
goes out of the boundary.