LeetCode算法题-Student Attendance Record I（Java实现）

佚名 5年前 (2019-02-24) 算法 1354人围观抢沙发百度已收录

这是悦乐书的第258次更新，第271篇原创

01 看题和准备

今天介绍的是LeetCode算法题中Easy级别的第125题（顺位题号是551）。您将获得一个表示学生出勤记录的字符串。该记录仅包含以下三个字符：

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

'A'：缺席。

'L'：迟到。

'P'：在场。

如果学生的出勤记录不超过一个“A”（缺席）或超过两个连续的“L”（迟到），则可以奖励学生。您需要返回学生是否可以根据他的出勤记录获得奖励。例如：

输入：“PPALLP”
输出：true

输入：“PPALLL”
输出：false

本次解题使用的开发工具是eclipse，jdk使用的版本是1.8，环境是win7 64位系统，使用Java语言编写和测试。

02 第一种解法

根据题目的意思，出现一次A可以是true，两次及以上是false，连续三次L是false。因此，我们只需要判断该字符串中，A是不是出现了两次及以上；该字符串中是否包含"LLL"子串。对此，我们只需要判断第一次出现A的索引和最后一次出现的A的索引是否相等即可，不相等说明有至少两个A。另外，查找s中是否含有"LLL"子串，都可以直接借助indexOf来完成。

public boolean checkRecord(String s) {
    if (s.indexOf('A') != s.lastIndexOf('A')) {
        return false;
    }
    if (s.indexOf("LLL") != -1) {
        return false;
    }
    return true;
}

03 第二种解法

第一种解法我们再简化下，可以一行代码搞定。也就是s中不包含两个A，并且不包含三个连续的L，才能返回true，否则一律是false。

public boolean checkRecord2(String s) {
    return s.indexOf('A') == s.lastIndexOf('A') && s.indexOf("LLL") == -1;
}

04 第三种解法

我们也可以直接使用记数的方式来判断。使用两个变量，统计A和L出现的次数。for循环内部，如果出现两次A就直接返回false；如果遇上L，记数变量先加1，如果下一个字符不是L就将记数变量重置为0，反之如果连续出现三次，那么就直接返回false。

public boolean checkRecord3(String s) {
    int count_A = 0;
    int count_L = 0;
    for (char ch : s.toCharArray()) {
        if (ch == 'A') {
            count_A++;
            if (count_A >= 2) {
                return false;
            }
        }
        if (ch == 'L') {
            count_L++;
            if (count_L >= 3) {
                return false;
            }
        } else {
            count_L = 0;
        }
    }
    return true;
}

05 第四种解法

我们还可以使用正则表达式来匹配判断。

public boolean checkRecord4(String s) {
    /**
     * 如果含有连续三个L的子串，可以用.*LLL.*表示，.表示匹配除 "\n" 之外的任何单个字符，*匹配前面的子表达式零次或多次。
     * |表示或的关系。.*A.*A.*表示包含两个A。
     */
    return !s.matches(".*LLL.*|.*A.*A.*");
}