闲聊

本月1号开始每天都刷着Leetcode的每日一题，今天是12号。前面的题目都挺顺的，今天的这题我是看懵了，是求两条线的交点【面试题 16.03. 交点】。刚看完题，哇，这不就是一元二次方程组吗，简单，初中数学吧...... 然后写着写着，30+分钟后...... 题解区见了。真的很考验编码的内功，很容易就写错了。不说了，接着今天的题目【字符串转换整数】

看题总结

请你来实现一个 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', 但它不是数字或正、负号。
     因此无法执行有效的转换。

示例 5:

输入: "-91283472332"
输出: -2147483648
解释: 数字 "-91283472332" 超过 32 位有符号整数范围。 
     因此返回 INT_MIN (?231) 。

Related Topics

通过对题目的阅读，我们可以得出以下几个结论

• 题目类型为字符串
• 题意为给定字符输出一个整数
• 输入安全判断，空字符串
• 返回值，无法转换返回0

多解法及复杂度分析

该题的解法可以分为3步

public int myAtoi(String str) {
        if (str == null || str.length() == 0) {
            return 0;
        }

        int index = 0;
        // 1. 去掉前导空格
        while (index < str.length() && str.charAt(index) == ' ') {
            index++;
        }

        if (index == str.length()) {
            return 0;
        }

        // 2. 判断符号
        int sign = 1;
        if (index < str.length() && str.charAt(index) == '-' || str.charAt(index) == '+') {
            sign = str.charAt(index) == '-' ? -1 : 1;
            index++;
        }

        // 3. 识别数字
        int tatol = 0;
        while (index < str.length()) {
            int digit = str.charAt(index) - '0';
            if (digit < 0 || digit > 9) {
                break;
            }
          
          	// 越界处理
            if ((Integer.MAX_VALUE / 10 < tatol) || (Integer.MAX_VALUE / 10 == tatol && Integer.MAX_VALUE % 10 < digit)) {
                return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
            }

            tatol = tatol * 10 + digit;
            index++;
        }
        return tatol * sign;
    }

复杂度分析

时间复杂度：O(n)，遍历一遍字符串 s

空间复杂度：O(1)，只用了几个变量

技巧与心得

1. 开一个github仓库用来记录各种题解
2. 在idea或者vscode中都提供了leecode的插件刷题，方便调试断走流程
3. 遇到不会的题不要慌，稳住心态直接看题解
4. 文字类的表述不如视图类的直观，图文并茂精选图解优先或者参考leetcode国际站的大牛题解
5. 图解依旧看着吃力也无妨，可以在哔哩哔哩或者YouTube上，通过leecode + 题号，搜索高收视率的视频观看
6. 多看几次本文跟我学：LeetCode刷题大法，相信我你肯定能越刷越自信

最后的最后

看到最后，我相信你对本题应该有不一样的感受了吧！在此若有不对之处或建议等，留言告诉我；若有疑惑或者不一样的看法，也请告诉我，我们可以一起探讨学习！

我是Yangcy，该吃吃该喝喝，该学还得学，我们一起加油！

点击左下角了解更多，查看所有LeetCode优质题解代码