给媳妇做的网站,今天刚刚发生的新闻事故,全网万能搜索引擎,国外个人网站模板本文涉及的基础知识点
C算法#xff1a;前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频 C单调栈
LeetCode 1124. 表现良好的最长时间段
给你一份工作时间表 hours#xff0c;上面记录着某一位员工每天的工作小时数。 我们认为当员工一天中的工作小时数大…本文涉及的基础知识点
C算法前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频 C单调栈
LeetCode 1124. 表现良好的最长时间段
给你一份工作时间表 hours上面记录着某一位员工每天的工作小时数。 我们认为当员工一天中的工作小时数大于 8 小时的时候那么这一天就是「劳累的一天」。 所谓「表现良好的时间段」意味在这段时间内「劳累的天数」是严格 大于「不劳累的天数」。 请你返回「表现良好时间段」的最大长度。 示例 1 输入hours [9,9,6,0,6,6,9] 输出3 解释最长的表现良好时间段是 [9,9,6]。 示例 2 输入hours [6,6,6] 输出0 提示 1 hours.length 104 0 hours[i] 16
前缀和单调栈
劳累的一天权值1,不劳累的一天权值-1。某个子数组的权值和大于0,则是表现良好的时间段否则不是。子数组[i,j]之和为:preSum[j1] - preSum[i]。其中i ∈ \in ∈[0,j]。 如果preSum[i] preSum[j1]则[i,j]是良好表现时段。寻找最大的i。 如果有多个preSum[i]符合显示取小标最小的。 i1i2,且preSum[i1] preSum[i2]则i1无论如何优于i2即i1淘汰i2。淘汰后 preSum[stack元素]严格递减。 分两步 一预处理建立栈。 二j从大到小处理栈。两种条件出栈 a,栈顶元素下标大于当前下标。 b,preSum[栈顶元素] preSum[j][栈顶元素,j]是良好区域。如果是良好时间段出栈不会影响结果。因为j只会越来越小即[i,j]的长度也只会越来越小。
代码
核心代码
class Solution {public:int longestWPI(vectorint hours) {vectorint preSum(1);for (const auto n : hours) {preSum.emplace_back(preSum.back() (n 8 ? 1 : -1));}stackint sta;for (int i 0; i preSum.size(); i) {if (sta.empty() || (preSum[i] preSum[sta.top()])) {sta.emplace(i);}}int res 0;for (int j hours.size() - 1; j 0; j--) {while (sta.size() (sta.top() j)) {sta.pop();}while (sta.size() (preSum[j1] preSum[sta.top()])) {res max(res, j 1 - sta.top());sta.pop();}}return res;}};单元测试 vectorint hours;TEST_METHOD(TestMethod11){hours { 9, 9, 6, 0, 6, 6, 9 };auto res Solution().longestWPI(hours);AssertEx(3, res);}TEST_METHOD(TestMethod12){hours { 6,6,6 };auto res Solution().longestWPI(hours);AssertEx(0, res);}TEST_METHOD(TestMethod13){hours { 9,9,9,9,6,6,6 };auto res Solution().longestWPI(hours);AssertEx(7,res);}优化 while (sta.size() (sta.top() j)) {sta.pop();}可以被优化掉sta.top() j 其长度为负数自然被排除掉。
class Solution {public:int longestWPI(vectorint hours) {vectorint preSum(1);for (const auto n : hours) {preSum.emplace_back(preSum.back() (n 8 ? 1 : -1));}stackint sta;for (int i 0; i preSum.size(); i) {if (sta.empty() || (preSum[i] preSum[sta.top()])) {sta.emplace(i);}}int res 0;for (int j hours.size() - 1; j 0; j--) { while (sta.size() (preSum[j1] preSum[sta.top()])) {res max(res, j 1 - sta.top());sta.pop();}}return res;}};扩展阅读
我想对大家说的话工作中遇到的问题可以按类别查阅鄙人的算法文章请点击《算法与数据汇总》。学习算法按章节学习《喜缺全书算法册》大量的题目和测试用例打包下载。重视操作有效学习明确的目标 及时的反馈 拉伸区难度合适 专注闻缺陷则喜(喜缺)是一个美好的愿望早发现问题早修改问题给老板节约钱。子墨子言之事无终始无务多业。也就是我们常说的专业的人做专业的事。如果程序是一条龙那算法就是他的是睛失败反思成功 成功反思成功
视频课程
先学简单的课程请移步CSDN学院听白银讲师也就是鄙人的讲解。 https://edu.csdn.net/course/detail/38771 如何你想快速形成战斗了为老板分忧请学习C#入职培训、C入职培训等课程 https://edu.csdn.net/lecturer/6176
测试环境
操作系统win7 开发环境 VS2019 C17 或者 操作系统win10 开发环境 VS2022 C17 如无特殊说明本算法用**C**实现。
