Java有限状态机解力扣题:8. 字符串转换整数 (atoi),代码实现及详细解析

Wesley13
• 阅读 841

文章目录


前言

在我重复刷力扣题:8. 字符串转换整数 (atoi) 时,发现了一个之前没发现的解法,就是确定有限状态机(DFA),此处对该解法做一个记录


一、确定有限状态机(DFA)是什么?

对于该题,就是逐字符读取题目给出的字符串,然后在当前状态下,读到该字符,应该转变为什么样子的状态,然后再通过该状态去进行相应的操作;
对于“有限”两字的理解,我的理解是,当前状态只会不断的朝着结束状态靠近,不会返回到上一级的状态,就是只会朝着可执行状态数量越来越少的方向靠近。

二、确定有限状态机(DFA)的作用

通过DFA,可以减少代码有过多的 if - else 条件判断语句(貌似这道题通过DFA并没有减少很多的 if - else语句,相反代码行数还挺多,应该是这道题的判断条件并不多,如果判断条件更加的多,更加的繁杂,通过DFA还是有相应的优化的);
使用DFA还可以增加代码的维护性,使代码更加容易修改和维护。

三、题目解析

对于该题,有四种状态,分别是:
start :读到空格时的状态
singed : 读到 - / + 号时的状态
in_number:读到数字时的状态
end:读到其他的字符时的状态

初始状态为start,作为该DFA的一个入口,可以列出下面这个状态表

‘ ’(空格)

+ / -

number(数字)

other(其他)

start

start

singed

number

other

singed

end

end

in_number

end

in_number

end

end

in_number

end

end

end

end

end

end

解释:(只举了其中一种可能的例子)
刚开始是start状态,如果刚开始读到的字符是空格,就对应的start的状态,不停的循环,直到读到非空格为止;
如果start的状态下读到了 + / - 号,那么就进入下一个状态singed状态,此状态下将读到的符号通过一个变量给存储下来。
根据题目的要求,符号的后面只能接数字,如果是非数字,那么这个字符串就无法转化为整数,直接返回0;所以,singed状态下如果读到了 空格、 符号、 其他字符,就直接跳转到结束状态,如果读到的是数字,那么就跳转到in_number状态,而in_number状态下和singed状态是一样的,只要读到非数字,就直接转到结束状态。

四、代码实现

class Solution {
   
   
   
    
    public int myAtoi(String str) {
   
   
   
        Automaton auto = new Automaton();
        char[] ch = str.toCharArray();
        
        for(char c : ch){
   
   
   
            //如果auto.calculate(c)是false,则终止循环
            if(!auto.calculate(c)) break;
        }
        return auto.sum;
    }
}
class Automaton{
   
   
   
    //设置确定有限状态机的状态
    final String START = "start";//开始状态
    final String SIGNED = "signed";//符号位状态
    final String IN_NUMBER = "in_number";//数字位状态
    final String END = "end";//结束状态

    String state = START;//设置初始状态,start
    int sum = 0;//记录字符转换为数字的结果
    int sign = 1;//记录符号
    
    //通过HashMap构建一个DFA表
    Map<String, String[]> table;
    public Automaton(){
   
   
   
        table = new HashMap<>();  
        table.put(START, new String[]{
   
   
   START, SIGNED, IN_NUMBER, END});
        table.put(SIGNED, new String[]{
   
   
   END, END, IN_NUMBER, END});
        table.put(IN_NUMBER, new String[]{
   
   
   END, END, IN_NUMBER, END});
        table.put(END, new String[]{
   
   
   END, END, END, END});
    }
    
    //用来获取该字符所对应的DFA表里的列
    public int getState(char c){
   
   
   
        if(c == ' ') return 0;
        if(c == '+' || c == '-') return 1;
        if(c >= '0' && c <= '9') return 2;
        return 3;
    }

    public boolean calculate(char c){
   
   
   
        //table.get(state)获取到DFA表里的行
        //getState(c)获取该字符在DFA表里的列
           //两者组合,获取到了一个确定的状态
        state = table.get(state)[getState(c)];
        
        if(END.equals(state)){
   
   
   //结束状态,返回false,传达终止信号
            return false;
        }else if(SIGNED.equals(state)){
   
   
   //符号位状态,记录当前符号
            sign = c == '-' ? -1 : 1;
        }else if(IN_NUMBER.equals(state)){
   
   
   //数字位状态
            int num = c - '0';//将char 转换为 int
            //此处题目要求,只能用int来存储数据类型,所以通过该方法判断sum是否越界
            //如果没越界
            if(sum >= (Integer.MIN_VALUE + num) / 10 && sum <= (Integer.MAX_VALUE - num) / 10){
   
   
   
                sum = sum * 10 + (sign * num);
            }else{
   
   
   //如果越界了
                sum = sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
                return false;
            }
        }
        return true;//传达继续判断信号
    }
}

总结

通过DFA解决该问题,在不新增状态的条件下,修改某些要求,大部分情况我们只需要修改上述代码构建的table表,而不需要去修改其他地方的代码

本文分享 CSDN - 弹弹霹雳。
如有侵权,请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。

点赞
收藏
评论区
推荐文章
blmius blmius
3年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
皕杰报表之UUID
​在我们用皕杰报表工具设计填报报表时,如何在新增行里自动增加id呢?能新增整数排序id吗?目前可以在新增行里自动增加id,但只能用uuid函数增加UUID编码,不能新增整数排序id。uuid函数说明:获取一个UUID,可以在填报表中用来创建数据ID语法:uuid()或uuid(sep)参数说明:sep布尔值,生成的uuid中是否包含分隔符'',缺省为
待兔 待兔
3个月前
手写Java HashMap源码
HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程22
Jacquelyn38 Jacquelyn38
3年前
2020年前端实用代码段,为你的工作保驾护航
有空的时候,自己总结了几个代码段,在开发中也经常使用,谢谢。1、使用解构获取json数据let jsonData  id: 1,status: "OK",data: 'a', 'b';let  id, status, data: number   jsonData;console.log(id, status, number )
Wesley13 Wesley13
3年前
mysql设置时区
mysql设置时区mysql\_query("SETtime\_zone'8:00'")ordie('时区设置失败,请联系管理员!');中国在东8区所以加8方法二:selectcount(user\_id)asdevice,CONVERT\_TZ(FROM\_UNIXTIME(reg\_time),'08:00','0
Wesley13 Wesley13
3年前
00:Java简单了解
浅谈Java之概述Java是SUN(StanfordUniversityNetwork),斯坦福大学网络公司)1995年推出的一门高级编程语言。Java是一种面向Internet的编程语言。随着Java技术在web方面的不断成熟,已经成为Web应用程序的首选开发语言。Java是简单易学,完全面向对象,安全可靠,与平台无关的编程语言。
Stella981 Stella981
3年前
Django中Admin中的一些参数配置
设置在列表中显示的字段,id为django模型默认的主键list_display('id','name','sex','profession','email','qq','phone','status','create_time')设置在列表可编辑字段list_editable
Stella981 Stella981
3年前
Docker 部署SpringBoot项目不香吗?
  公众号改版后文章乱序推荐,希望你可以点击上方“Java进阶架构师”,点击右上角,将我们设为★“星标”!这样才不会错过每日进阶架构文章呀。  !(http://dingyue.ws.126.net/2020/0920/b00fbfc7j00qgy5xy002kd200qo00hsg00it00cj.jpg)  2
Wesley13 Wesley13
3年前
MySQL部分从库上面因为大量的临时表tmp_table造成慢查询
背景描述Time:20190124T00:08:14.70572408:00User@Host:@Id:Schema:sentrymetaLast_errno:0Killed:0Query_time:0.315758Lock_
Python进阶者 Python进阶者
9个月前
Excel中这日期老是出来00:00:00,怎么用Pandas把这个去除
大家好,我是皮皮。一、前言前几天在Python白银交流群【上海新年人】问了一个Pandas数据筛选的问题。问题如下:这日期老是出来00:00:00,怎么把这个去除。二、实现过程后来【论草莓如何成为冻干莓】给了一个思路和代码如下:pd.toexcel之前把这