LeetCode.8-字符串转整数(String to Integer (atoi))

这是悦乐书的第349次升级，第374篇原创

01 看题和准备

今天详情的是LeetCode算法题中Medium级别的第4题（顺位题号是8）。实现将字符串转换为整数的atoi方法。

该函数首先去掉所需丢弃的空白字符，直到找到第一个非空白字符。而后，从该字符开始，采用可选的初始加号或者减号，后跟尽可能多的数字，并将它们转换为整数。

字符串可以包含在形成整数之后的其余字符，这些字符将被忽略并且对此函数的行为没有影响。

假如str中的第一个非空白字符不是有效的整数，或者者因为str是空的或者者只包含空白字符而不存在这样的序列，则不执行转换。

假如无法执行有效转换，则返回零值。

注意：

• 只有空格字符’ ‘被视为空格字符。

假设我们正在解决一个只能在32位有符号整数范围内存储整数的环境：[ -2^31,231 -1]。假如数值超出可表示值的范围，则返回INT_MAX（2^{31-1）或者INT_MIN（-2}31）。例如：

输入：“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+篇，公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词，获取系列文章合集。

以上就是一律内容，假如大家有什么好的解法思路、建议或者者其余问题，可以下方留言交流，点赞、留言、转发就是对我最大的回报和支持！