剑指 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》