LeetCode刷题实战8：字符串转换整数

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选 ！

今天和大家聊的问题叫做字符串转换整数，我们先来看题面：

Implement atoi which converts a string to an integer.

The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.

The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.

If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.

If no valid conversion could be performed, a zero value is returned.

https://leetcode-cn.com/problems/string-to-integer-atoi/

翻译

请你来实现一个 atoi 函数，使其能将字符串转换成整数。

首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。接下来的转化规则如下：

如果第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字字符组合起来，形成一个有符号整数。

假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成一个整数。

该字符串在有效的整数部分之后也可能会存在多余的字符，那么这些字符可以被忽略，它们对函数不应该造成影响。

注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换，即无法进行有效转换。

在任何情况下，若函数不能进行有效的转换时，请返回 0 。

提示：

本题中的空白字符只包括空格字符 ' ' 。

假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−231,  231 − 1]。如果数值超过这个范围，请返回  INT_MAX (231 − 1) 或 INT_MIN (−231) 。

样例

示例 1:
输入: "42"输出: 42示例 2:
输入: " -42"输出: -42解释: 第一个非空白字符为 '-', 它是一个负号。  我们尽可能将负号与后面所有连续出现的数字组合起来，最后得到 -42 。示例 3:
输入: "4193 with words"输出: 4193解释: 转换截止于数字 '3' ，因为它的下一个字符不为数字。示例 4:
输入: "words and 987"输出: 0解释: 第一个非空字符是 'w', 但它不是数字或正、负号。 因此无法执行有效的转换。


解题分析

这道题问的内容不是很深刻，无非就是字符串的简单处理，使用Java对字符串进行处理也是很简单的，所以就采用了java的算法，不过java这玩意儿相对来说确实要深一点，会用hash和不会用hash完全是两种水平！

首先我们使用trim()去掉字符串两端的空格

其次拿出第一个字符，如果不是+、 -、 数字 则返回0

否则第一个合法，入队

接着循环一个字符一个字符判断，如果是数字就直接入队，不是则终止循环

紧接着需要判断是否只有 +、-号的情况

最后得到数字字符串队列，调用Integer.parseInt()对队列进行转换操作，如果遇到异常则处理异常，异常有两种情况：

(1).超过最大整数，则返回Integer.MAX_VALUE ( 0x7fffffff )

(2). 超过最小整数,则 返回Integer.MIN_VALUE ( 0x80000000 )

class Solution {
    public int myAtoi(String str) {
        str = str.trim(); //第一步去掉前后的空格
        StringBuilder ans = new StringBuilder();
        if(str.length() < 1){
            return 0;
        }
        // 判断第一个是什么 是符号或者数字，其它的话直接返回0
        char ch = str.charAt(0);
        if(ch != '-' && ch != '+' && (ch < '0' || ch > '9')){
            return 0;
        }
        //第一个是合法的
        ans.append(ch);
        //接着，慢慢进入字符
        for (int i = 1; i < str.length(); i++){
            if (str.charAt(i) >= '0' && str.charAt(i) <= '9'){
                ans.append(str.charAt(i));
            }else {
                break;
            }
        }
        //排除只有正负号的情况
        if (ans.length() <= 1 && (ans.charAt(0) == '+' || ans.charAt(0) == '-')){
            return 0;
        }
        //ans就是得到的数字，但是不知道大小
        try {
            return Integer.parseInt(ans.toString());
        } catch (NumberFormatException e) {
            if (ans.charAt(0) == '-'){
                return Integer.MIN_VALUE;
            }else {
                return Integer.MAX_VALUE;
            }
        }
    }
}

本题官方还给了另外个方法：有限状态机 ，大家有兴趣的自己去leetcode学习一下，今天文章就不说了。

如果喜欢本文，请顺手点个赞或者转发吧。

上期推文：

LeetCode刷题实战1：在数组上遍历出花样

LeetCode刷题实战2：用链表模拟加法

LeetCode刷题实战3：最长不重复子串

LeetCode刷题实战4：两个正序数组的中位数

LeetCode刷题实战5：判断回文子串

LeetCode刷题实战6：Z字形变换

LeetCode刷题实战7：整数反转