剑指 Offer 20. 表示数值的字符串
请实现一个函数用来判断字符串是否表示数值(包括整数和小数)。
数值(按顺序)可以分成以下几个部分:
- 若干空格
- 一个 小数 或者 整数
- (可选)一个
'e'
或'E'
,后面跟着一个 整数 - 若干空格
小数(按顺序)可以分成以下几个部分:
- (可选)一个符号字符(
'+'
或'-'
) - 下述格式之一:
- 至少一位数字,后面跟着一个点
'.'
- 至少一位数字,后面跟着一个点
'.'
,后面再跟着至少一位数字 - 一个点
'.'
,后面跟着至少一位数字
- 至少一位数字,后面跟着一个点
整数(按顺序)可以分成以下几个部分:
- (可选)一个符号字符(
'+'
或'-'
) - 至少一位数字
部分数值列举如下:
["+100", "5e2", "-123", "3.1416", "-1E-16", "0123"]
部分非数值列举如下:
["12e", "1a3.14", "1.2.3", "+-5", "12e+5.4"]
示例 1:
输入:s = "0" 输出:true
示例 2:
输入:s = "e" 输出:false
示例 3:
输入:s = "." 输出:false
示例 4:
输入:s = " .1 " 输出:true
提示:
1 <= s.length <= 20
s
仅含英文字母(大写和小写),数字(0-9
),加号'+'
,减号'-'
,空格' '
或者点'.'
。
本题链接:剑指 Offer 20. 表示数值的字符串 - 力扣(LeetCode)
此题我第一次使用暴力方法:
1 class Solution { 2 public: 3 bool isNumber(string s) { 4 int sl=s.length(); 5 int p=0; 6 while(p<sl&&s[p]==' ')p++; 7 if(p<sl&&(s[p]=='+'||s[p]=='-'))p++; 8 if(p<sl&&(s[p]>='0'&&s[p]<='9')){ 9 while(p<sl&&(s[p]>='0'&&s[p]<='9'))p++; 10 int ttp=p; 11 while(ttp<sl&&(s[ttp]==' '))ttp++; 12 if(ttp>=sl)return true; 13 if(p<sl&&s[p]=='.'){ 14 if(p>=sl-1)return true; 15 p++; 16 int tp=p; 17 while(p<sl&&(s[p]>='0'&&s[p]<='9'))p++; 18 int tttp=p; 19 while(tttp<sl&&(s[tttp]==' '))tttp++; 20 if(p>=sl||tttp>=sl)return true; 21 while(tp<sl&&(s[tp]==' '))tp++; 22 if(tp>=sl)return true; 23 } 24 if(p<sl&&(s[p]=='E'||s[p]=='e')){ 25 if(p<sl-1)p++; 26 if(p<sl&&(s[p]=='+'||s[p]=='-'))p++; 27 if(p<sl&&(s[p]>='0'&&s[p]<='9')){ 28 while(p<sl&&(s[p]>='0'&&s[p]<='9'))p++; 29 while(p<sl&&(s[p]==' '))p++; 30 if(p>=sl)return true; 31 } 32 } 33 }else{ 34 if(p<sl&&s[p]=='.'){ 35 if(p<sl-1)p++; 36 if(p<sl&&(s[p]>='0'&&s[p]<='9')){ 37 while(p<sl&&(s[p]>='0'&&s[p]<='9'))p++; 38 if(p<sl&&(s[p]=='E'||s[p]=='e')){ 39 if(p<sl-1)p++; 40 if(p<sl&&(s[p]=='+'||s[p]=='-'))p++; 41 if(p<sl&&(s[p]>='0'&&s[p]<='9')){ 42 while(p<sl&&(s[p]>='0'&&s[p]<='9'))p++; 43 while(p<sl&&(s[p]==' '))p++; 44 if(p>=sl)return true; 45 } 46 } 47 while(p<sl&&(s[p]==' '))p++; 48 } 49 if(p>=sl)return true; 50 } 51 } 52 return false; 53 } 54 };
第二次学习了enum枚举和有限状态自动机的概念,结合官方题解,重新做了一遍,代码如下:
1 class Solution { 2 public: 3 enum state{ 4 start, 5 sign, 6 num, 7 dot, 8 dotWithoutNum, 9 decimal, 10 exp, 11 expSign, 12 expNum, 13 end, 14 defeat 15 }; 16 enum CharType{ 17 space, 18 pm, 19 in, 20 e, 21 d, 22 theElse 23 }; 24 CharType judge(char c){ 25 if(c>='0'&&c<='9')return in; 26 if(c==' ')return space; 27 if(c=='e'||c=='E')return e; 28 if(c=='.')return d; 29 if(c=='+'||c=='-')return pm; 30 return theElse; 31 } 32 bool isNumber(string s) { 33 unordered_map<state,unordered_map<CharType,state>>m{ 34 {start,{ 35 {space,start}, 36 {pm,sign}, 37 {in,num}, 38 {e,defeat}, 39 {d,dotWithoutNum}, 40 {theElse,defeat} 41 }}, 42 {sign,{ 43 {space,defeat}, 44 {pm,defeat}, 45 {in,num}, 46 {e,defeat}, 47 {d,dotWithoutNum}, 48 {theElse,defeat} 49 }}, 50 {num,{ 51 {space,end}, 52 {pm,defeat}, 53 {in,num}, 54 {e,exp}, 55 {d,dot}, 56 {theElse,defeat} 57 }}, 58 {dot,{ 59 {space,end}, 60 {pm,defeat}, 61 {in,decimal}, 62 {e,exp}, 63 {d,defeat}, 64 {theElse,defeat} 65 }}, 66 {dotWithoutNum,{ 67 {space,defeat}, 68 {pm,defeat}, 69 {in,decimal}, 70 {e,defeat}, 71 {d,defeat}, 72 {theElse,defeat} 73 }}, 74 {decimal,{ 75 {space,end}, 76 {pm,defeat}, 77 {in,decimal}, 78 {e,exp}, 79 {d,defeat}, 80 {theElse,defeat} 81 }}, 82 {exp,{ 83 {space,defeat}, 84 {pm,expSign}, 85 {in,expNum}, 86 {e,defeat}, 87 {d,defeat}, 88 {theElse,defeat} 89 }}, 90 {expSign,{ 91 {space,defeat}, 92 {pm,defeat}, 93 {in,expNum}, 94 {e,defeat}, 95 {d,defeat}, 96 {theElse,defeat} 97 }}, 98 {expNum,{ 99 {space,end}, 100 {pm,defeat}, 101 {in,expNum}, 102 {e,defeat}, 103 {d,defeat}, 104 {theElse,defeat} 105 }}, 106 {end,{ 107 {space,end}, 108 {pm,defeat}, 109 {in,defeat}, 110 {e,defeat}, 111 {d,defeat}, 112 {theElse,defeat} 113 }}, 114 {defeat,{ 115 {space,defeat}, 116 {pm,defeat}, 117 {in,defeat}, 118 {e,defeat}, 119 {d,defeat}, 120 {theElse,defeat} 121 }}, 122 }; 123 int sl=s.length(); 124 state st=start; 125 CharType ct; 126 for(int i=0;i<sl;++i){ 127 ct=judge(s[i]); 128 st=m[st][ct]; 129 //if(st==defeat)return false; 130 } 131 if(st==end||st==num||st==decimal||st==dot||st==expNum)return true; 132 return false; 133 } 134 };标签:theElse,20,sl,Offer,space,&&,defeat,自动机,pm From: https://www.cnblogs.com/vusblog/p/17155296.html