Leetcode(8) -字符串转整数 - java版
Leetcode(8) -字符串转整数 - java版
题目
难度: 中等
请你来实现一个 atoi函数，使其能将字符串转换成整数。
首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。
当我们寻找到的第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字组合起来，作为该整数的正负号；假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数。
该字符串除了有效的整数部分之后也可能会存在多余的字符，这些字符可以被忽略，它们对于函数不应该造成影响。
注意 假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换。
在任何情况下，若函数不能进行有效的转换时，请返回 0。
说明：
假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [-2147483648 , 2147483647]。如果数值超过这个范围，请返回 INT_MAX 或 INT_MIN 。
示例1:
输入: "42"
输出: 42
示例2:
输入: " -42"
输出: -42
解释: 第一个非空白字符为 '-', 它是一个负号。
我们尽可能将负号与后面所有连续出现的数字组合起来，最后得到 -42 。
示例3:
输入: "words and 987"
输出: 0
解释: 第一个非空字符是 'w', 但它不是数字或正、负号。
因此无法执行有效的转换。
一. 逐位判断&字符串拼接
因为LeetCode不支持BigInteger类所以此方法不作推荐
具体思路:
第一步: 遍历字符串,从头开始找到第一个非空的数,再判断其是否为非数字且不为"+"或"-",若是,则返回0,若不是则继续执行第二步.(这里还要进行边界判断)
第二步:将第一个非空的数保存到一个新字符串ans中.
第三步:判断第一个非空字符的下一位是否为非数字,若为非数字,则返回0,若不是继续执行第三步.
第四步:从第一个非空数开始向下遍历字符串,直到找到第一个非数字字符,或遍历到字符串末尾,并将每次遍历得到的字符拼接到字符串ans中.
第五步:将String类型的ans转为BigInteger的resultlong,并将resultlong与Integer.MAX_VALUE以及Integer.MIN_VALUE进行分别判断,并作返回处理.
第六步:返回Integer.parseInt(ans).
实现:
class Solution {
public int myAtoi(String str) {
int i = 0,n = str.length();
//若为空串,直接返回0
if(n == 0) return 0;
//遍历字符串,找到第一个非空字符的索引
while(i<str.length()-1 && ' ' == str.charAt(i)) i++;
//如果第一个非空字符不是正,负,且不是数字,则直接返回0
if('+'!=str.charAt(i) && '-'!=str.charAt(i) && (str.charAt(i)>'9'||str.charAt(i)<'0')) return 0 ;
String ans = str.charAt(i++)+"";
//判断第一个非空字符的下一位是否为非数字,若为非数字,则返回0
if(i!=n&& !Character.isDigit(str.charAt(i))) return 0;
//向下遍历字符串,并进行拼接
while(i<str.length() && Character.isDigit(str.charAt(i))){
ans += str.charAt(i);
i++;
}
//将字符串转为BigInteger
BigInteger resultlong=new BigInteger(ans);
//溢出判断
if(resultlong.compareTo(new BigInteger(String.valueOf(Integer.MAX_VALUE)))==1)
return Integer.MAX_VALUE;
if(resultlong.compareTo(new BigInteger(String.valueOf(Integer.MIN_VALUE)))==-1)
return Integer.MIN_VALUE;
//转为Int类型返回
return Integer.parseInt(ans);
}
}
二. 溢出前判断
具体思路:
第一步:先跳过空格,然后检测加减号,如果首位非空字符为加号或数字,则isPositive为1,若为负号,则isPositive为-1,若为其他字符,直接返回0.
第二步:向后遍历字符串,在更新得到数字之前先进行溢出判断,之后通过ans = ans*10+isPositive*num;来把字符串转为数字.
第三步:返回ans.
实现:
class Solution {
public int myAtoi(String str) {
int index = 0;
//找到第一个非空的index
while(index <str.length()){
if(str.charAt(index) == ' ') index++;
else break;
}
if(index ==str.length()) return 0;
char curr = str.charAt(index);
//去掉异常情况
if(curr!='+' && curr!='-' && (curr>'9'||curr<'0')) return 0;
int isPositive = 1, num = 0,ans =0;
if(curr == '+') index++;
if(curr == '-') {index++;isPositive = -1;}
//向后遍历字符串
while(index <str.length()){
curr = str.charAt(index);
if(curr>'9' || curr<'0') break;
num = curr - '0';
//溢出前判断
if(ans>Integer.MAX_VALUE/10 || (ans ==Integer.MAX_VALUE/10&&num>7)) return Integer.MAX_VALUE;
if(ans<Integer.MIN_VALUE/10 || (ans ==Integer.MIN_VALUE/10&&num>8)) return Integer.MIN_VALUE;
ans = ans*10+isPositive*num;
index++;
}
return ans;
}
}
