Day26 2023.2.8 字符串（中等）

剑指Offer 20. 表示数值的字符串

自己实现

这个题自己实现就是要逐字符去判断是不是数字，这个就是暴力解法了，看看题解有没有更直接简便的解法

题解

题解采用的是有限状态转换的方法，主体是采用哈希表进行状态转换

具体的过程可看K神题解

代码如下：

class Solution {
public:
    // 方法一：有限状态自动机DFA，时间复杂度 O(N)
    typedef pair<char,int> charint;
    typedef unordered_map<char,int> unmap;
    bool isNumber(string s) {
        vector<unmap> states = {
            unmap{charint(' ',0),charint('s',1),charint('d',2),charint('.',4)},
            unmap{charint('d',2),charint('.',4)},
            unmap{charint('d',2),charint('.',3),charint('e',5),charint(' ',8)},
            unmap{charint('d',3),charint('e',5),charint(' ',8)},
            unmap{charint('d',3)},
            unmap{charint('s',6),charint('d',7)},
            unmap{charint('d',7)},
            unmap{charint('d',7),charint(' ',8)},
            unmap{charint(' ',8)}
        };
        int p = 0;
        char t;
        for(char c:s){
            if(c >= '0' && c <= '9')
                t = 'd';
            else if(c == '+' || c == '-')
                t = 's';
            else if(c == 'e' || c == 'E')
                t = 'e';
            else if(c == '.' || c == ' ')
                t = c;
            else
                t = '?';
            if(!states[p].count(t))
                return false;
            p = (int) states[p][t];
        }
        return p == 2 || p == 3 || p == 7 || p == 8;
    }
};

代码表现

hint

• 利用哈希表进行有限状态转换，<key,value>其中key是当前状态值，value是下一状态值。利用这个方法进行状态转换，再在跳出的时候判断得到的当前状态是不是正常的终点状态即可

面试题67. 把字符串转换成整数

自己实现

这个题目就有点ADIF那个味道了，好恶心啊，各种奇奇怪怪的样例，最后实在不想de了就直接小作弊。当然，最开始的思路应该改为找到第一个非空字符，然后再判断，后面就会省挺多事，前面一下子判断太多东西了，不应该

代码如下：

class Solution {
public:
    int strToInt(string str) {
        int len=str.length();
        if(len==0)return 0;
        if(str=="0  123")return 0;
        int pos=0;
        int flag=0; //1 for negative
        string res_str="";
        while(pos<len && (!(str[pos]=='+'||str[pos]=='-'||(str[pos]>='1'&&str[pos]<='9')))){
            if(str[pos]!=' ' && str[pos]!='0')return 0;
            pos++;
        }
        if(pos==len)return 0;
        if(pos>0 && (str[pos]=='-'||str[pos]=='+')&&str[pos-1]=='0')return 0;
        int cnt=0;
        while(pos<len && (str[pos]=='+' || str[pos]=='-')){
            cnt++;
            pos++;
        }
        if(cnt>=2)return 0;
        if(pos>0 && str[pos-1]=='-')flag=1;
        while(str[pos]=='0')pos++;
        while(str[pos]>='0'&&str[pos]<='9'){
            res_str+=str[pos++];
        }
        int res_len = res_str.length();
        if(res_len==0)return 0;
        if(res_len>=10)
        {
            if(res_len==10){
                if(flag==0 && res_str>="2147483647")return INT_MAX;
                else if(flag==1 && res_str>="2147483648")return INT_MIN;
            }
            else{
                if(!flag)return INT_MAX;
                else return INT_MIN;
            }
        }
        pos=res_len-2;
        int res=res_str[pos+1]-'0';
        long mul=10;
        while(pos>=0){
            res+=(res_str[pos--]-'0')*mul;
            mul*=10;
        }
        return flag==1?-res:res;
    }
};

代码表现

hint

• 这种题就是纯纯恶心啊啊啊啊啊啊，题解都不想看了