wordpress建站优缺点,怀化建设公司网站,wordpress 手机主题插件,百度爱采购优化作者推荐
本文涉及的基础知识点
二分查找算法合集 滑动窗口 单调队列#xff1a;计算最大值时#xff0c;如果前面的数小#xff0c;则必定被淘汰#xff0c;前面的数早出队。
题目
你有 n 个机器人#xff0c;给你两个下标从 0 开始的整数数组 chargeTimes 和 runnin…作者推荐
本文涉及的基础知识点
二分查找算法合集 滑动窗口 单调队列计算最大值时如果前面的数小则必定被淘汰前面的数早出队。
题目
你有 n 个机器人给你两个下标从 0 开始的整数数组 chargeTimes 和 runningCosts 两者长度都为 n 。第 i 个机器人充电时间为 chargeTimes[i] 单位时间花费 runningCosts[i] 单位时间运行。再给你一个整数 budget 。 运行 k 个机器人 总开销 是 max(chargeTimes) k * sum(runningCosts) 其中 max(chargeTimes) 是这 k 个机器人中最大充电时间sum(runningCosts) 是这 k 个机器人的运行时间之和。 请你返回在 不超过 budget 的前提下你 最多 可以 连续 运行的机器人数目为多少。 示例 1 输入chargeTimes [3,6,1,3,4], runningCosts [2,1,3,4,5], budget 25 输出3 解释 可以在 budget 以内运行所有单个机器人或者连续运行 2 个机器人。 选择前 3 个机器人可以得到答案最大值 3 。总开销是 max(3,6,1) 3 * sum(2,1,3) 6 3 * 6 24 小于 25 。 可以看出无法在 budget 以内连续运行超过 3 个机器人所以我们返回 3 。 示例 2 输入chargeTimes [11,12,19], runningCosts [10,8,7], budget 19 输出0 解释即使运行任何一个单个机器人还是会超出 budget所以我们返回 0 。 参数范围 chargeTimes.length runningCosts.length n 1 n 5 * 104 1 chargeTimes[i], runningCosts[i] 105 1 budget 1015
双指针
分析
本质是子数组我们可以枚举起点left 子数组[left,righ)是不超预算的最长子数组。
时间复杂度
O(n)枚举left和right都是O(n)right没有从新开始所有总时间复杂度是O(n)。
代码
核心代码
class Solution { public: int maximumRobots(vector chargeTimes, vector runningCosts, long long budget) { m_c chargeTimes.size(); int iRet 0; long long llSum 0; std::deque vMaxIndex; for (int left 0, right 0; left m_c; left) { if (right left) { llSum 0; right left; vMaxIndex.clear(); } while (right m_c) { while (vMaxIndex.size() (chargeTimes[vMaxIndex.back()] chargeTimes[right])) { vMaxIndex.pop_back(); } vMaxIndex.emplace_back(right); const long long llNew (llSum runningCosts[right]) * (right-left1) chargeTimes[vMaxIndex.front()]; if (llNew budget) { break;// [left,right)超出预算有多个right取最小的按个 } llSum runningCosts[right]; right; } iRet max(iRet, right - left); llSum - runningCosts[left]; if (vMaxIndex.front() left) { vMaxIndex.pop_front(); } } return iRet; } int m_c; };
测试用例
templateclass T
void Assert(const vectorT v1, const vectorT v2)
{if (v1.size() ! v2.size()){assert(false);return;}for (int i 0; i v1.size(); i){assert(v1[i] v2[i]);}
}templateclass T
void Assert(const T t1, const T t2)
{assert(t1 t2);
}int main()
{vectorint chargeTimes, runningCosts;long long budget;{Solution slu;chargeTimes { 3,6,1,3,4 }, runningCosts { 2,1,3,4,5 }, budget 25;auto res slu.maximumRobots(chargeTimes, runningCosts, budget);Assert(3, res);}{Solution slu;chargeTimes { 11,12,19 }, runningCosts { 10,8,7 }, budget 19;auto res slu.maximumRobots(chargeTimes, runningCosts, budget);Assert(res, 0);}{Solution slu;chargeTimes { 19,63,21,8,5,46,56,45,54,30,92,63,31,71,87,94,67,8,19,89,79,25 }, runningCosts { 91,92,39,89,62,81,33,99,28,99,86,19,5,6,19,94,65,86,17,10,8,42 }, budget 85;auto res slu.maximumRobots(chargeTimes, runningCosts, budget);Assert(res, 1);}//CConsole::Out(res);
}优化
如果不存在以left开始的合法子数组right和left相同left后right就小于left 需要特殊处理。 我们换成先枚举right再枚举left。左闭右闭空间[left,right]是最长合法子数组。但不存在合法子数组时left等于right1right后两者就相等了无需特殊处理。
代码
class Solution {
public:int maximumRobots(vectorint chargeTimes, vectorint runningCosts, long long budget) {m_c chargeTimes.size();int iRet 0;long long llSum 0;std::dequeint vMaxIndex;for (int right 0, left 0; right m_c; right){ while (vMaxIndex.size() (chargeTimes[vMaxIndex.back()] chargeTimes[right])){vMaxIndex.pop_back(); }vMaxIndex.emplace_back(right);llSum runningCosts[right];while (left right ){ const long long llNew llSum * (right-left1) chargeTimes[vMaxIndex.front()];if (llNew budget){llSum - runningCosts[left];if (vMaxIndex.front() left){vMaxIndex.pop_front();}left;}else{break;}}iRet max(iRet, right - left1); }return iRet;}int m_c;
};二分查找
寻找最后一个不超预算的连续机器人长度左开右闭。时间复杂度(longnn)。二分长度时间复杂度度O(logn);指定长度枚举所有终点时间复杂度O(n)。
代码
class Solution { public: int maximumRobots(vector chargeTimes, vector runningCosts, long long budget) { m_c chargeTimes.size(); int left 0, right m_c 1; while (right - left 1) { const auto mid left (right - left) / 2; if (NeedBudget(chargeTimes, runningCosts, mid) budget) { left mid; } else { right mid; } } return left; } long long NeedBudget(vector chargeTimes, vector runningCosts, int len) { long long llSum 0; std::deque vMaxIndex; int i 0; for (; i len; i) { llSum runningCosts[i]; while (vMaxIndex.size() (chargeTimes[vMaxIndex.back()] chargeTimes[i])) { vMaxIndex.pop_back(); } vMaxIndex.emplace_back(i); } long long llNeed llSum * len chargeTimes[vMaxIndex.front()]; for (; i m_c; i) { llSum runningCosts[i]- runningCosts[i-len]; while (vMaxIndex.size() (chargeTimes[vMaxIndex.back()] chargeTimes[i])) { vMaxIndex.pop_back(); } vMaxIndex.emplace_back(i); if (vMaxIndex.front() i-len) { vMaxIndex.pop_front(); } llNeed min(llNeed,llSum * len chargeTimes[vMaxIndex.front()]); } return llNeed; } int m_c; }; 扩展阅读
视频课程
有效学习明确的目标 及时的反馈 拉伸区难度合适可以先学简单的课程请移步CSDN学院听白银讲师也就是鄙人的讲解。 https://edu.csdn.net/course/detail/38771
如何你想快
速形成战斗了为老板分忧请学习C#入职培训、C入职培训等课程 https://edu.csdn.net/lecturer/6176
相关下载
想高屋建瓴的学习算法请下载《喜缺全书算法册》doc版 https://download.csdn.net/download/he_zhidan/88348653
我想对大家说的话闻缺陷则喜是一个美好的愿望早发现问题早修改问题给老板节约钱。子墨子言之事无终始无务多业
。也就是我们常说的专业的人做专业的事。 | |如果程序是一条龙那算法就是他的是睛|
测试环境
操作系统win7 开发环境 VS2019 C17 或者 操作系统win10 开发环境
VS2022 C17
