1. 题目描述2. 解题思路3. 代码实现
3.1 依靠long判断溢出3.2 不依靠long判断溢出3.3 对比
1. 题目描述
这道题目要做的第一件事情是消去前导空格，这个简单，String类里面就有trim()函数是做这个事情的。
第二个事情，读取首位字符，决定是正数还是负数，还是说以外的字符。在这里要注意的是，我们习惯性思维上都认为如果是正数就直接是数字了，不会出现“+”号，其实是不恰当的，一开始我也是这样思考，直到有一个“+7542”（数字随便编的忘了）的测试用例过不了。因此第二件事情的判断首位字符是**“+”、“-”、数字还是其他字符**，其实理论上来说**“+”与数字是同一种情况**，代表的都是正数，因此我们可以取巧一点，在判断到是“+”的时候，直接把该字符去掉后调用本算法解决。
第三件事情是字符串转整数了，这个数理上很好解决，就不阐述了。
第四件事情，也是最关键的一件事情，如何判断该数据是否溢出了呢？我们看一眼题目，要求的是32位的数，就是int类型的数据，一个比较取巧的方法，我们在计算过程中使用long进行计算，在每一次计算结束后把它与int类型的最大值Integer.MAX_VALUE比较即可知道了，若溢出就立马返回。
但是吧，使用了long让我有一种像在作弊的感觉，不使用long可以解决吗？当然是可以的。首先我们来判断一下数据的溢出是发生在哪一步当中，更直白一点的表示就是“原数据-运算-溢出数据”，理论上来说溢出数据与原数据之间的运算关系已经不存在了（若存在他就应该是合理数据而不是溢出数据了），例如在int运算中214748365*10=-2147483646，但是**-2147483646/10=-214748364**，显然214748365≠-214748364，那就意味着溢出了。
这种情况有例外吗？其实是有的，也是我碰到了这个测试用例之后才发现，对于int运算2147483647+3=-2147483646，但是 -2147483646-3=2147483647，是不是很神奇？居然能合理运算，不过仔细观察一下还是可以进行判断的，显然运算后与原数据已经是异号了，这也是溢出的表现情况。因此，依靠以上的分析，就可以实现不依赖long的溢出判断了。
3. 代码实现 3.1 依靠long判断溢出public int myAtoi(String s) {
s = s.trim();
char[] chars = s.toCharArray();
long sum;
if (chars.length > 0 && Character.isDigit(chars[0])) {
sum = chars[0] - '0';
for (int i = 1; i < chars.length; i++) {
if (Character.isDigit(chars[i])) {
sum = sum * 10 + chars[i] - '0';
if (sum > Integer.MAX_VALUE)
return Integer.MAX_VALUE;
} else
return (int) sum;
}
} else if (chars.length > 1 && Character.isDigit(chars[1])) {
if (chars[0] == '+')
return myAtoi(s.substring(1));
if (chars[0] != '-')
return 0;
sum = -chars[1] + '0';
for (int i = 2; i < chars.length; i++) {
if (chars[i] >= '0' && chars[i] <= '9') {
sum = sum * 10 - chars[i] + '0';
if (sum < Integer.MIN_VALUE)
return Integer.MIN_VALUE;
} else
return (int) sum;
}
} else
return 0;
return (int) sum;
}
3.2 不依靠long判断溢出
public int myAtoi(String s) {
s = s.trim();
char[] chars = s.toCharArray();
int sum, pre;
if (chars.length > 0 && Character.isDigit(chars[0])) {
sum = chars[0] - '0';
for (int i = 1; i < chars.length; i++) {
if (Character.isDigit(chars[i])) {
pre = sum;
sum = sum * 10 + chars[i] - '0';
System.out.println(pre + "======" + sum);
if ((sum + '0' - chars[i]) / 10 != pre)
return Integer.MAX_VALUE;
} else
return sum;
}
return sum >= 0 ? sum : Integer.MAX_VALUE;
} else if (chars.length > 1 && Character.isDigit(chars[1])) {
if (chars[0] == '+')
return myAtoi(s.substring(1));
if (chars[0] != '-')
return 0;
sum = -chars[1] + '0';
for (int i = 2; i < chars.length; i++) {
if (chars[i] >= '0' && chars[i] <= '9') {
pre = sum;
sum = sum * 10 - chars[i] + '0';
if ((sum - '0' + chars[i]) / 10 != pre)
return Integer.MIN_VALUE;
} else
return sum;
}
return sum <= 0 ? sum : Integer.MIN_VALUE;
}
return 0;
}
3.3 对比
两个算法的差别不大，就只是改了两个判断条件而已，影响最大的是他们的空间复杂度，因为long所占用的空间比int大一倍，所以依靠long的算法的内存消耗也就更大了，但其实他们的空间复杂度都是O(1)，时间复杂度都是O(n)。
