leetcode 65题——有效数字_自动机解_java实现
2021/5/9 1:25:50
本文主要是介绍leetcode 65题——有效数字_自动机解_java实现,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
leetcode 65题——有效数字_自动机解_java实现
//20210508
写在前面:今天刷leetcode刷到的题目,一开始用暴力写逻辑,漏洞百出,遂放弃,去看题解,发现使用自动机做(编译原理知识),实现之后觉得挺有意思(确实也是我不会的东西),所以在这里记录一下
自动机逻辑:
-
将系统中可能出现的状态列出来,并把从一个状态到另一个状态是否能够转移标记出来,最后生成一个二维状态数组,循环的时候使用数组状态转移,在状态为-1的时候返回false,如果循环之后没有返回,则判断最后的状态是否为状态图中可以为终态的状态结点,如果是,则返回true,否则返回false
-
图解如下(比较潦草,看不懂可留言~):
-
二维数组如下:
题目描述
程序源代码
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实现的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-04TiDB 资源管控的对撞测试以及最佳实践架构
- 2024-07-03万字长文聊聊Web3的组成架构
- 2024-07-02springboot项目无法注册到nacos-icode9专业技术文章分享
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现