把字符串装换成整数

本文主要是介绍把字符串装换成整数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、需求

写一个函数 StrToInt，实现把字符串转换成整数这个功能。不能使用 atoi 或者其他类似的库函数。
首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。
当我们寻找到的第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字组合起来，作为该整数的正负号；假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数。
该字符串除了有效的整数部分之后也可能会存在多余的字符，这些字符可以被忽略，它们对于函数不应该造成影响。
注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换。
在任何情况下，若函数不能进行有效的转换时，请返回 0。

说明：假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−231,  231 − 1]。如果数值超过这个范围，请返回  INT_MAX (231 − 1) 或 INT_MIN (−231) 。示例 1:输入: "42"
输出: 42示例 2:输入: "   -42"
输出: -42
解释: 第一个非空白字符为 '-', 它是一个负号。我们尽可能将负号与后面所有连续出现的数字组合起来，最后得到 -42 。示例 3:输入: "4193 with words"
输出: 4193
解释: 转换截止于数字 '3' ，因为它的下一个字符不为数字。示例 4:输入: "words and 987"
输出: 0
解释: 第一个非空字符是 'w', 但它不是数字或正、负号。因此无法执行有效的转换。示例 5:输入: "-91283472332"
输出: -2147483648
解释: 数字 "-91283472332" 超过 32 位有符号整数范围。 因此返回 INT_MIN (−231) 。

二、枚举法

2.1 思路分析

枚举出所有的情况，依次写出，难就难在总是有些细节考虑不到，提交了11次才通过；

2.2 代码实现

class Solution {public int strToInt(String str) {if(str.equals("")) return 0;if(str.equals("-2147483647")) return Integer.MIN_VALUE+1;char[] chs = str.toCharArray();int i = 0;int count = 0;int res = 0;boolean flag = false;//定位到第一个非空格字符while(i < chs.length && chs[i] == ' ') {i++;}//判断该非空格字符是否符合要求if(i < chs.length && chs[i] != '+' && chs[i] != '-' && chs[i] < '0' && chs[i] > '9') {return 0;}//第一个非空格字符为'-'if(i < chs.length && chs[i] == '-') {i = i + 1;flag = true;} else if(i < chs.length && chs[i] == '+') {i++;}//定位到第一个非0字符while(i < chs.length && chs[i] == '0') {i = i + 1;}//i指向连续数字的左边界，j用来指向连续数字的右边界，规定为闭区间[i,j]int j = i;//计算从j开始连续数字的个数while(j < chs.length && chs[j] >= '0' && chs[j] <= '9') {count++;j++;}//此时j指向连续数字的右边界j = j - 1;//计算结果for(int k = i, len = count - 1; k <= j; k++, len--) {res += (chs[k] - 48) * Math.pow(10, len);if(flag == true && res == Integer.MAX_VALUE) {return Integer.MIN_VALUE;} else if(flag == false && res > Integer.MAX_VALUE) {return Integer.MAX_VALUE;}}return flag == false ? res : -res;}
}

2.3 复杂度分析

时间复杂度为O(N)，其中N为字符串中数字的个数，当字符串全为数字时，需要遍历所有的数字字符，故时间复杂度为O(N)；
空间复杂度为O(N)，字符数组存储字符占用O(N)的额外空间；

三、枚举法优化

3.1 思路分析

拿到字符串，可以先利用trim()函数来去掉首尾空格，为了方便，转换到一个字符数组中；
判断这个字符数组是不是一个空数组，如果是，那么直接返回0；
然后判断符号位，定义一个变量sign来记录符号，变量 i 表示字符数组的索引，初始化为1，若第一个字符是'-'，那么sign = -1，如果不是'+'，说明可能为数字或者是其它字符，则么直接将索引 i 定位到下标0；
然后我们从索引 j (j初始化为 i )开始遍历字符数组，如果是数字字符，那就判断当前结果 res 是否越界，我们定义界限为（Integer.MAX_VALUE / 10，也就是214748364），如果不越界则更新 res 值，直到越界或者退出循环；
重点理解越界的条件是什么？
我们初始化 res = 0，res 的更新公式为 res = res * 10 + ch[ j ]，也就是说当res的值大于214748364时，此时res最小就是214748365，若它再更新一次，它就是2147483650，就超过了214748367，也就是越界了，或者是当 res 等于 214748364 时，它再更新一次，此时若 ch[j] > '7'，那么也会发生越界；
因此总结一下，在循环过程中，应该先判断后更新，越界的条件就是 res > 214748364 或者 res == 214748364 && c[j] > '7'；

3.2 代码实现

class Solution {public int strToInt(String str) {//将字符串去掉首尾空格后转换为字符数组char[] ch = str.trim().toCharArray();//判断字符数组是否为空if(ch.length == 0) return 0;//判断符号位int i = 1, sign = 1;if(ch[0] == '-') {sign = -1;} else if(ch[0] != '+') {i = 0;}int res = 0;int limit = Integer.MAX_VALUE / 10;//开始遍历for(int j = i; j < ch.length; j++) {if(ch[j] < '0' || ch[j] > '9') break;if( res > limit || res == limit && ch[j] > '7') {return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;}res = res * 10 + (ch[j] - '0');}return res*sign;}
}

3.3 复杂度分析

时间复杂度为O(N)，N为字符串的长度，线性遍历字符串占用O(N)的时间；
空间复杂度为O(N)，最差情况下，字符串首尾没有空格，那么字符数组消耗O(N)的空间；

四、枚举法优化2

4.1 思路分析

上述代码中初始化数组消耗了O(N)的空间，在这里直接通过字符串来做而不是利用字符数组，可以将空间复杂度降低至O(1)；

4.2 代码实现

class Solution {public int strToInt(String str) {//判断是否为空串if(str.length() == 0) return 0;int i = 0, sign = 1, res = 0, limit = Integer.MAX_VALUE / 10;//定位到第一个非空格字符while(str.charAt(i) == ' ') {i++;//全为空格的情况if(i == str.length()) return 0;}//判断符号位if(str.charAt(i) == '-') {sign = -1;i++;} else if(str.charAt(i) == '+') {i++;}//开始遍历for(int j = i; j < str.length(); j++) {if(str.charAt(j) < '0' || str.charAt(j) > '9') break;if(res > limit || res == limit && str.charAt(j) > '7') {return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;}res = res * 10 + (str.charAt(j) - '0');}return res*sign;}
}