阳江北京网站建设,wordpress站点添加skype,公众号微信,网站建设行业的前景题目描述
请你来实现一个 myAtoi(string s) 函数#xff0c;使其能将字符串转换成一个 32 位有符号整数#xff08;类似 C/C 中的 atoi 函数#xff09;。
函数 myAtoi(string s) 的算法如下#xff1a;
读入字符串并丢弃无用的前导空格检查下一个字符#xff08;假设还…题目描述
请你来实现一个 myAtoi(string s) 函数使其能将字符串转换成一个 32 位有符号整数类似 C/C 中的 atoi 函数。
函数 myAtoi(string s) 的算法如下
读入字符串并丢弃无用的前导空格检查下一个字符假设还未到字符末尾为正还是负号读取该字符如果有。 确定最终结果是负数还是正数。 如果两者都不存在则假定结果为正。读入下一个字符直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。将前面步骤读入的这些数字转换为整数即123 - 123 0032 - 32。如果没有读入数字则整数为 0 。必要时更改符号从步骤 2 开始。如果整数数超过 32 位有符号整数范围 [−231, 231 − 1] 需要截断这个整数使其保持在这个范围内。具体来说小于 −231 的整数应该被固定为 −231 大于 231 − 1 的整数应该被固定为 231 − 1 。返回整数作为最终结果。
注意
本题中的空白字符只包括空格字符 。除前导空格或数字后的其余字符串外请勿忽略 任何其他字符。 示例 1
输入s 42
输出42
解释加粗的字符串为已经读入的字符插入符号是当前读取的字符。
第 1 步42当前没有读入字符因为没有前导空格^
第 2 步42当前没有读入字符因为这里不存在 - 或者 ^
第 3 步42读入 42^
解析得到整数 42 。
由于 42 在范围 [-231, 231 - 1] 内最终结果为 42 。
示例 2
输入s -42
输出-42
解释
第 1 步 -42读入前导空格但忽视掉^
第 2 步 -42读入 - 字符所以结果应该是负数^
第 3 步 -42读入 42^
解析得到整数 -42 。
由于 -42 在范围 [-231, 231 - 1] 内最终结果为 -42 。示例 3
输入s 4193 with words
输出4193
解释
第 1 步4193 with words当前没有读入字符因为没有前导空格^
第 2 步4193 with words当前没有读入字符因为这里不存在 - 或者 ^
第 3 步4193 with words读入 4193由于下一个字符不是一个数字所以读入停止^
解析得到整数 4193 。
由于 4193 在范围 [-231, 231 - 1] 内最终结果为 4193 。
方法一(普通解法)
public class LeetCode008字符串转换整数 {public int myAtoi(String s) {char[] c s.trim().toCharArray(); // 去除前导空格并转换为字符数组if (c.length 0) return 0; // 如果字符串为空返回0int res 0; // 初始化结果为0int bndry Integer.MAX_VALUE / 10; // 定义边界用于检查溢出int i 1, sign 1; // 初始化指针i和符号位sign// 检查字符串首字符以确定符号if (c[0] -) sign -1; // 如果是负号设置sign为-1else if (c[0] ! ) i 0; // 如果不是正号从头开始处理数字// 遍历剩余字符以构建整数for (int j i; j c.length; j) {if (c[j] 0 || c[j] 9) break; // 如果当前字符不是数字终止循环// 检查溢出如果res大于边界或者res等于边界且当前数字大于7考虑到MAX_VALUE的最后一位是7if (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; // 返回最终结果考虑符号位}}思考: res等于边界且当前数字大于7考虑到MAX_VALUE的最后一位是7 代表什么 Java中的Integer.MAX_VALUE Integer.MAX_VALUE的值是2,147,483,647。注意这个最大值的最后一位是7。 边界值bndry的计算 bndry被计算为Integer.MAX_VALUE / 10即214,748,364。这意味着任何时候res超过这个bndry值再乘以10并加上一个正整数就会超过Integer.MAX_VALUE。 处理最后一位数字 当res正好等于bndry即214,748,364时加上的下一个数字必须小于或等于7否则结果将超过Integer.MAX_VALUE。例如如果下一个数字是8那么res将变为2147483648这超出了int的最大值范围。 方法二(状态机) 我们也可以用下面的表格来表示这个自动机 接下来我们只需要把上面这个状态转换表抄进代码即可。
myAtoi 方法
public int myAtoi(String str) {Automaton automaton new Automaton(); // 创建一个自动机实例int length str.length(); // 获取字符串长度for (int i 0; i length; i) {automaton.get(str.charAt(i)); // 处理每个字符}return (int) (automaton.sign * automaton.ans); // 返回最终结果
}
Automaton 类
public int sign 1; // 符号位1表示正数-1表示负数
public long ans 0; // 存储计算的结果
private String state start; // 初始状态
private MapString, String[] table new HashMapString, String[]() {{ // 状态转移表put(start, new String[]{start, signed, in_number, end});put(signed, new String[]{end, end, in_number, end});put(in_number, new String[]{end, end, in_number, end});put(end, new String[]{end, end, end, end});
}};public void get(char c) {state table.get(state)[get_col(c)]; // 根据当前状态和输入字符的类型更新状态if (in_number.equals(state)) {ans ans * 10 c - 0; // 计算当前数字//ans在get方法里始终为正数所以要用 -(long) Integer.MIN_VALUE比较ans sign 1 ? Math.min(ans, (long) Integer.MAX_VALUE) : Math.min(ans, -(long) Integer.MIN_VALUE); // 检查溢出} else if (signed.equals(state)) {sign c ? 1 : -1; // 确定正负号}
}private int get_col(char c) { // 根据字符类型返回列索引if (c ) {return 0;}if (c || c -) {return 1;}if (Character.isDigit(c)) {return 2;}return 3;
}思考Math.min(ans, -(long) Integer.MIN_VALUE); 为什么要强制转换为Long比较 在Java中对 Integer.MIN_VALUE 取负数会导致溢出因为 int 类型的最大值是 2,147,483,647无法表示 2,147,483,648。所以要强制转化为long 状态机相关题目
LeetCode122之股票买卖的最好时机相关话题动态规划记忆搜索状态机贪心算法-CSDN博客 总结
普通解法要考虑很多边缘case,状态机的思路明了可以做到不重不漏可是编码比较复杂
