标题来源: 8. 字符串转换整数 (atoi)

标题描绘：

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

函数myAtoi(string s) 的算法如下：

读入字符串并丢弃无用的前导空格 检查下一个字符（假设还未到字符结束）为正仍是负号，读取该字符（假如有）。 确定终究成果是负数仍是正数。 假如两者都不存在，则假定成果为正。 读入下一个字符，直到到达下一个非数字字符或到达输入的结束。字符串的其余部分将被忽略。 将前面过程读入的这些数字转换为整数（即，”123″ -> 123， “0032” -> 32）。假如没有读入数字，则整数为 0 。必要时更改符号（从过程 2 开端）。 假如整数数超越 32 位有符号整数规模 [−231,231−1][−2^{31}, 2^{31}− 1] ，需求截断这个整数，使其保持在这个规模内。详细来说，小于 −231−2^{31} 的整数应该被固定为 −231−2^{31} ，大于2312^{31}− 1 的整数应该被固定为 2312^{31}− 1 。 返回整数作为终究成果。

  • 示例:

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

示例1:
输入：s = "42"
输出：42

解释：加粗的字符串为现已读入的字符，插入符号是当时读取的字符。 第 1 步：”42″（当时没有读入字符，因为没有前导空格） ^ 第 2 步：”42″（当时没有读入字符，因为这儿不存在 ‘-‘ 或许 ‘+’） ^ 第 3 步：”42″（读入 “42”） ^ 解析得到整数 42 。 因为 “42” 在规模 [-231, 231 – 1] 内，终究成果为 42 。

思路

思路1 字符串处理的标题往往涉及杂乱的流程以及条件情况，假如直接上手写程序，一不小心就会写出极其臃肿的代码。

因此，为了有条理地剖析每个输入字符的处理方法，咱们可以运用自动机这个概念：

咱们的程序在每个时刻有一个状况 s，每次从序列中输入一个字符 c，并依据字符 c 转移到下一个状况 s’。这样，咱们只需求树立一个覆盖所有情况的从 s 与 c 映射到 s’ 的表格即可处理标题中的问题。

详细完成1

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

杂乱度剖析1:

  • 时刻杂乱度：O(n)，其间 n 为字符串的长度。咱们只需求顺次处理所有的字符，处理每个字符需求的时刻为O(1)。
  • 空间杂乱度：O(1)。