LeetCode_字符串_中等_8.字符串转换整数 (atoi)

港控/mmm° 2023-10-06 18:24 31阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数（类似 C/C++ 中的 atoi 函数）。

函数 myAtoi(string s) 的算法如下：  
① 读入字符串并丢弃无用的前导空格  
② 检查下一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如果有）。 确定最终结果是负数还是正数。 如果两者都不存在，则假定结果为正。  
③ 读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。  
④ 将前面步骤读入的这些数字转换为整数（即，“123” -> 123， “0032” -> 32）。如果没有读入数字，则整数为 0 。必要时更改符号（从步骤 ② 开始）。  
⑤ 如果整数数超过 32 位有符号整数范围 \[−231, 231 − 1\] ，需要截断这个整数，使其保持在这个范围内。具体来说，小于 −231 的整数应该被固定为 −231 ，大于 231 − 1 的整数应该被固定为 231 − 1 。  
⑥ 返回整数作为最终结果。

**注意：**  
本题中的空白字符只包括空格字符 ’ ’ 。  
除前导空格或数字后的其余字符串外，请勿忽略任何其他字符。

**示例 1：**

输入：s = "42"
    输出：42
    解释：加粗的字符串为已经读入的字符，插入符号是当前读取的字符。
    第 1 步："42"（当前没有读入字符，因为没有前导空格）
             ^
    第 2 步："42"（当前没有读入字符，因为这里不存在 '-' 或者 '+'）
             ^
    第 3 步："42"（读入 "42"）
               ^
    解析得到整数 42 。
    由于 "42" 在范围 [-2^31, 2^31 - 1] 内，最终结果为 42 。

**示例 2：**

输入：s = "   -42"
    输出：-42
    解释：
    第 1 步："   -42"（读入前导空格，但忽视掉）
                ^
    第 2 步："   -42"（读入 '-' 字符，所以结果应该是负数）
                 ^
    第 3 步："   -42"（读入 "42"）
                   ^
    解析得到整数 -42 。
    由于 "-42" 在范围 [-2^31, 2^31 - 1] 内，最终结果为 -42 。

**示例 3：**

输入：s = "4193 with words"
    输出：4193
    解释：
    第 1 步："4193 with words"（当前没有读入字符，因为没有前导空格）
             ^
    第 2 步："4193 with words"（当前没有读入字符，因为这里不存在 '-' 或者 '+'）
             ^
    第 3 步："4193 with words"（读入 "4193"；由于下一个字符不是一个数字，所以读入停止）
                 ^
    解析得到整数 4193 。
    由于 "4193" 在范围 [-2^31, 2^31 - 1] 内，最终结果为 4193 。

**提示：**  
0 <= s.length <= 200  
s 由英文字母（大写和小写）、数字（0-9）、’ ‘、’+‘、’-’ 和 ‘.’ 组成

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/string-to-integer-atoi

## 2.思路 ##

（1）遍历判断法  
常规思路：遍历字符串，依次判断每个字符。

*  使用trim()函数去掉字符串首尾的空格；
 *  设置需要的变量，例如存储临时字符的 c、区别结果正负的 sign（1 为正，-1 为负）、保存结果的 res（初始值为 0）等等；
 *  开始遍历字符串，使用 charAt() 函数获取当前字符并保存到 c 中，
    
     *  **如果 c 既不是正负号也不是数字**，则表示后续的字符与要转换的整数没有关系，所以退出遍历，返回结果res即可；
     *  **如果 c 的 ASCII 值为 \[48,57\] 之间的整数**，则表示c为数字字符，并将变量 flag 设置为 fasle，表示已经找到数字字符并开始转换为整数，如果在遍历后面的字符时遇到正负号，则不需要再给 sign 赋值；
     *  **如果 c 为正号或者负号并且 flag 为 true**，则对应地设置 sign 的值，并且与得到的 res 相乘即可；
 *  遍历结束后，sign \* res 的值即为所求的答案。

（2）自动机法  
思路1的代码大量使用了 if 判断语句，这样可能会导致写出来的代码比较臃肿，并且结构不是很清晰易懂。**如果在编写代码之前使用图表来展示出每个字符的可能情况，那么在编写代码时便会方便很多**。思路来源于[本题官方题解][Link 1]。

<table> 
 <thead> 
  <tr> 
   <th></th> 
   <th>’ ’</th> 
   <th>+/-</th> 
   <th>number</th> 
   <th>other</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>start</td> 
   <td>start</td> 
   <td>signed</td> 
   <td>in_number</td> 
   <td>end</td> 
  </tr> 
  <tr> 
   <td>signed</td> 
   <td>end</td> 
   <td>end</td> 
   <td>in_number</td> 
   <td>end</td> 
  </tr> 
  <tr> 
   <td>in_number</td> 
   <td>end</td> 
   <td>end</td> 
   <td>in_number</td> 
   <td>end</td> 
  </tr> 
  <tr> 
   <td>end</td> 
   <td>end</td> 
   <td>end</td> 
   <td>end</td> 
   <td>end</td> 
  </tr> 
 </tbody> 
</table>

## 3.代码实现（Java） ##

//思路1————遍历判断法
    public int myAtoi(String str) {
        
        //去掉无用的前后空格
        str = str.trim();
        if (str.isEmpty()) return 0;
        char c;
        //区别正负
        int sign = 1;
        long res = 0;
        boolean flag = true;
        int length = str.length();
        for (int i = 0; i < length; i++) {
        
            c = str.charAt(i);
            if (c != '-' && c != '+' && (c < 48 || c > 57)) {
        
                break;
            } else if (c >= 48 && c <= 57) {
        
                flag = false;
                res = res * 10 + Integer.parseInt("" + (c - 48));
                if (res * sign >= Integer.MAX_VALUE) return Integer.MAX_VALUE;
                if (res * sign <= Integer.MIN_VALUE) return Integer.MIN_VALUE;
            } else if (c == '-' && i + 1 < length && str.charAt(i + 1) >= 48 && str.charAt(i + 1) <= 57 && flag) {
        
                sign = -1;
            } else if (c == '+' && i + 1 < length && str.charAt(i + 1) >= 48 && str.charAt(i + 1) <= 57 && flag) {
        
                sign = 1;
            } else {
        
                break;
            }
        }
        res = res * sign;
        return (int) res;
    }

//思路2————自动机法
    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;
        }
    }

[Link 1]: https://leetcode-cn.com/problems/string-to-integer-atoi/solution/zi-fu-chuan-zhuan-huan-zheng-shu-atoi-by-leetcode-/