Java数据结构与算法——有限状态机（DFA）-白红宇

Java数据结构与算法——有限状态机（DFA）

阅读量：3944 次

发布时间：2019-05-24

本文共 8464 字，大约阅读时间需要 28 分钟。

在编程的时候，经常需要根据一个当前状态和各种可能的输入来实现不同的逻辑以及维护状态的变化，一般用大量if…else或者switch…case来遍历实现，这其实就涵盖了状态机的思想。题目具有很多逻辑判断，为了减少代码冗余，可用枚举或Map约束好状态，通过状态转移实现逻辑判断。

在计算理论中，确定有限状态自动机或确定有限自动机（英语：deterministic finite automaton, DFA）是一个能实现状态转移的自动机。对于一个给定的属于该自动机的状态和一个属于该自动机字母表Σ的字符，它都能根据事先给定的转移函数转移到下一个状态，以此到达最终状态。

力扣官网解释：

确定有限状态自动机（以下简称「自动机」）是一类计算模型。它包含一系列状态，这些状态中：

有一个特殊的状态，被称作「初始状态」。

还有一系列状态被称为「接受状态」，它们组成了一个特殊的集合。其中，一个状态可能既是「初始状态」，也是「接受状态」。

起初，这个自动机处于「初始状态」。随后，它顺序地读取字符串中的每一个字符，并根据当前状态和读入的字符，按照某个事先约定好的「转移规则」，从当前状态转移到下一个状态；当状态转移完成后，它就读取下一个字符。当字符串全部读取完毕后，如果自动机处于某个「接受状态」，则判定该字符串「被接受」；否则，判定该字符串「被拒绝」。

自动机在计算机科学领域有着广泛的应用。在算法领域，它与大名鼎鼎的字符串查找算法「KMP」算法有着密切的关联；在工程领域，它是实现「正则表达式」的基础。

相关题目：

leetcode-8 字符串转换整数 (atoi)

力扣题解：

状态图：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-QveH9OFf-1618888237226)(./images/91.jpg)]

	‘’	±	number	other
start	start	signed	in_number	end
signed	end	end	in_number	end
in_number	end	end	in_number	end
end	end	end	end	end

import java.util.HashMap;import java.util.Map;/** * Title：leetcode-8. 字符串转换整数 (atoi) * Description：有限状态机（DFA） * @author WZQ * @version 1.0.0 * @date 2021/4/19 */public class Main08 {
       public int myAtoi(String str) {
           DFA dfa = new DFA();        int length = str.length();        for (int i = 0; i < length; ++i) {
               dfa.get(str.charAt(i));        }        // ans*符号位        return (int) (dfa.sign * dfa.ans);    }    // 有限自动机    class DFA {
           // 符号位，默认无符号为正，相乘，1正-1负        public int sign = 1;        // 正数值        public long ans = 0;        private String state = "start";        // 状态表        private Map
   
     table = new HashMap
    
     () {
   {
               // 起始            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)[getCol(c)];            if ("in_number".equals(state)) {
                   // 位运算，减去0的ASCLL值                ans = ans * 10 + c - '0';                // ans保留为正，外部*sign                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 getCol(char c) {
               if (c == ' ') {
                   return 0;            }            if (c == '+' || c == '-') {
                   return 1;            }            // 数字            if (Character.isDigit(c)) {
                   return 2;            }            return 3;        }    }}

leetcode-393. UTF-8 编码验证

力扣题解：

import java.util.HashMap;import java.util.Map;/** * Title：leetcode-393. UTF-8 编码验证 * Description：有限状态机（DFA） * * @author WZQ * @version 1.0.0 * @date 2021/4/19 */public class Main393 {
       public boolean validUtf8(int[] data) {
           int cur = 0;        for (int input : data) {
               Integer next = DFA.getNext(cur, input);            // 无状态false            if (next == null) {
                   return false;            }            cur = next;        }        // 0正常结束状态        return cur == 0;    }    // 有限自动机    static class DFA {
           // 自动机状态 0b二进制        static final int TYPE_0 = 0b00000000;        static final int TYPE_1 = 0b10000000;        static final int TYPE_2 = 0b11000000;        static final int TYPE_3 = 0b11100000;        static final int TYPE_4 = 0b11110000;        /**         * 判断字节段的格式， &运算         * 0xxxxxxx格式判断首位即可（0），10000000         * 10xxxxxx格式判断前2位即可（10），11000000         * 110xxxxx格式判断前3位即可（110），11100000         * 1110xxxx格式判断前4位即可（1110），11110000         * 11110xxx格式判断前5位即可（11110），11111000         */        static final int[] MASKS = new int[]{
   0b10000000, 0b11000000, 0b11100000, 0b11110000, 0b11111000};        // 所有字节段        static final int[] TYPES = new int[]{
   TYPE_0, TYPE_1, TYPE_2, TYPE_3, TYPE_4};        // 状态表        static final Map
   
    > DFA = new HashMap<>();        // Map.of--JDK9        static {
               // 起始1-4字节,0是起始也是结束状态            DFA.put(0, Map.of(TYPE_0, 0, TYPE_2, 1, TYPE_3, 2, TYPE_4, 3));            // 2字节，1次后字节TYPE_1-->10000000            DFA.put(1, Map.of(TYPE_1, 0));            // 3字节，2次后字节TYPE_1-->10000000            DFA.put(2, Map.of(TYPE_1, 4));            DFA.put(4, Map.of(TYPE_1, 0));            // 4字节，3次后字节TYPE_1-->10000000            DFA.put(3, Map.of(TYPE_1, 5));            DFA.put(5, Map.of(TYPE_1, 6));            DFA.put(6, Map.of(TYPE_1, 0));        }        /**         * 验证字节段         * @param in 字节段         * @return         */        private static int getType(int in) {
               for (int i = 0; i < TYPES.length; i++) {
                   // in是十进制，二进制&运算判断题目字节段格式                if ((MASKS[i] & in) == TYPES[i]) {
                       return TYPES[i];                }            }            // 不符合的字节字段            return -1;        }        /**         * 状态获取         * @param cur   第几个字节         * @param input 字节段         * @return         */        private static Integer getNext(int cur, int input) {
               int type = getType(input);            if (type == -1) {
                   return null;            }            // 状态跳转            return DFA.get(cur).get(type);        }    }}

leetcode-65. 有效数字

力扣题解：

import java.util.HashMap;import java.util.Map;/** * Title：leetcode-65. 有效数字 * Description：有限状态机（DFA） * * @author WZQ * @version 1.0.0 * @date 2021/4/19 */public class Main65 {
       public boolean isNumber(String s) {
           Map
   
    > transfer = new HashMap
    
     >();        Map
     
       initialMap = new HashMap
      
       () {
   {
               put(CharType.CHAR_NUMBER, State.STATE_INTEGER);            put(CharType.CHAR_POINT, State.STATE_POINT_WITHOUT_INT);            put(CharType.CHAR_SIGN, State.STATE_INT_SIGN);        }};        transfer.put(State.STATE_INITIAL, initialMap);        Map
       
         intSignMap = new HashMap
        
         () { { put(CharType.CHAR_NUMBER, State.STATE_INTEGER); put(CharType.CHAR_POINT, State.STATE_POINT_WITHOUT_INT); }}; transfer.put(State.STATE_INT_SIGN, intSignMap); Map
         
           integerMap = new HashMap
          
           () { { put(CharType.CHAR_NUMBER, State.STATE_INTEGER); put(CharType.CHAR_EXP, State.STATE_EXP); put(CharType.CHAR_POINT, State.STATE_POINT); }}; transfer.put(State.STATE_INTEGER, integerMap); Map
           
             pointMap = new HashMap
            
             () { { put(CharType.CHAR_NUMBER, State.STATE_FRACTION); put(CharType.CHAR_EXP, State.STATE_EXP); }}; transfer.put(State.STATE_POINT, pointMap); Map
             
               pointWithoutIntMap = new HashMap
              
               () { { put(CharType.CHAR_NUMBER, State.STATE_FRACTION); }}; transfer.put(State.STATE_POINT_WITHOUT_INT, pointWithoutIntMap); Map
               
                 fractionMap = new HashMap
                
                 () { { put(CharType.CHAR_NUMBER, State.STATE_FRACTION); put(CharType.CHAR_EXP, State.STATE_EXP); }}; transfer.put(State.STATE_FRACTION, fractionMap); Map
                 
                   expMap = new HashMap
                  
                   () { { put(CharType.CHAR_NUMBER, State.STATE_EXP_NUMBER); put(CharType.CHAR_SIGN, State.STATE_EXP_SIGN); }}; transfer.put(State.STATE_EXP, expMap); Map
                   
                     expSignMap = new HashMap
                    
                     () { { put(CharType.CHAR_NUMBER, State.STATE_EXP_NUMBER); }}; transfer.put(State.STATE_EXP_SIGN, expSignMap); Map
                     
                       expNumberMap = new HashMap
                      
                       () { { put(CharType.CHAR_NUMBER, State.STATE_EXP_NUMBER); }}; transfer.put(State.STATE_EXP_NUMBER, expNumberMap); int length = s.length(); State state = State.STATE_INITIAL; for (int i = 0; i < length; i++) { CharType type = toCharType(s.charAt(i)); if (!transfer.get(state).containsKey(type)) { return false; } else { state = transfer.get(state).get(type); } } return state == State.STATE_INTEGER || state == State.STATE_POINT || state == State.STATE_FRACTION || state == State.STATE_EXP_NUMBER || state == State.STATE_END; } public CharType toCharType(char ch) { if (ch >= '0' && ch <= '9') { return CharType.CHAR_NUMBER; } else if (ch == 'e' || ch == 'E') { return CharType.CHAR_EXP; } else if (ch == '.') { return CharType.CHAR_POINT; } else if (ch == '+' || ch == '-') { return CharType.CHAR_SIGN; } else { return CharType.CHAR_ILLEGAL; } } enum State { STATE_INITIAL, STATE_INT_SIGN, STATE_INTEGER, STATE_POINT, STATE_POINT_WITHOUT_INT, STATE_FRACTION, STATE_EXP, STATE_EXP_SIGN, STATE_EXP_NUMBER, STATE_END, } enum CharType { CHAR_NUMBER, CHAR_EXP, CHAR_POINT, CHAR_SIGN, CHAR_ILLEGAL, }}

转载地址：http://rviwi.baihongyu.com/

你可能感兴趣的文章