Leetcode 7 Reverse Integer and 8 String to Integer (atoi)
This two problem share lots of similarities in data manipulating and thinking, and simplicity (:-D). Thus I decide to put them together. First let me get two Reverse Integer problem.
Edit Reverse Integer on GitHub
The description and example of problem is as follow:
Example1: x = 123, return 321 Example2: x = -123, return -321
Basically there are two tricks in this problem:
1. For a integer like 1000 that ends with one or more zeros, we should ignore certain zeros after reverse.
2. As we all know, integer has it’s limit, just as everything else (:-D). For a 32-bit signed binary integer, the maximum positive value is 2^31-1 = 2147483647. The minimum negative value is -2^32 = -2147483648. Thus, if the original integer is 1000000003, then the reverse will be 3000000001, which will cause a overflow issue.
After simple analysis, we could get to the simplest part:
public class Solution { public int reverse(int x) { int isPositive = 1; double sum = 0; if (x<0){ isPositive=-1; x=isPositive*x; } while(x>0){ int temp=(int)(x/10); sum=sum*10+(x-10*temp); x=temp; if(sum>=2147483647) return 0; if(sum<=-2147483648) return 0; } return isPositive*(int)sum; } }
The number manipulation is basic. First we use a flag isPositive
to determine if the number is positive or negative. For convenience, we convert negatives to positive, and simply convert it back after reverse.
Take the number 123 as example. We just have to take the number in least significant order, which is 3 in this case, and use it to construct the reverse number. This part is int temp=(int)(x/10); sum=sum*10+(x-10*temp);
.
After first loop, we get sum = 3; x = 12;
After second loop, we get sum = 32; x = 1;
After final loop, we get sum = 321; x = 0;
and exit the loop since x = 0
During the loop, we should also have overflow protection, which is if(sum>=2147483647) return 0; if(sum<=-2147483648) return 0;
Edit String to Integer (atoi) on GitHub
This problem is to implement a atoi
function. Don’t tell you haven’t used a atoi function. There are several traps:
1. Since we are having String
as input, we should assume that any characters could be input. We will need validation for those. The function String.charAt()
is convenient to get each characters in string for validation. Thank got that integers from 0 to 9 is consecutive in ASCII, so that we can use String.charAt(i)>'9'||String.charAt(i)<'0'
For example, ^&*110
should return 0, 110&*^
should return 110 (the custom is to ignore all the characters after the left most invalud charater).
2. There might be spaces in front of or at the end of the inputs, we should trim those. For example, 1001
should return 1001. This can be done with String.trim()
3. Then we should consider the situation for signed integer. Thus we should have validation for string after trim to determine if the left most character is ‘+’ or ‘-‘ or valid number.
Now we get to simplest part again, the number manipulation is too straightforward to mention:
public class Solution { public int myAtoi(String str) { String trim=str.trim(); if (trim==null||trim.length()==0){ return 0; } double sum=0; int isPositive=1; for(int i=0;i<trim.length();i++){ if(i==0&&(trim.charAt(i)=='+'||trim.charAt(i)=='-')){ if(trim.charAt(i)=='-'){ isPositive=-1; } continue; } if(trim.charAt(i)>'9'||trim.charAt(i)<'0') break; sum=sum*10+trim.charAt(i)-'0'; } sum=sum*isPositive; return (int)sum; } }