[Java知识库]剑指odffer java day26 字符串

T1 20. 表示数值的字符串

方1：k神的题解有限状态自动机

初始状态，接受状态

? |------>被接受

初始状态-------^转移规制------->接受状态----------|------>被拒绝

本题根据题意9种状态

0、开始的空格
1、幂符号前的正负号
2、小数点前的数字
3、小数点、小数点后的数字
4、当小数点前为空格时，小数点、小数点后的数字
5、幂符号
6、幂符号后的正负号
7、幂符号后的数字
8、结尾的空格

绘制状态转移图

根据状态转移图抽象成状态转移表，字符串根据状态转移表遍历，最后结果属于 2，3，7，8则字串合法

class Solution {
    public boolean isNumber(String s) {
        //状态转移表 hashMap键是转移条件，值是转移到的状态
        Map[] states = {
            new HashMap<>() {{ put(' ', 0); put('s', 1); put('d', 2); put('.', 4); }}, // 0. 
            new HashMap<>() {{ put('d', 2); put('.', 4); }},                           // 1.
            new HashMap<>() {{ put('d', 2); put('.', 3); put('e', 5); put(' ', 8); }}, // 2.
            new HashMap<>() {{ put('d', 3); put('e', 5); put(' ', 8); }},              // 3.
            new HashMap<>() {{ put('d', 3); }},                                        // 4.
            new HashMap<>() {{ put('s', 6); put('d', 7); }},                           // 5.
            new HashMap<>() {{ put('d', 7); }},                                        // 6.
            new HashMap<>() {{ put('d', 7); put(' ', 8); }},                           // 7.
            new HashMap<>() {{ put(' ', 8); }}                                         // 8.
        };
        int p = 0;
        char t;
        for(char c : s.toCharArray()) {
            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].containsKey(t)) return false;
            p = (int)states[p].get(t);
        }
        return p == 2 || p == 3 || p == 7 || p == 8;
    }
}

作者：jyd
链接：https://leetcode-cn.com/problems/biao-shi-shu-zhi-de-zi-fu-chuan-lcof/solution/mian-shi-ti-20-biao-shi-shu-zhi-de-zi-fu-chuan-y-2/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

方二：剑指书上的解法

class Solution {
    //数.[.[+/-]][e|E数] 或者 .[+/-][e|E数]   (合法的顺序[]表示可无)
    //以.和e为分界线进行处理
    //注意判断l<=right,防止越界
    int left,right;
    public boolean isNumber(String s) {
        char[] c = s.toCharArray();
        right = c.length-1;
        //跳过前后空格
        while(left<=right && c[left] == ' ')  left++;
        while(left<=right && c[right] == ' ')  right--;
        if(left<=right && (c[left] == '+' || c[left] == '-'))    left++;

        boolean res = isNumber(c); //res表示当前位置之前合法性

        //.判断前后数字可能性
        if(left<=right && c[left] == '.'){
            left++;
            // 合法的情况 
            //前数后点 或 前点后数 或 数点数;   
            //条件1||条件2 条件1true->true;条件1false再根据条件2判断
            res = isNumber(c) || res;
        }
        
        //e 前后判断
        if(left<=right && (c[left] == 'e' || c[left] == 'E')){
            left++;
            //e 需要前后都要有整数 注意e的后面是可以跟符号的
            if(left<=right && (c[left] == '+' || c[left] == '-'))    left++;
            res = res && isNumber(c);
        }
        
        
        return res && left == right+1; //遍历完全且合法
    }

    //判断是否有数字
    public boolean isNumber(char[] c){
        int tmp = left; //记录起始下标

        while(left<=right && c[left]>='0' && c[left]<='9')   left++;
        
        //left>before说明有扫描到数字
        return left>tmp;
    }
}

T2 67. 把字符串转换成整数

越界判断

x是当前位

class Solution {
    public int strToInt(String str) {
        char[] c = str.trim().toCharArray(); //去掉前后空格并转换位字符数组
        if(c.length==0) return 0;
        int res=0,bndry = Integer.MAX_VALUE/10; //结果，越界分界点
        int i=1,flag=1; //i表示数字位的开始.flag标志正负位

        //符号判断
        if(c[0]=='-') flag=-1;
        else if(c[0]!='+') i=0;//正号相当于从0位开始

        for(int j=i;j<c.length;j++){
            //非数字停止
            if(c[j]<'0' || c[j]>'9') break; 

            //满足越界情况，根据正负返回最值
            if(res>bndry || (res==bndry && c[j]>'7')) 
                return flag==1? Integer.MAX_VALUE:Integer.MIN_VALUE;
            res = res*10+(c[j]-'0'); //转化位数字的绝对值
        }
        return res*flag; //符号和数值
    }
}