[LeetBook]【学习日记】有效数字——状态机

题目

有效数字

有效数字(按顺序)可以分成以下几个部分:

  • 若干空格
  • 一个小数或者整数
  • (可选)一个’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),加号’+‘,减号’-‘,空格’ ‘或者点’.'。

解法

  • 这道题很容易想到遍历字符串,对不同情况进行判断,遇到不符合题意的情况就直接退出
  • 但是情况数比较多,需要写很多判断分支,比如底数是否有正负符号就有3种情况,指数有没有正负符号又是三种情况,这已经有九种情况符合题意了
  • 能不能有一种方法,以简洁的方式规定好每种情况后面可以出现的情况,一旦出现了不在规定里的情况,就不为有效数字;并且如果在还未完成有效数字时,在某个中间情况戛然而止,也不为有效数字
  • 这其实有点像拓扑排序,在这题中,对有向无环图,定义每个节点以及所有有效的最终节点,查找从起始节点 u 是否有路径 u->v 通往最终节点 v
    在这里插入图片描述
class Solution {
public:
    bool validNumber(string s) {
        //0.前导空格->0,1,2,4
        //1.底数正负符号->2,4
        //2.底数有整数部分的整数(234的2)->2,3,5,8
        //3.小数点或者点后的数字->3,5,8
        //4.底数没有整数部分时的小数点(.123的.),当小数点后有数字->3
        //5.e或者E->6,7
        //6.指数正负符号->7
        //7.指数部分的数字->7,8
        //8.后导空格->8

        //2,3,7,8为正确的出口
        vector<map<char, int>> states = {
            {{' ',0}, {'s',1}, {'d',2}, {'.',4}},   //在0状态遍历到的符号对应的可以转移的状态
            {{'d',2}, {'.',4}},                     //1状态转移
            {{'d',2}, {'.',3}, {'e',5}, {' ',8}},   //2状态转移
            {{'d',3}, {'e',5}, {' ',8}},            //3
            {{'d',3}},                              //4
            {{'s',6}, {'d',7}},                     //5
            {{'d',7}},                              //6
            {{'d',7}, {' ',8}},                     //7
            {{' ',8}}                               //8
        };
        char curChType = '?';//当前字符类型,数字'd'、符号's'、幂符号'e'、点'.'、空格' '
        int curState = 0;//初始状态设置为0,因为0没有前驱状态
        for(auto &ch:s){
            if(isdigit(ch)) curChType='d';
            else if(ch=='+' || ch=='-') curChType='s';
            else if(ch=='e' || ch=='E') curChType='e';
            else if(ch=='.') curChType='.';
            else if(ch==' ') curChType=' ';
            else return false;
            if(states[curState].find(curChType) != states[curState].end()){
                curState = states[curState].find(curChType)->second;
            }
            else return false;
        }
        return curState==2 || curState==3 || curState==7 || curState==8;
    }
};

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
THE END
分享
二维码
< <上一篇
下一篇>>