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.
Idea: We need to handle a few special cases,
1) possible empty spaces before and after the digits.
Solved by: trim()
2) possible '+' or the '-' symbol in the front of the digits.
Solved by: check the first symbol
3) possible overflow if bigger than Integer.MAX_VALUE or smaller than Integer.MIN_VALUE.
Solved by: Use a long type variable to cache the result, whenever the partial result is out of the boundary (max_value, min_value), stop and return. Otherwise the result may even overflow in long type......
Time: O(n) Space: O(1)
Code:
public class Solution {
public int atoi(String str) {
str=str.trim();
if(str.length()==0)
return 0;
int sign=1;
int index=0;
if(str.charAt(index)=='+')
{
sign=1;
index++;
}
else if(str.charAt(index)=='-')
{
sign=-1;
index++;
}
long num=0;
while(index<str.length())
{
if(str.charAt(index)<'0'||str.charAt(index)>'9')
break;
num=num*10+(int)(str.charAt(index)-'0');
if(num*sign>Integer.MAX_VALUE||num*sign<Integer.MIN_VALUE)
break;
index++;
}
if(sign*num>Integer.MAX_VALUE)
return Integer.MAX_VALUE;
if(sign*num<Integer.MIN_VALUE)
return Integer.MIN_VALUE;
return (int)(sign*num);
}
}
No comments:
Post a Comment