​LeetCode刷题实战552:学生出勤记录 II

2023-11-02 11:31

本文主要是介绍​LeetCode刷题实战552:学生出勤记录 II,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !

今天和大家聊的问题叫做 学生出勤记录 II,我们先来看题面:

https://leetcode-cn.com/problems/student-attendance-record-ii/

You are given a string s representing an attendance record for a student where each character signifies whether the student was absent, late, or present on that day. The record only contains the following three characters:

  • 'A': Absent.

  • 'L': Late.

  • 'P': Present.

The student is eligible for an attendance award if they meet both of the following criteria:

  • The student was absent ('A') for strictly fewer than 2 days total.

  • The student was never late ('L') for 3 or more consecutive days.

Given an integer n, return the number of possible attendance records of length n that make a student eligible for an attendance award. The answer may be very large, so return it modulo 109 + 7.

给你一个字符串 s 表示一个学生的出勤记录,其中的每个字符用来标记当天的出勤情况(缺勤、迟到、到场)。记录中只含下面三种字符:

  • 'A':Absent,缺勤

  • 'L':Late,迟到

  • 'P':Present,到场

如果学生能够 同时 满足下面两个条件,则可以获得出勤奖励:

  • 按 总出勤 计,学生缺勤('A')严格 少于两天。

  • 学生 不会 存在 连续 3 天或 连续 3 天以上的迟到('L')记录。

给你一个整数 n ,表示出勤记录的长度(次数)。请你返回记录长度为 n 时,可能获得出勤奖励的记录情况 数量 。答案可能很大,所以返回对 109 + 7 取余 的结果。

示例

示例 1:
输入:n = 2
输出:8
解释:
有 8 种长度为 2 的记录将被视为可奖励:
"PP" , "AP", "PA", "LP", "PL", "AL", "LA", "LL" 
只有"AA"不会被视为可奖励,因为缺勤次数为 2 次(需要少于 2 次)。示例 2:
输入:n = 1
输出:3示例 3:
输入:n = 10101
输出:183236316

解题

https://www.jianshu.com/p/ac5eb0474f7a

输入 n 代表的是天数,我每天去上学,有三种结果:准时 P,缺席 P,迟到 L。如果我 n 天后没有缺席超过一次(严格少于 2 天),且没有连续超过两天迟到,则我可以拿到奖励。

我在 1 - n 中的任何一天,是否有可能拿到奖励,取决于我过去的日子的上学情况,例如:

例 1:如果今天缺席了,而我过去某一天也缺席了,则我一定无法最终拿到奖励;

例 2:如果今天缺席了,我过去每一天都是好学生,一次缺席也没有,一次迟到也没有,那我今天缺席一次没啥嘛,之后好好表现还是有可能拿到奖励。

这样就是从小问题可以推导出大问题,用动态规划解。

dp[i][j][k] 等于第 i 天,在过去缺席了 j 次,以及连续迟到了 k 次的情况下,还可以拿到奖励的出席排列的数量。随着天数的增加,这个 dp 的值肯定是递减的,因为搞不好未来哪一天就缺席或者迟到再也拿不到奖励了。

j 一共有两种可能,0 或者 1 ,对应不能缺席超过 1 次。k 一共有三种可能:0,1,2,对应不能连续迟到超过 2 次。

今天:缺席、不缺席、连续迟到天数

dp[天数][缺席][连续迟到] 一共有六种:

dp[i][0][0]:今天截止 0 次缺席,今天截止 0 天连续迟到。

dp[i][0][1]:今天截止 0 次缺席,今天截止 1 天连续迟到。

dp[i][0][2]:今天截止 0 次缺席,今天截止 2 天连续迟到。

dp[i][1][0]:今天截止 1 次缺席,今天截止 0 天连续迟到。

dp[i][1][1]:今天截止 1 次缺席,今天截止 1 天连续迟到。

dp[i][1][2]:今天截止 1 次缺席,今天截止 2 天连续迟到。

我们依次分析六种情况:

情况 1:今天截止 0 次缺席,今天截止 0 次连续迟到:

dp[i][0][0] = dp[i - 1][0][0] + dp[i - 1][0][1] + dp[i - 1][0][2]

说明:「今天截止 0 次缺席」说明今天出席。

过去一定也是 0 次缺席,但过去可以有 0,1,2 次连续迟到;

只要今天按时出席,过去的迟到记录都一笔勾销。

情况 2:今天截止 1 次缺席,今天截止 0 次连续迟到:

dp[i][1][0] = dp[i - 1][1][0] + dp[i - 1][1][1] + dp[i - 1][1][2] + dp[i - 1][0][0] + dp[i - 1][0][1] + dp[i - 1][0][2]

分两种情况:

前三项,代表过去有 1 次缺席,今天没有缺席,但过去可以有 0、1、2 次连续迟到,过去的迟到记录都一笔勾销。

后三项,代表过去有 0 次缺席,今天缺席了,但过去可以有 0、1、2 次连续迟到,过去的迟到记录都一笔勾销。

情况 3:今天截止 0 次缺席,今天截止 1 次连续迟到:

dp[i][0][1] = dp[i - 1][0][0];

过去 0 次缺席,过去 0 次迟到,今天迟到了。

情况 4:今天截止 0 次缺席,今天截止 2 次连续迟到:

dp[i][0][2] = dp[i - 1][0][1];

过去 0 次缺席,昨天迟到,今天迟到了,(只能从 1 转来)。

情况 5:今天截止 1 次缺席,今天截止 1 次连续迟到:

dp[i][1][1] = dp[i - 1][1][0];

过去 1 次缺席,过去 0 次迟到,今天迟到了。

这里可以仔细想一下,我今天必须要迟到,所以今天截止的 1 次缺席必定来自过去。

情况 6:今天截止 1 次缺席,今天截止 2 次连续迟到:

dp[i][1][2] = dp[i - 1][1][1];

过去 1 次缺席,昨天迟到,今天迟到了。

最后,把最后一天的六种情况加和即为答案。

class Solution {public int checkRecord(int n) {final int MOD = 1000000007;int[][][] dp = new int[n + 1][2][3]; // 长度,A (缺席)的数量,结尾连续 L (迟到)的数量dp[0][0][0] = 1;for (int i = 1; i <= n; i++) {// 以 P 结尾的数量for (int j = 0; j <= 1; j++) {for (int k = 0; k <= 2; k++) {dp[i][j][0] = (dp[i][j][0] + dp[i - 1][j][k]) % MOD;}}// 以 A 结尾的数量for (int k = 0; k <= 2; k++) {dp[i][1][0] = (dp[i][1][0] + dp[i - 1][0][k]) % MOD;}// 以 L 结尾的数量for (int j = 0; j <= 1; j++) {for (int k = 1; k <= 2; k++) {dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j][k - 1]) % MOD;}}}int sum = 0;for (int j = 0; j <= 1; j++) {for (int k = 0; k <= 2; k++) {sum = (sum + dp[n][j][k]) % MOD;}}return sum;}
}

好了,今天的文章就到这里,如果觉得有所收获,请顺手点个在看或者转发吧,你们的支持是我最大的动力 。

上期推文:

LeetCode1-540题汇总,希望对你有点帮助!

LeetCode刷题实战541:反转字符串 II

LeetCode刷题实战542:01 矩阵

LeetCode刷题实战543:二叉树的直径

LeetCode刷题实战544:输出比赛匹配对

LeetCode刷题实战545:二叉树的边界

LeetCode刷题实战546:移除盒子

LeetCode刷题实战547:省份数量

LeetCode刷题实战548:将数组分割成和相等的子数组

LeetCode刷题实战549:二叉树中最长的连续序列

LeetCode刷题实战550:游戏玩法分析 IV

LeetCode刷题实战551:学生出勤记录 I

d7a9956822d48e11f2fa656d6d7c9264.png

这篇关于​LeetCode刷题实战552:学生出勤记录 II的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/330323

相关文章

网页解析 lxml 库--实战

lxml库使用流程 lxml 是 Python 的第三方解析库,完全使用 Python 语言编写,它对 XPath表达式提供了良好的支 持,因此能够了高效地解析 HTML/XML 文档。本节讲解如何通过 lxml 库解析 HTML 文档。 pip install lxml lxm| 库提供了一个 etree 模块,该模块专门用来解析 HTML/XML 文档,下面来介绍一下 lxml 库

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

性能分析之MySQL索引实战案例

文章目录 一、前言二、准备三、MySQL索引优化四、MySQL 索引知识回顾五、总结 一、前言 在上一讲性能工具之 JProfiler 简单登录案例分析实战中已经发现SQL没有建立索引问题,本文将一起从代码层去分析为什么没有建立索引? 开源ERP项目地址:https://gitee.com/jishenghua/JSH_ERP 二、准备 打开IDEA找到登录请求资源路径位置

C#实战|大乐透选号器[6]:实现实时显示已选择的红蓝球数量

哈喽,你好啊,我是雷工。 关于大乐透选号器在前面已经记录了5篇笔记,这是第6篇; 接下来实现实时显示当前选中红球数量,蓝球数量; 以下为练习笔记。 01 效果演示 当选择和取消选择红球或蓝球时,在对应的位置显示实时已选择的红球、蓝球的数量; 02 标签名称 分别设置Label标签名称为:lblRedCount、lblBlueCount

滚雪球学Java(87):Java事务处理:JDBC的ACID属性与实战技巧!真有两下子!

咦咦咦,各位小可爱,我是你们的好伙伴——bug菌,今天又来给大家普及Java SE啦,别躲起来啊,听我讲干货还不快点赞,赞多了我就有动力讲得更嗨啦!所以呀,养成先点赞后阅读的好习惯,别被干货淹没了哦~ 🏆本文收录于「滚雪球学Java」专栏,专业攻坚指数级提升,助你一臂之力,带你早日登顶🚀,欢迎大家关注&&收藏!持续更新中,up!up!up!! 环境说明:Windows 10

Node.js学习记录(二)

目录 一、express 1、初识express 2、安装express 3、创建并启动web服务器 4、监听 GET&POST 请求、响应内容给客户端 5、获取URL中携带的查询参数 6、获取URL中动态参数 7、静态资源托管 二、工具nodemon 三、express路由 1、express中路由 2、路由的匹配 3、路由模块化 4、路由模块添加前缀 四、中间件

AI基础 L9 Local Search II 局部搜索

Local Beam search 对于当前的所有k个状态,生成它们的所有可能后继状态。 检查生成的后继状态中是否有任何状态是解决方案。 如果所有后继状态都不是解决方案,则从所有后继状态中选择k个最佳状态。 当达到预设的迭代次数或满足某个终止条件时,算法停止。 — Choose k successors randomly, biased towards good ones — Close

leetcode-24Swap Nodes in Pairs

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode swapPairs(L

leetcode-23Merge k Sorted Lists

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode mergeKLists

C++ | Leetcode C++题解之第393题UTF-8编码验证

题目: 题解: class Solution {public:static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num &