算法篇十 DFA确定有穷自动机

💡

DFA全称为：Deterministic Finite Automaton,即确定有穷自动机。其特征为：有一个有限状态集合和一些从一个状态通向另一个状态的边，每条边上标记有一个符号，其中一个状态是初态，某些状态是终态。

💡

NFA: 不确定有穷自动机: 当一个状态面对一个输入符号的时候，它所转换到的可能不只一个状态，可以是一个状态集合。 DFA与NFA的区别在于：DFA的每一次输入只对应一个结果，而NFA的依次输入可能对应多个结果，形成一个结果集，可以使用子集法将NFA构造为DFA

力扣

https://leetcode-cn.com/problems/string-to-integer-atoi/


class Solution {
    public int myAtoi(String s) {
        Automaton automaton = new Automaton();
        for (int i = 0; i < s.length(); i++) {
            automaton.process(s.charAt(i));
        }
        return (int) (automaton.sign * automaton.ans);
    }
}

class Automaton {
    // 表示数组的正负数, 如果碰到 - 则要变为 -1
    public int sign = 1;
    // 表示最终计算出来的数字
    public long ans = 0;
    // 表示当前状态
    private String state = "start";
    private Map<String, String[]> table = new HashMap<String, String[]>() {{
        // 0   1   2      3
        // ' ' +/- number other
        // 因为包含前导空格, 所以碰到空格要再次转为start状态
        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 process(char c) {
        // 根据当前状态获取碰到c字符之后的下个状态
        state = table.get(state)[getCol(c)];
        if ("in_number".equals(state)) {
            // - '0' 是因为直接ascii码计算
            ans = ans * 10 + c - '0';
            // 如果是正数, 防止溢出, 则直接取min
            // 如果是负数, 防止溢出, 则ans变负数取max然后转正数
            ans = sign == 1 ? Math.min(ans, Integer.MAX_VALUE) : -Math.max(-ans, Integer.MIN_VALUE);
        } else if ("signed".equals(state)) {
            sign = c == '+' ? 1 : -1;
        }
        // start和end不需要任何操作
    }

    // 根据字符获取状态index
    public int getCol(char c) {
        if (c == ' ') return 0;
        if (c == '+' || c == '-') return 1;
        if (Character.isDigit(c)) return 2;
        return 3;
    }
}