表示数值的字符串:DFA解法

表示数值的字符串

http://www.nowcoder.com/questionTerminal/6f8c901d091949a5837e24bb82a731f2

public class Solution {
    // 方法1:使用编译原理中的确定有穷自动机DFA(Deterministic finite automation)
    // 思路:先确定可能输入的符号集合,并进行分类,如符号位(+/-),数字(0-9)等.然后根据
    // 不同的类型的符号作为输入,记录状态的变化,并将变化的状态总结成状态矩阵,矩阵类型
    // 为char[][].
    // PS:此方法的时间复杂度(时间消耗)和空间复杂度都是最低的,但是缺点在于针对不同的
    // 输入符号集就需要构建不同状态转换矩阵,在解题时实际上准备工作是非常耗时的,而且
    // 在进行DFA化简时,也很容易遗漏或者合并错误状态,导致矩阵错误.如"-.123"等特例,
    // 在本题中可能符合要求,也可能不符合要求,因此存在歧义.在牛客中"-.123",".123"
    // 也是属于数字,即需要返回True(真的无法理解为啥)
    // 时间复杂度:O(n),空间复杂度:O(1)
    private char[][] stateMatrix = new char[][]{
        // [+,-],[E,e],[0-9],[.],[&],[Other]
        // PS:&表示字符串结尾,T表示满足数字规定格式,F表示不满足数字规定格式,其他字
        // 符都不在接收范围内,遇到时直接返回False
        {'1', 'F', '2', '4', 'F'},
        {'F', 'F', '2', '4', 'F'},
        {'F', '3', '2', '4', 'T'},
        {'5', 'F', '6', 'F', 'F'},
        {'F', 'F', '7', 'F', 'F'},
        {'F', 'F', '6', 'F', 'F'},
        {'F', 'F', '6', 'F', 'T'},
        {'F', '3', '7', 'F', 'T'}
    };

    public boolean isNumeric(char[] str) {
        // 排除特殊边界条件的情况
        if (str == null || str.length == 0) return false;
        // 遍历字符数组中的每个字符,并匹配字符类型,同时转换状态
        char state = '0';
        int stateIndex = 0;
        for (char c : str) {
            stateIndex = state - '0';
            if (c == '+' || c == '-') state = stateMatrix[stateIndex][0];
            else if (c == 'E' || c == 'e') state = stateMatrix[stateIndex][1];
            else if (c >= '0' && c <= '9') state = stateMatrix[stateIndex][2];
            else if (c == '.') state = stateMatrix[stateIndex][3];
            else return false;// 若接收到意外字符,则直接返回False
            // 如果在遍历结束之前已经判断出为False,则直接返回
            if (state == 'F') return false;
        }
        // 遍历结束,直接返回最终结果
        // PS:正确的字符总要遍历到结尾,错误的字符在遍历过程中间和遍历结束时都需要判断
        return stateMatrix[state - '0'][4] == 'T';
    }
}
全部评论

相关推荐

Twilight_m...:表格简历有点难绷。说说个人看法: 1.个人基本情况里好多无意义信息,什么婚姻状况、健康状况、兴趣爱好、户口所在地、身份证号码、邮政编码,不知道的以为你填什么申请表呢。 2.校内实践个人认为对找工作几乎没帮助,建议换成和测开有关的项目,实在没得写留着也行。 3.工作经历完全看不出来是干什么的,起码看着和计算机没啥关系,建议加强描述,写点你在工作期间的实际产出、解决了什么问题。 4.个人简述大而空,看着像AI生成,感觉问题最大。“Python,C,C++成为我打造高效稳定服务的得力工具”、“我渴望凭借自身技术知识与创新能力,推动人工智能技术的应用发展,助力社会实现智能化转型”有种小学作文的美感。而且你确定你个人简述里写的你都会嘛?你AI这块写的什么“深入研究”,发几篇顶会的硕博生都不一定敢这么写。而且你AI这块的能力和软测也完全无关啊。个人简述建议写你对哪些技术栈、哪些语言、哪些生产工具的掌握,写的有条理些,而且最好是和测开强相关的。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务