Java教程

leetcode 65题——有效数字_自动机解_java实现

本文主要是介绍leetcode 65题——有效数字_自动机解_java实现,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

leetcode 65题——有效数字_自动机解_java实现

//20210508
写在前面:今天刷leetcode刷到的题目,一开始用暴力写逻辑,漏洞百出,遂放弃,去看题解,发现使用自动机做(编译原理知识),实现之后觉得挺有意思(确实也是我不会的东西),所以在这里记录一下

自动机逻辑:

  • 将系统中可能出现的状态列出来,并把从一个状态到另一个状态是否能够转移标记出来,最后生成一个二维状态数组,循环的时候使用数组状态转移,在状态为-1的时候返回false,如果循环之后没有返回,则判断最后的状态是否为状态图中可以为终态的状态结点,如果是,则返回true,否则返回false

  • 图解如下(比较潦草,看不懂可留言~):

  • 二维数组如下:

题目描述

  • image

程序源代码

package algorithm;

public class IsNumber {
    public static int make(char s){
        switch (s){
            case ' ':return 0;
            case '+':
            case '-':return 1;
            case '.':return 3;
            case 'E':
            case 'e':return 4;
            default:
                if(s>='0'&&s<='9')return 2;
        }
        return -1;//其他情况
    }

    //自动机
    public static boolean isNumber(String s) {
        char[] sArr = s.toCharArray();
        int[][] global_state = {
                {0,1,6,2,-1,-1},
                {-1,-1,6,2,-1,-1},
                {-1,-1,3,-1,-1,-1},
                {8,-1,3,-1,4,-1},
                {-1,7,5,-1,-1,-1},
                {8,-1,5,-1,-1,-1},
                {8,-1,6,3,4,-1},
                {-1,-1,5,-1,-1,-1},
                {8,-1,-1,-1,-1,-1}
        };
        int state = 0;
        for(int i = 0;i<sArr.length;++i){
            int temp = make(sArr[i]);
            if(temp==-1)return false;
            state = global_state[state][temp];
            if(state==-1) return false;
        }
        if(state==8||state==6||state==3||state==5) return true;
        return false;
    }

    public static void main(String[] args) {
        System.out.println(isNumber("0"));
    }
}

leetcode通过截图

这篇关于leetcode 65题——有效数字_自动机解_java实现的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!