0
0

算法leetcode｜65. 有效数字（rust重拳出击）

文章目录

65. 有效数字：

有效数字（按顺序）可以分成以下几个部分：

  1. 一个 小数 或者 整数
  2. （可选）一个 'e' 或 'E' ，后面跟着一个 整数

小数（按顺序）可以分成以下几个部分：

  1. （可选）一个符号字符（'+' 或 '-'）
  2. 下述格式之一： 1. 至少一位数字，后面跟着一个点 '.'2. 至少一位数字，后面跟着一个点 '.' ，后面再跟着至少一位数字3. 一个点 '.' ，后面跟着至少一位数字

整数（按顺序）可以分成以下几个部分：

  1. （可选）一个符号字符（'+' 或 '-'）
  2. 至少一位数字

部分有效数字列举如下：

["2", "0089", "-0.1", "+3.14", "4.", "-.9", "2e10", "-90E3", "3e+7", "+6e-1", "53.5e93", "-123.456e789"]

部分无效数字列举如下：

["abc", "1a", "1e", "e3", "99e2.5", "--6", "-+3", "95a54e53"]

给你一个字符串 

s

，如果 

s

是一个 有效数字 ，请返回 

true

。

样例 1：

输入：
    
    s = "0"
    
输出：
    
    true

样例 2：

输入：
    
    s = "e"
    
输出：
    
    false

样例 3：

输入：
    
    s = "."
    
输出：
    
    false

提示：

  • 1 <= s.length <= 20
  • s 仅含英文字母（大写和小写），数字（0-9），加号 '+' ，减号 '-' ，或者点 '.' 。

分析：

  • 面对这道算法题目，二当家的再次陷入了沉思。
  • 二当家的觉得这道题和其他算法题不太一样，感觉这种判断是否有效的不太像算法。
  • 平时看到数字大脑是瞬间判断的。
  • 没想到写起程序却这么繁琐。
  • 在设计模式中有一种叫做状态模式，在这里可以借鉴。
  • 如果用一大堆分支逻辑判断，人是要疯掉的，但是用状态切换的方式，就非常的清晰。
  • 有效数字的状态是可预知而且有限的，有限状态机，对，就是叫这个。

题解：

rust：

implSolution{pubfnis_number(s:String)->bool{
        s.chars().try_fold(State::new(),State::handle).as_ref().map_or(false,State::is_valid)}}typeResult=std::result::Result<State,()>;enumState{Start,Sign,Integer,Dot,EmptyDot,Decimal,E,ExpSign,Exponent,End,}implState{pubfnnew()->Self{State::Start}pubfnis_valid(&self)->bool{useState::*;matchself{Start|Sign|E|ExpSign|EmptyDot=>false,
            _ =>true,}}pubfnhandle(self, c:char)->Result{useState::*;matchself{Start=>match c {' '=>Ok(Start),'+'|'-'=>Ok(Sign),'0'..='9'=>Ok(Integer),'.'=>Ok(EmptyDot),
                _ =>Err(()),}Sign=>match c {'0'..='9'=>Ok(Integer),'.'=>Ok(EmptyDot),
                _ =>Err(()),}Integer=>match c {'0'..='9'=>Ok(Integer),'.'=>Ok(Dot),'e'|'E'=>Ok(E),' '=>Ok(End),
                _ =>Err(()),}EmptyDot=>match c {'0'..='9'=>Ok(Decimal),// "  .1" or "  +.1"
                _ =>Err(()),}Dot=>match c {'0'..='9'=>Ok(Decimal),'e'|'E'=>Ok(E),// "46.e3"' '=>Ok(End),
                _ =>Err(()),}Decimal=>match c {'0'..='9'=>Ok(Decimal),'e'|'E'=>Ok(E),' '=>Ok(End),
                _ =>Err(()),}E=>match c {'+'|'-'=>Ok(ExpSign),'0'..='9'=>Ok(Exponent),
                _ =>Err(()),}ExpSign=>match c {'0'..='9'=>Ok(Exponent),
                _ =>Err(()),}Exponent=>match c {'0'..='9'=>Ok(Exponent),' '=>Ok(End),
                _ =>Err(()),}End=>match c {' '=>Ok(End),
                _ =>Err(()),}}}}

go：

type State inttype CharType intconst(
    STATE_INITIAL State =iota
    STATE_INT_SIGN
    STATE_INTEGER
    STATE_POINT
    STATE_POINT_WITHOUT_INT
    STATE_FRACTION
    STATE_EXP
    STATE_EXP_SIGN
    STATE_EXP_NUMBER
    STATE_END
)const(
    CHAR_NUMBER CharType =iota
    CHAR_EXP
    CHAR_POINT
    CHAR_SIGN
    CHAR_ILLEGAL
)functoCharType(ch byte) CharType {switch ch {case'0','1','2','3','4','5','6','7','8','9':return CHAR_NUMBER
    case'e','E':return CHAR_EXP
    case'.':return CHAR_POINT
    case'+','-':return CHAR_SIGN
    default:return CHAR_ILLEGAL
    }}funcisNumber(s string)bool{
    transfer :=map[State]map[CharType]State{
        STATE_INITIAL:map[CharType]State{
            CHAR_NUMBER: STATE_INTEGER,
            CHAR_POINT:  STATE_POINT_WITHOUT_INT,
            CHAR_SIGN:   STATE_INT_SIGN,},
        STATE_INT_SIGN:map[CharType]State{
            CHAR_NUMBER: STATE_INTEGER,
            CHAR_POINT:  STATE_POINT_WITHOUT_INT,},
        STATE_INTEGER:map[CharType]State{
            CHAR_NUMBER: STATE_INTEGER,
            CHAR_EXP:    STATE_EXP,
            CHAR_POINT:  STATE_POINT,},
        STATE_POINT:map[CharType]State{
            CHAR_NUMBER: STATE_FRACTION,
            CHAR_EXP:    STATE_EXP,},
        STATE_POINT_WITHOUT_INT:map[CharType]State{
            CHAR_NUMBER: STATE_FRACTION,},
        STATE_FRACTION:map[CharType]State{
            CHAR_NUMBER: STATE_FRACTION,
            CHAR_EXP:    STATE_EXP,},
        STATE_EXP:map[CharType]State{
            CHAR_NUMBER: STATE_EXP_NUMBER,
            CHAR_SIGN:   STATE_EXP_SIGN,},
        STATE_EXP_SIGN:map[CharType]State{
            CHAR_NUMBER: STATE_EXP_NUMBER,},
        STATE_EXP_NUMBER:map[CharType]State{
            CHAR_NUMBER: STATE_EXP_NUMBER,},}
    state := STATE_INITIAL
    for i :=0; i <len(s); i++{
        typ :=toCharType(s[i])if_, ok := transfer[state][typ];!ok {returnfalse}else{
            state = transfer[state][typ]}}return state == STATE_INTEGER || state == STATE_POINT || state == STATE_FRACTION || state == STATE_EXP_NUMBER || state == STATE_END
}

c++：

classSolution{public:enumState{
        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
    };enumCharType{
        CHAR_NUMBER,
        CHAR_EXP,
        CHAR_POINT,
        CHAR_SIGN,
        CHAR_ILLEGAL
    };

    CharType toCharType(char ch){if(ch >='0'&& ch <='9'){return CHAR_NUMBER;}elseif(ch =='e'|| ch =='E'){return CHAR_EXP;}elseif(ch =='.'){return CHAR_POINT;}elseif(ch =='+'|| ch =='-'){return CHAR_SIGN;}else{return CHAR_ILLEGAL;}}boolisNumber(string s){
        unordered_map<State, unordered_map<CharType, State>> transfer{{
                STATE_INITIAL,{{CHAR_NUMBER, STATE_INTEGER},{CHAR_POINT, STATE_POINT_WITHOUT_INT},{CHAR_SIGN, STATE_INT_SIGN}}},{
                STATE_INT_SIGN,{{CHAR_NUMBER, STATE_INTEGER},{CHAR_POINT, STATE_POINT_WITHOUT_INT}}},{
                STATE_INTEGER,{{CHAR_NUMBER, STATE_INTEGER},{CHAR_EXP, STATE_EXP},{CHAR_POINT, STATE_POINT}}},{
                STATE_POINT,{{CHAR_NUMBER, STATE_FRACTION},{CHAR_EXP, STATE_EXP}}},{
                STATE_POINT_WITHOUT_INT,{{CHAR_NUMBER, STATE_FRACTION}}},{
                STATE_FRACTION,{{CHAR_NUMBER, STATE_FRACTION},{CHAR_EXP, STATE_EXP}}},{
                STATE_EXP,{{CHAR_NUMBER, STATE_EXP_NUMBER},{CHAR_SIGN, STATE_EXP_SIGN}}},{
                STATE_EXP_SIGN,{{CHAR_NUMBER, STATE_EXP_NUMBER}}},{
                STATE_EXP_NUMBER,{{CHAR_NUMBER, STATE_EXP_NUMBER}}}};int len = s.length();
        State st = STATE_INITIAL;for(int i =0; i < len; i++){
            CharType typ =toCharType(s[i]);if(transfer[st].find(typ)== transfer[st].end()){returnfalse;}else{
                st = transfer[st][typ];}}return st == STATE_INTEGER || st == STATE_POINT || st == STATE_FRACTION || st == STATE_EXP_NUMBER || st == STATE_END;}};

python：

from enum import Enum

classSolution:defisNumber(self, s:str)->bool:
        State = 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"])
        Chartype = Enum("Chartype",["CHAR_NUMBER","CHAR_EXP","CHAR_POINT","CHAR_SIGN","CHAR_ILLEGAL"])deftoChartype(ch:str)-> Chartype:if ch.isdigit():return Chartype.CHAR_NUMBER
            elif ch.lower()=="e":return Chartype.CHAR_EXP
            elif ch ==".":return Chartype.CHAR_POINT
            elif ch =="+"or ch =="-":return Chartype.CHAR_SIGN
            else:return Chartype.CHAR_ILLEGAL
        
        transfer ={
            State.STATE_INITIAL:{
                Chartype.CHAR_NUMBER: State.STATE_INTEGER,
                Chartype.CHAR_POINT: State.STATE_POINT_WITHOUT_INT,
                Chartype.CHAR_SIGN: State.STATE_INT_SIGN
            },
            State.STATE_INT_SIGN:{
                Chartype.CHAR_NUMBER: State.STATE_INTEGER,
                Chartype.CHAR_POINT: State.STATE_POINT_WITHOUT_INT
            },
            State.STATE_INTEGER:{
                Chartype.CHAR_NUMBER: State.STATE_INTEGER,
                Chartype.CHAR_EXP: State.STATE_EXP,
                Chartype.CHAR_POINT: State.STATE_POINT
            },
            State.STATE_POINT:{
                Chartype.CHAR_NUMBER: State.STATE_FRACTION,
                Chartype.CHAR_EXP: State.STATE_EXP
            },
            State.STATE_POINT_WITHOUT_INT:{
                Chartype.CHAR_NUMBER: State.STATE_FRACTION
            },
            State.STATE_FRACTION:{
                Chartype.CHAR_NUMBER: State.STATE_FRACTION,
                Chartype.CHAR_EXP: State.STATE_EXP
            },
            State.STATE_EXP:{
                Chartype.CHAR_NUMBER: State.STATE_EXP_NUMBER,
                Chartype.CHAR_SIGN: State.STATE_EXP_SIGN
            },
            State.STATE_EXP_SIGN:{
                Chartype.CHAR_NUMBER: State.STATE_EXP_NUMBER
            },
            State.STATE_EXP_NUMBER:{
                Chartype.CHAR_NUMBER: State.STATE_EXP_NUMBER
            },}

        st = State.STATE_INITIAL
        for ch in s:
            typ = toChartype(ch)if typ notin transfer[st]:returnFalse
            st = transfer[st][typ]return st in[State.STATE_INTEGER, State.STATE_POINT, State.STATE_FRACTION, State.STATE_EXP_NUMBER, State.STATE_END]

java：

classSolution{publicbooleanisNumber(String s){Map<State,Map<CharType,State>> transfer =newHashMap<State,Map<CharType,State>>();Map<CharType,State> initialMap =newHashMap<CharType,State>(){{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<CharType,State> intSignMap =newHashMap<CharType,State>(){{put(CharType.CHAR_NUMBER,State.STATE_INTEGER);put(CharType.CHAR_POINT,State.STATE_POINT_WITHOUT_INT);}};
        transfer.put(State.STATE_INT_SIGN, intSignMap);Map<CharType,State> integerMap =newHashMap<CharType,State>(){{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<CharType,State> pointMap =newHashMap<CharType,State>(){{put(CharType.CHAR_NUMBER,State.STATE_FRACTION);put(CharType.CHAR_EXP,State.STATE_EXP);}};
        transfer.put(State.STATE_POINT, pointMap);Map<CharType,State> pointWithoutIntMap =newHashMap<CharType,State>(){{put(CharType.CHAR_NUMBER,State.STATE_FRACTION);}};
        transfer.put(State.STATE_POINT_WITHOUT_INT, pointWithoutIntMap);Map<CharType,State> fractionMap =newHashMap<CharType,State>(){{put(CharType.CHAR_NUMBER,State.STATE_FRACTION);put(CharType.CHAR_EXP,State.STATE_EXP);}};
        transfer.put(State.STATE_FRACTION, fractionMap);Map<CharType,State> expMap =newHashMap<CharType,State>(){{put(CharType.CHAR_NUMBER,State.STATE_EXP_NUMBER);put(CharType.CHAR_SIGN,State.STATE_EXP_SIGN);}};
        transfer.put(State.STATE_EXP, expMap);Map<CharType,State> expSignMap =newHashMap<CharType,State>(){{put(CharType.CHAR_NUMBER,State.STATE_EXP_NUMBER);}};
        transfer.put(State.STATE_EXP_SIGN, expSignMap);Map<CharType,State> expNumberMap =newHashMap<CharType,State>(){{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)){returnfalse;}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;}publicCharTypetoCharType(char ch){if(ch >='0'&& ch <='9'){returnCharType.CHAR_NUMBER;}elseif(ch =='e'|| ch =='E'){returnCharType.CHAR_EXP;}elseif(ch =='.'){returnCharType.CHAR_POINT;}elseif(ch =='+'|| ch =='-'){returnCharType.CHAR_SIGN;}else{returnCharType.CHAR_ILLEGAL;}}enumState{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}enumCharType{CHAR_NUMBER,CHAR_EXP,CHAR_POINT,CHAR_SIGN,CHAR_ILLEGAL}}

非常感谢你阅读本文~
欢迎【点赞】【收藏】【评论】三连走一波~
放弃不难，但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子：https://le-yi.blog.csdn.net/ 博客原创~

标签： rust golang 数据结构
本文转载自: https://blog.csdn.net/leyi520/article/details/131974927
版权归原作者 二当家的白帽子 所有， 如有侵权，请联系我们删除。
登录后发布评论

“算法leetcode｜65. 有效数字（rust重拳出击）”的评论:

还没有评论
关于作者
...
overfit同步小助手
文章同步
相关阅读

Android开发，使用TabLayout+ViewPager2实现校园健康安全宣传

网络测试工具集推荐

Mac M1芯片安装Homebrew

在VScode运行C++

如何合并 Git 提交到上一次提交

毕设开源 python大数据旅游数据分析可视化系统(源码分享)

Spark之RDD,常用的分析算子大全 分组聚合,排序,重分区,连接合并等算子

文章导航