8. 字符串转换整数 (atoi)

矫情吗；* 2022-12-29 14:06 149阅读 0赞

# [8. 字符串转换整数 (atoi)][8. _ _atoi] #

## 1、参考资料 ##

[字符串转换整数 (atoi)官方题解][_atoi]

## 2、题目要求 ##

> **题目描述**

![image-20201221212353843][]

> **示例**

示例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 (−2^31) 。

## 3、代码思路 ##

> 方法一：字符串转换

首先需要明确转换的规则

1.  空格处理：取出前导空格
2.  正负号处理：处理数字的正负号
3.  数字的溢出处理：转换为 Integer.MAX\_VALUE 的逆运算

如何推入数字：`result = result * 10 + num`

> 方法二：自动机

参考自 LeetCode

为了有条理地分析每个输入字符的处理方法，我们可以使用自动机这个概念：我们的程序在每个时刻有一个状态 s，每次从序列中输入一个字符 c，并根据字符 c 转移到下一个状态 s’。这样，我们只需要建立一个覆盖所有情况的从 s 与 c 映射到 s’ 的表格即可解决题目中的问题。

本题可以建立如下图所示的自动机：

![image-20201222223301937][]

我们也可以用下面的表格来表示这个自动机：

![image-20201222223403674][]

接下来编程部分就非常简单了：我们只需要把上面这个状态转换表抄进代码即可。

另外自动机也需要记录当前已经输入的数字，只要在 s’ 为 in\_number 时，更新我们输入的数字，即可最终得到输入的数字。

## 4、代码实现 ##

> 方法一：字符串转换

class Solution {
        
        public int myAtoi(String str) {
        
            // Guard Safe
            if(str == null || str.length() == 0){
        
                return 0;
            }
            char[] charArray = str.toCharArray();
            int index = 0; // 字符下标索引
            boolean isPositive = true; // 是否为正数
            int res = 0; // 转换结果
            // 去除前导空格
            while (index < charArray.length && charArray[index] == ' ') {
        
                index++;
            }
            // 判断正负号
            if (index < charArray.length && charArray[index] == '+') {
        
                isPositive = true;
                index++;
            } else if (index < charArray.length && charArray[index] == '-') {
        
                isPositive = false;
                index++;
            }
            // 进行字符串的转换
            while (index < charArray.length && Character.isDigit(charArray[index])) {
        
                int num = charArray[index] - '0'; // 当前位的值
                if (isPositive == true) {
        
                    // 正数的处理
                    if (res > Integer.MAX_VALUE / 10 || (res == Integer.MAX_VALUE / 10 && num > Integer.MAX_VALUE % 10)) {
        
                        return Integer.MAX_VALUE;
                    }
                    res = res * 10 + num;
                } else {
        
                    // 负数的处理
                    if (res < Integer.MIN_VALUE / 10 || (res == Integer.MIN_VALUE / 10 && -num < Integer.MIN_VALUE % 10)) {
        
                        return Integer.MIN_VALUE;
                    }
                    res = res * 10 - num;
                }
                index++;
            }
            return res;
        }
    }

> 方法二：自动机

我有些许懵逼~~~

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;
        }
    }

[8. _ _atoi]: https://leetcode-cn.com/problems/string-to-integer-atoi/
[_atoi]: https://leetcode-cn.com/problems/string-to-integer-atoi/solution/zi-fu-chuan-zhuan-huan-zheng-shu-atoi-by-leetcode-/
[image-20201221212353843]: /images/20221120/95fe71bad8c94e5998f2ad4c6cb43b19.png
[image-20201222223301937]: /images/20221120/4fcc6ebda4e04bd9965c92e42ce152b2.png
[image-20201222223403674]: /images/20221120/6c0daa78dfd644c6ad417444609bd589.png