剑指 Offer 67 把字符串转换成整数
摘要
面试题67. 把字符串转换成整数
一、字符串解析
根据题意,有以下四种字符需要考虑:
- 首部空格: 删除之即可;
- 符号位:三种情况,即 ''+'' , ''−'' , ''无符号";新建一个变量保存符号位,返回前判断正负。
- 非数字字符:遇到首个非数字的字符时,应立即返回。
- 数字字符:
- 字符转数字: “此数字的 ASCII 码” 与 “ 00 的 ASCII 码” 相减即可;
- 数字拼接:若从左向右遍历数字,设当前位字符为c ,当前位数字为x ,数字结果为res ,则数字拼接公式为:
数字越界处理:题目要求返回的数值范围应在 [−231,231−1],因此需要考虑数字越界问题。而由于题目指出 环境只能存储 32 位大小的有符号整数 ,因此判断数字越界时,要始终保持res在 int 类型的取值范围内。
- 在每轮数字拼接前,判断res在此轮拼接后是否超过 2147483647,若超过则加上符号位直接返回。
- 设数字拼接边界 bndry=2147483647//10=214748364 ,则以下两种情况越界:
package String;import org.junit.Test;/*** @Classname String.JZ67把字符转为整数* @Description TODO* @Date 2023/3/8 21:45* @Created by xjl*/
public class JZ67把字符转为整数 {public int strToInt(String str) {char[] c = str.trim().toCharArray();if (c.length == 0) {return 0;}int res = 0, bndry = Integer.MAX_VALUE / 10;int i = 0, sign = 1;if (c[0] == '-') {sign = -1;i++;} else if (c[0] == '+') {i++;}for (int j = i; j < c.length; j++) {if (c[j] < '0' || c[j] > '9') {break;}if (res > bndry || res == bndry && c[j] > '7') {return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;}res = res * 10 + (c[j] - '0');}return sign * res;}@Testpublic void test(){int i = strToInt(" -42");System.out.println(i);}
}
复杂度分析:
- 时间复杂度 O(N): 其中 N为字符串长度,线性遍历字符串占用O(N)时间。
- 空间复杂度 O(N): 删除首尾空格后需建立新字符串,最差情况下占用O(N)额外空间。
博文参考
《leetcode》