这是悦乐书的第 349 次更新, 第 374 篇原创
01 看题和准备
今天介绍的是 LeetCode 算法题中 Medium 级别的第 4 题(顺位题号是 8). 实现将字符串转换为整数的 atoi 方法.
该函数首先去掉所需丢弃的空白字符, 直到找到第一个非空白字符. 然后, 从该字符开始, 采用可选的初始加号或减号, 后跟尽可能多的数字, 并将它们转换为整数.
字符串可以包含在形成整数之后的其他字符, 这些字符将被忽略并且对此函数的行为没有影响.
如果 str 中的第一个非空白字符不是有效的整数, 或者由于 str 是空的或者只包含空白字符而不存在这样的序列, 则不执行转换.
如果无法执行有效转换, 则返回零值.
注意:
只有空格字符' '被视为空格字符.
假设我们正在处理一个只能在 32 位有符号整数范围内存储整数的环境:[ -231,231 -1]. 如果数值超出可表示值的范围, 则返回 INT_MAX(231-1)或 INT_MIN(-231). 例如:
输入:"42"
输出: 42
输入:"-42"
输出:-42
说明: 第一个非空白字符是'-', 这是减号. 然后取尽可能多的数字, 得到 42.
输入:"4193 with words"
输出: 4193
说明: 转换在数字 "3" 处停止, 因为下一个字符不是数字.
输入:"words and 987"
输出: 0
说明: 第一个非空白字符是'w', 它不是数字或 +/- 符号. 因此, 无法执行有效转换.
输入:"-91283472332"
输出:-2147483648
说明: 数字 "-91283472332" 超出 32 位有符号整数的范围. 返回 INT_MIN(-2^31).
02 第一种解法
将字符串转成整数, 根据题目给的说明和试错, 需要考虑以下几个条件:
是否为空, 或者由空格组成.
是否带有正负符号, 正号可以忽略, 负号在返回结果时需要带上.
以 0 开头, 需要跳过连续的前置 0. 例如 "000123", 转换的结果是 123.
超过了 Integer 的最大边界或最小边界.
小数点可以忽略, 因为是转成整型, 会舍掉小数点后面的数.
出现多个正负符号, 直接返回 0. 例如 "+-2", 结果是 0.
第一位只能是数字 (0 到 9) 或者正负符号, 出现其他字符直接返回 0.
根据上面这些情况, 在关键处进行判断即可.
- public int myAtoi(String str) {
- str = str.trim();
- // 判空
- if (str.length() <1) {
- return 0;
- }
- // 判断首位字符
- char c = str.charAt(0);
- if (!Character.isDigit(c) && c != '-' && c != '+') {
- return 0;
- }
- // 判断符号
- boolean flag = false;
- if (c == '-') {
- flag = true;
- }
- int end = 0;
- for (int i=1; i<str.length(); i++) {
- if (Character.isDigit(str.charAt(i))) {
- end = i;
- } else {
- break;
- }
- }
- String newStr = str.substring(flag ? 1 : 0, end+1);
- if (newStr.length() < 1 || newStr.equals("+")) {
- return 0;
- }
- // 判断边界
- if (!newStr.startsWith("0") && newStr.length()> 12) {
- return flag ? Integer.MIN_VALUE : Integer.MAX_VALUE;
- }
- Long result = Long.parseLong(newStr);
- if (result.toString().length()> 11) {
- return flag ? Integer.MIN_VALUE : Integer.MAX_VALUE;
- }
- if (result> Integer.MAX_VALUE) {
- return flag ? Integer.MIN_VALUE : Integer.MAX_VALUE;
- }
- return flag ? 0-(int)result.longValue() : (int)result.longValue();
- }
03 第二种解法
在第一种解法的基础上, 我们还可以做下优化.
public int myAtoi2(String str) { if (str == null) { return 0; } str = str.trim(); if (str.isEmpty()) { return 0; } char c = str.charAt(0); int start = 0; if (c == '+' || c == '-') { start = 1; } int end = str.length(), n = str.length(); for (int i=start; i<n; i++) { char ch = str.charAt(i); if ("0123456789".indexOf(ch) <0) { end = i; break; } else { // 截取的字符串长度可能会超过 Integer 的边界 if (i>= 10) { long tem = Long.valueOf(str.substring(0, i+1)); if (tem> Integer.MAX_VALUE) { return Integer.MAX_VALUE; } else if (tem <Integer.MIN_VALUE) { return Integer.MIN_VALUE; } } } } if (end <= start) { return 0; } long result = Long.valueOf(str.substring(0, end)); if (result> Integer.MAX_VALUE) { return Integer.MAX_VALUE; } else if (result <Integer.MIN_VALUE) { return Integer.MIN_VALUE; } return (int)result; }
04 第三种解法
我们也可以不采用截取字符串的方式, 通过计算每一位数, 判断是否是 0 到 9 的数字, 并且判断是否越界.
public int myAtoi3(String str) { if (str == null) { return 0; } str = str.trim(); if (str.isEmpty()) { return 0; } int index = 0, total = 0, n = str.length(); int sign = 1; // 判断正负 // 只判断一次, 不能使用循环 if (index < n && (str.charAt(index) == '+' || str.charAt(index) == '-')) { sign = str.charAt(index) == '-' ? -1 : 1; index++; } // 计算整数 while (index < n) { int num = str.charAt(index)-'0'; if (num < 0 || num> 9) { break; } // 避免越界 if (total> Integer.MAX_VALUE/10 || (total == Integer.MAX_VALUE/10 && num> Integer.MAX_VALUE%10)) { return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE; } total = total*10 + num; index++; } return total*sign; }
05 小结
算法专题目前已连续日更超过六个月, 算法题文章 217 + 篇, 公众号对话框回复[数据结构与算法] ,[算法] ,[数据结构] 中的任一关键词, 获取系列文章合集.
以上就是全部内容, 如果大家有什么好的解法思路, 建议或者其他问题, 可以下方留言交流, 点赞, 留言, 转发就是对我最大的回报和支持!
来源: http://www.jianshu.com/p/83f0d21f8830