[字符串]leetcode65：有效数字(hard)

字符串]leetcode65：有效数字(hard)"/>

[字符串]leetcode65：有效数字(hard)

题目：

65. 有效数字

题解：

本题挺难的，主要一些小问题很难处理，在这里我提供两种方法解题。第一种方法比较简单，第二种方法比较难，我也没懂，以后研究吧。

---

题解①：暴力法

• 1）先去除字符串首尾的空格
• 2）然后根据e划分指数和底数
• 3）判断指数和底数是否合法即可

---

题解②：有限自动机，表驱动（需要参考编译原理，主要我没学，我也不会呜呜呜）

题解①代码如下：

class Solution {
public:bool isNumber(string s) {//1、从首尾寻找s中不为空格首尾位置，也就是去除首尾空格int i=s.find_first_not_of(' ');//寻找第一个不为空格的字符位置if(i==string::npos)return false;//字符串全为空格，直接返回falseint j=s.find_last_not_of(' ');//寻找最后一个不为空格的字符s=s.substr(i,j-i+1);if(s.empty())return false;//2、根据e来划分底数和指数int e=s.find('e');//3、指数为空，判断底数if(e==string::npos)return judgeP(s);//4、指数不为空，判断底数和指数else return judgeP(s.substr(0,e))&&judgeS(s.substr(e+1));}bool judgeP(string s)//判断底数是否合法{bool result=false,point=false;int n=s.size();for(int i=0;i<n;++i){if(s[i]=='+'||s[i]=='-'){//符号位不在第一位，返回falseif(i!=0)return false;}else if(s[i]=='.'){if(point)return false;//有多个小数点，返回falsepoint=true;}else if(s[i]<'0'||s[i]>'9'){//非纯数字，返回falsereturn false;}else{result=true;}}return result;}bool judgeS(string s)//判断指数是否合法{   bool result=false;//注意指数不能出现小数点，所以出现除符号位的非纯数字表示指数不合法for(int i=0;i<s.size();++i){if(s[i]=='+'||s[i]=='-'){//符号位不在第一位，返回falseif(i!=0)return false;}else if(s[i]<'0'||s[i]>'9'){//非纯数字，返回falsereturn false;}else{result=true;}}return result;}
};

题解②代码如下：

class Solution {
public:bool isNumber(string s) {int state = 0;for (int i = 0; state != -1 && i < s.size(); i++) {switch (s[i]) {case ' ' :state = trans[state][0];break;case '+' :case '-' :state = trans[state][1];break;case '.' :state = trans[state][2];break;case 'e' :state = trans[state][3];break;default:state = isdigit(s[i]) ? trans[state][4] : -1;}}return state >= 5;}private:vector<vector<int>> trans = {{ 0,  1,  2, -1,  5}, {-1, -1,  2, -1,  5}, {-1, -1, -1, -1,  6},{-1,  4, -1, -1,  7}, {-1, -1, -1, -1,  7}, { 8, -1,  6,  3,  5},{ 8, -1, -1,  3,  6}, { 8, -1, -1, -1,  7}, { 8, -1, -1, -1, -1}};
};