字符串]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}};
};
更多推荐
[字符串]leetcode65:有效数字(hard)
发布评论