文章目录
- 65. 有效数字:
- 样例 1:
- 样例 2:
- 样例 3:
- 提示:
- 分析:
- 题解:
- rust:
- go:
- c++:
- python:
- java:
65. 有效数字:
有效数字(按顺序)可以分成以下几个部分:
- 一个 小数 或者 整数
- (可选)一个
'e'
或'E'
,后面跟着一个 整数
小数(按顺序)可以分成以下几个部分:
- (可选)一个符号字符(
'+'
或'-'
) - 下述格式之一:
- 至少一位数字,后面跟着一个点
'.'
- 至少一位数字,后面跟着一个点
'.'
,后面再跟着至少一位数字 - 一个点
'.'
,后面跟着至少一位数字
- 至少一位数字,后面跟着一个点
整数(按顺序)可以分成以下几个部分:
- (可选)一个符号字符(
'+'
或'-'
) - 至少一位数字
部分有效数字列举如下:["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:
impl Solution {pub fn is_number(s: String) -> bool {s.chars().try_fold(State::new(), State::handle).as_ref().map_or(false, State::is_valid)}
}type Result = std::result::Result<State, ()>;enum State {Start,Sign,Integer,Dot,EmptyDot,Decimal,E,ExpSign,Exponent,End,
}impl State {pub fn new() -> Self {State::Start}pub fn is_valid(&self) -> bool {use State::*;match self {Start | Sign | E | ExpSign | EmptyDot => false,_ => true,}}pub fn handle(self, c: char) -> Result {use State::*;match self {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 int
type CharType intconst (STATE_INITIAL State = iotaSTATE_INT_SIGNSTATE_INTEGERSTATE_POINTSTATE_POINT_WITHOUT_INTSTATE_FRACTIONSTATE_EXPSTATE_EXP_SIGNSTATE_EXP_NUMBERSTATE_END
)const (CHAR_NUMBER CharType = iotaCHAR_EXPCHAR_POINTCHAR_SIGNCHAR_ILLEGAL
)func toCharType(ch byte) CharType {switch ch {case '0', '1', '2', '3', '4', '5', '6', '7', '8', '9':return CHAR_NUMBERcase 'e', 'E':return CHAR_EXPcase '.':return CHAR_POINTcase '+', '-':return CHAR_SIGNdefault:return CHAR_ILLEGAL}
}func isNumber(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_INITIALfor i := 0; i < len(s); i++ {typ := toCharType(s[i])if _, ok := transfer[state][typ]; !ok {return false} else {state = transfer[state][typ]}}return state == STATE_INTEGER || state == STATE_POINT || state == STATE_FRACTION || state == STATE_EXP_NUMBER || state == STATE_END
}
c++:
class Solution {
public: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};CharType toCharType(char ch) {if (ch >= '0' && ch <= '9') {return CHAR_NUMBER;} else if (ch == 'e' || ch == 'E') {return CHAR_EXP;} else if (ch == '.') {return CHAR_POINT;} else if (ch == '+' || ch == '-') {return CHAR_SIGN;} else {return CHAR_ILLEGAL;}}bool isNumber(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()) {return false;} 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 Enumclass Solution:def isNumber(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"])def toChartype(ch: str) -> Chartype:if ch.isdigit():return Chartype.CHAR_NUMBERelif ch.lower() == "e":return Chartype.CHAR_EXPelif ch == ".":return Chartype.CHAR_POINTelif ch == "+" or ch == "-":return Chartype.CHAR_SIGNelse:return Chartype.CHAR_ILLEGALtransfer = {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_INITIALfor ch in s:typ = toChartype(ch)if typ not in transfer[st]:return Falsest = transfer[st][typ]return st in [State.STATE_INTEGER, State.STATE_POINT, State.STATE_FRACTION, State.STATE_EXP_NUMBER, State.STATE_END]
java:
class Solution {public boolean isNumber(String s) {Map<State, Map<CharType, State>> transfer = new HashMap<State, Map<CharType, State>>();Map<CharType, State> initialMap = new HashMap<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 = new HashMap<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 = new HashMap<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 = new HashMap<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 = new HashMap<CharType, State>() {{put(CharType.CHAR_NUMBER, State.STATE_FRACTION);}};transfer.put(State.STATE_POINT_WITHOUT_INT, pointWithoutIntMap);Map<CharType, State> fractionMap = new HashMap<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 = new HashMap<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 = new HashMap<CharType, State>() {{put(CharType.CHAR_NUMBER, State.STATE_EXP_NUMBER);}};transfer.put(State.STATE_EXP_SIGN, expSignMap);Map<CharType, State> expNumberMap = new HashMap<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)) {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}
}
非常感谢你阅读本文~
欢迎【点赞】【收藏】【评论】三连走一波~
放弃不难,但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子:https://le-yi.blog.csdn.net/ 博客原创~