剑指offer-53、表达数值的字符串
<h2 id="题描述">题⽬描述</h2><p>请实现⼀个函数⽤来判断字符串str是否表示数值（包括科学计数法的数字，⼩数和整数）。科学计数法的数字(按顺序）可以分成以下⼏个部分:</p>
<ol>
<li>若⼲空格</li>
<li>⼀个整数或者⼩数</li>
<li>（可选）⼀个 ' e ' 或 ' E ' ，后⾯跟着⼀个整数(可正可负)</li>
<li>若⼲空格</li>
</ol>
<p>⼩数（按顺序）可以分成以下⼏个部分：</p>
<ol>
<li>若⼲空格</li>
<li>（可选）⼀个符号字符（'+' 或 '-'）</li>
<li>可能是以下描述格式之⼀:
<ol>
<li>⾄少⼀位数字，后⾯跟着⼀个点 '.'</li>
<li>⾄少⼀位数字，后⾯跟着⼀个点 '.' ，后⾯再跟着⾄少⼀位数字</li>
<li>⼀个点 '.' ，后⾯跟着⾄少⼀位数字</li>
</ol>
</li>
<li>若⼲空格</li>
</ol>
<p>整数（按顺序）可以分成以下⼏个部分：</p>
<ol>
<li>若⼲空格</li>
<li>（可选）⼀个符号字符（' + ' 或 ' - ')</li>
<li>⾄少⼀位数字</li>
<li>若⼲空格</li>
</ol>
<p>例如，字符串["+100","5e2","-123","3.1416","-1E-16"] 都表示数值。</p>
<p>但是["12e","1a3.14","1.2.3","+-5","12e+4.3"] 都不是数值。</p>
<p>提示:</p>
<ol>
<li>1 <= str.length <= 25</li>
<li>str 仅含英⽂字⺟（⼤写和⼩写），数字（0-9），加号 '+' ，减号 '-' ，空格 ' ' 或者点 '.' 。</li>
<li>如果怀疑⽤例是不是能表示为数值的，可以使⽤python 的print(float(str)) 去查看</li>
</ol>
<p>示例1<br>
输⼊："123.45e+6"<br>
返回值：true</p>
<p>示例2<br>
输⼊："1.2.3"<br>
返回值：false</p>
<h2 id="思路及解答">思路及解答</h2>
<h3 id="暴力分析拆解">暴力分析拆解</h3>
<p>主要是分析好判断分⽀，可以定义⼏个变量：</p>
<ul>
<li>hashNum : 是否已经有数字</li>
<li>hashE ：是否已经有E</li>
<li>hasSign ：是否已经有符号</li>
<li>hasDot ：是否已经有⼩数点</li>
</ul>
<p>⾸先，初始化当前的索引index =0 ，字符串头部的空格需要跳过。</p>
<ul>
<li>循环判断索引是否在有效的范围内：
<ul>
<li>循环判断是否是数字，是数字则更新hasNum = true ,并且索引后移，直到不是数字的时候，跳出循环。</li>
</ul>
</li>
<li>跳出循环后，需要判断当前的index 是否合法，不合法直接break</li>
<li>取出当前索引的字符c ：
<ul>
<li>如果c 是e 或者E ：
<ul>
<li>如果前⾯已经出现过E ，或者前⾯没有数字，直接返回false</li>
<li>否则， hasE 置为true ，其他的置为false ，也就是E后⾯可以继续出现符号数字和⼩数点了</li>
</ul>
</li>
<li>如果c 是“ + ”或者“ - ”：
<ul>
<li>前⾯如果已经出现过数字或者符号或者⼩数点，都不是合法的</li>
<li>否则hasSign 置为true ，表示符号出现过</li>
</ul>
</li>
<li>如果c 是⼩数点“ . ”
<ul>
<li>如果前⾯已经有⼩数点或者有E出现了，那么就是⾮法的，返回false</li>
<li>否则hasDot 置为true</li>
</ul>
</li>
<li>如果c 为空格，直接跳出循环</li>
<li>否则，直接返回false</li>
</ul>
</li>
<li>最后也需要跳过空格</li>
<li>最后判断是否合法的条件是：是否到达最后⼀个字符，并且出现过数字</li>
</ul>
<pre><code class="language-java">public boolean isNumeric(String str) {
int size = str.length();
int index= 0 ;
// 默认全部是false
boolean hashNum=false ,hasE=false ,hasSign=false ,hasDot=false;
// 跳过空格
while(index<size&&str.charAt(index)==' '){
index++;
}
while(index<size){
while(index<size&&str.charAt(index)>='0'&& str.charAt(index)<='9'){
index++;
// 表示前⾯有数字
hashNum = true;
}
-
// 到末尾直接跳出
if(index==size){
break;
}
-
char c = str.charAt(index);
if(c=='e'||c=='E'){
// 前⾯有E或者没有数字在前⾯
if(hasE||!hashNum){
return false;
}
hasE = true;
// 出现E了后⾯⼜可以出现数字了
hashNum = false;
hasSign = false;
hasDot = false;
}else if(c=='+'||c=='-'){
if(hasSign||hashNum||hasDot){
return false;
}
hasSign = true;
}else if(c=='.'){
if(hasDot||hasE){
return false;
}
hasDot =true;
}else if(c==' '){
break;
}else{
return false;
}
index++;
}
// 跳过空格
while(index<size&&str.charAt(index)==' '){
index++;
}
return hashNum &&index==size;
}
</code></pre>
<p>这道题，其实本质是状态的切换，最最重要的⼀点，是 E 出现之后，其实⼩数点和符号，和数字，都是可以再出现的，可以理解为 E 就是⼀个分割线。</p>
<h3 id="正则表达式">正则表达式</h3>
<p>直接借助正则表达式进⾏匹配，但是并不太推荐这种解法：</p>
<pre><code class="language-java">public class Solution {
public boolean isNumeric (String str) {
// 核心正则表达式：处理空格、符号、小数、指数部分
// ^表示开头 $ 表示结尾 java中两个\\ 代表⼀个\
// \\s*开头可能有空格
// * 零次或多次匹配前⾯的字符或⼦表达式
// ？零次或⼀次匹配前⾯的字符或⼦表达式
// + ⼀次或多次匹配前⾯的字符或⼦表达式
// [] 字符集。匹配包含的任⼀字符
// (:? )匹配 pattern 但不捕获该匹配的⼦表达式，即它是⼀个⾮捕获匹配
String p = "^\\s*[+-]?(\\d*\\.\\d+|\\d+(\\.\\d*)?)(?:[+-]?\\d+)?$";
return Pattern.matches(p,str);
}
}
</code></pre>
<ul>
<li>O(n)时间复杂度</li>
<li>O(1)空间复杂度</li>
</ul>
<h3 id="有限状态机">有限状态机</h3>
<p>使用确定有限状态机(DFA)来精确建模数值的判断过程。</p>
<p>有限状态机法：通过状态转移精确控制数值格式。定义9种状态，根据输入字符进行状态转移</p>
<pre><code class="language-java">public boolean isNumberDFA(String str) {
if (str == null) return false;
// 状态定义：0-8共9种状态
// 0: 起始空格 1: 符号 2: 整数数字 3: 小数点前无数字
// 4: 小数点后有数字 5: 指数e 6: 指数符号 7: 指数数字 8: 结尾空格
int state = 0; // 初始状态
// 状态转移表
int[][] transitionTable = {
// 空格 符号 数字 小数点 e/E 其他
{0, 1, 2, 3, -1, -1}, // 状态0: 起始空格
{-1, -1, 2, 3, -1, -1}, // 状态1: 符号
{8,-1, 2, 4, 5, -1}, // 状态2: 整数数字
{-1, -1, 4, -1,-1, -1}, // 状态3: 小数点前无数字
{8,-1, 4, -1, 5, -1}, // 状态4: 小数点后有数字
{-1,6, 7, -1,-1, -1}, // 状态5: 指数e
{-1, -1, 7, -1,-1, -1}, // 状态6: 指数符号
{8,-1, 7, -1,-1, -1}, // 状态7: 指数数字
{8,-1,-1, -1,-1, -1}// 状态8: 结尾空格
};
for (char c : str.toCharArray()) {
int inputType = getInputType(c);
if (inputType == -1) return false;
state = transitionTable;
if (state == -1) return false;
}
// 可接受的状态：数字相关状态(2,4,7,8)
return state == 2 || state == 4 || state == 7 || state == 8;
}
// 将字符分类为状态机输入类型
private int getInputType(char c) {
switch (c) {
case ' ': return 0; // 空格
case '+': case '-': return 1; // 符号
case '0': case '1': case '2': case '3': case '4':
case '5': case '6': case '7': case '8': case '9':
return 2; // 数字
case '.': return 3; // 小数点
case 'e': case 'E': return 4; // 指数符号
default: return 5; // 其他字符
}
}
</code></pre>
<ul>
<li>时间复杂度：O(n)</li>
<li>空间复杂度：O(1)</li>
</ul>
</div>
<div id="MySignature" role="contentinfo">
<p>本文来自在线网站：seven的菜鸟成长之路，作者：seven，转载请注明原文链接：www.seven97.top</p><br><br>
来源：https://www.cnblogs.com/sevencoding/p/19377675
頁:
[1]