1.题目

请你来实现一个 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) 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/string-to-integer-atoi
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2.思路

字符数组
将字符串转化为字符数组
1.判断开头的空格（trim函数去空格
2.判断第一个非空字符：正负号或者数字
3.记录第一个的数字角标i，依次判断，记录最后一个符合要求的数字角标j
4.从j向i读取数字并乘10的n次方，累加
5.加上符号的正负，判断越界
6.输出结果
时间：N
空间：N

3.实现

一个没抓住重点的实现

class Solution {
    public int myAtoi(String str) {
        if(str == null || str.equals(""))
            return 0;

        int sign = 1;

        char[] ch = str.trim().toCharArray();
        if(ch.length == 0)
            return 0;
        if( !((ch[0] >= 48 && ch[0] <= 57 )|| ch[0] == '+' || ch[0] == '-') )
            return 0;
        if(ch[0] == '+')
        {
            System.out.println("+");
            return toInt(ch, 1, sign *= 1);
        }

        if(ch[0] == '-')
        {
            System.out.println("-");
            return toInt(ch, 1, sign *= -1);
        }
        return toInt(ch, 0, sign);


    }
    private int toInt(char[] ch, int k, int sign)
    {
        int i = k;
        int j = k;
        long result = 0 ;


        while(j < ch.length && ch[j] >= 48 && ch[j] <= 57 )
        {
            j++;
            System.out.println(j);
        }
        j--;


        for(int n = j; n >= i; n-- )
        {
            result += (ch[n]-48) * Math.pow(10, j - n);
            System.out.println(result);
        }
        result *= sign;
        if(result > Integer.MAX_VALUE)
            return Integer.MAX_VALUE;N
        if(result < Integer.MIN_VALUE)
            return Integer.MIN_VALUE;
        return (int)result;

    }
    
}

时间N
空间N
存在的问题：
1.long的使用：如果不使用long，那么在每一次累加时需要判断是否越界
2.字符数组的使用，增加了额外的空间，但更直观
3.trim()函数的使用：不使用也可以，增加一个判断空格的过程，建议使用
4.正向遍历同样可以获得结果，每次乘10加上字符代表数字即可

修改上述问题

class Solution {
    public int myAtoi(String str) {
        str = str.trim();//去除开头结尾空格
        
        if(str.length() == 0)//去除空格后的字符串为空串
            return 0;
        if( !Character.isDigit(str.charAt(0)) 
                && str.charAt(0) != '+' && str.charAt(0) != '-')//字符串开头是否符合要求
            return 0;
        int ans = 0;
        boolean flag = str.charAt(0) == '-';//标记负号,存在为真，不存在为假
        int i = Character.isDigit(str.charAt(0)) ? 0 : 1;//开始记录数字的位置

        while(i < str.length() && Character.isDigit(str.charAt(i)))
        {   //为什么用负数：负数的值比正数大1，可以表示全部正数，最后取反即可
            //对于负数a,正数b：10a-b = temp < min 
            int temp = ( (flag ? Integer.MIN_VALUE : Integer.MIN_VALUE + 1) + (str.charAt(i) - '0')) / 10;
            if(ans < temp)//负数比较
                return flag ? Integer.MIN_VALUE : Integer.MAX_VALUE;
            ans = ans * 10 - (str.charAt(i++) - '0');

        }
        return flag ? ans : ans * -1;

        
    }
}

时间N
空间1

4.总结思路与解法

本题为确定有限状态机（deterministic finite automaton, DFA）
我们的程序在每个时刻有一个状态 s，每次从序列中输入一个字符 c，并根据字符 c 转移到下一个状态 s’。这样，我们只需要建立一个覆盖所有情况的从 s 与 c 映射到 s’ 的表格即可解决题目中的问题。

将上述表格写入程序

class Solution {
    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);
    }
}

class Automaton {
    public int sign = 1;
    public long ans = 0;
    private String state = "start";
    private Map<String, String[]> table = new HashMap<String, 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 = 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;
    }
}

时间N
空间1

5.相关知识

• Math类：a的b次方：Math.pow(a, b)
• Character.isDigit()：判断一个字符是否为数字