LeetCode算法题

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

01 看题和准备

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

'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来完成。

1public boolean checkRecord(String s) {
2    if (s.indexOf('A') != s.lastIndexOf('A')) {
3        return false;
4    }
5    if (s.indexOf("LLL") != -1) {
6        return false;
7    }
8    return true;
9}

03 第二种解法

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

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

04 第三种解法

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

1public boolean checkRecord3(String s) {
2    int count_A = 0;
3    int count_L = 0;
4    for (char ch : s.toCharArray()) {
5        if (ch == 'A') {
6            count_A++;
7            if (count_A >= 2) {
8                return false;
9            }
10        }
11        if (ch == 'L') {
12            count_L++;
13            if (count_L >= 3) {
14                return false;
15            }
16        } else {
17            count_L = 0;
18        }
19    }
20    return true;
21}

05 第四种解法

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

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

06 小结

算法专题目前已日更超过三个月，算法题文章125+篇，公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词，获取系列文章合集。

以上就是全部内容，如果大家有什么好的解法思路、建议或者其他问题，可以下方留言交流，点赞、留言、转发就是对我最大的回报和支持！