开发网站需要问什么,淘宝网站建设合同,国内永久免费crm系统破解版,制作手机软件网站本文涉及的基础知识点
C单调栈
LeetCode853. 车队
在一条单行道上#xff0c;有 n 辆车开往同一目的地。目的地是几英里以外的 target 。 给定两个整数数组 position 和 speed #xff0c;长度都是 n #xff0c;其中 position[i] 是第 i 辆车的位置#xff0c; speed[i…本文涉及的基础知识点
C单调栈
LeetCode853. 车队
在一条单行道上有 n 辆车开往同一目的地。目的地是几英里以外的 target 。 给定两个整数数组 position 和 speed 长度都是 n 其中 position[i] 是第 i 辆车的位置 speed[i] 是第 i 辆车的速度(单位是英里/小时)。 一辆车永远不会超过前面的另一辆车但它可以追上去并以较慢车的速度在另一辆车旁边行驶。 车队 是指并排行驶的一辆或几辆汽车。车队的速度是车队中 最慢 的车的速度。 即便一辆车在 target 才赶上了一个车队它们仍然会被视作是同一个车队。 返回到达目的地的车队数量 。 示例 1 输入target 12, position [10,8,0,5,3], speed [2,4,1,1,3] 输出3 解释 从 10速度为 2和 8速度为 4开始的车会组成一个车队它们在 12 相遇。车队在 target 形成。 从 0速度为 1开始的车不会追上其它任何车所以它自己是一个车队。 从 5速度为 1 和 3速度为 3开始的车组成一个车队在 6 相遇。车队以速度 1 移动直到它到达 target。 示例 2 输入target 10, position [3], speed [3] 输出1 解释 只有一辆车因此只有一个车队。 示例 3 输入target 100, position [0,2,4], speed [4,2,1] 输出1 解释 从 0速度为 4 和 2速度为 2开始的车组成一个车队在 4 相遇。从 4 开始的车速度为 1移动到了 5。 然后在 4速度为 2的车队和在 5速度为 1的车成为一个车队在 6 相遇。车队以速度 1 移动直到它到达 target。 提示 n position.length speed.length 1 n 105 0 target 106 0 position[i] target position 中每个值都 不同 0 speed[i] 106
单调栈
性质一车头速度没边其它车有可能变化。 性质二postion[i1] postion[i2]由于不能超车则i1从始至终都在i2前面。 性质三排除i1和i2以外的所有车如果i2能赶上i1则在本题一定能加入一个车队。 性质四 ∀ \forall ∀i1,postion[i1] postion[i2], 排除i1和i2以外的所有车i2都赶不上i1。则在本题中,i2赶不上任何一两车即无法加入车队成为车头。可以用反证法证明如果加入车队时车头是i1车头速度没降。那么除去i1、i2外i2也能赶上i1。 indexs是postion的下标postion[indexs[i]] 降序排序。 for(i : indexs) 处理postion[i]和speed[i]。 如果前面有车到达终点需要的时间 当前车需要的时间则本车会加入车队。 否则是车头。 故只需要记录之前车辆的最晚到达时间不需要单调栈。 如果需要计算撞的那辆车则需要用单调栈记录各车时间 如果后面的车到达时间前面车的到达时间则前面的车永远不再会成为车头故淘汰之。淘汰后单调栈降序记录到达时间。处理完当前车队后如果栈为空则是车头。时间相等无需特殊处理。
代码
核心代码
class Solution {public:int carFleet(int target, vectorint position, vectorint speed) {const int N position.size();vectorint indexs(N);iota(indexs.begin(), indexs.end(), 0);sort(indexs.begin(), indexs.end(), [](const int i1, const int i2) {return position[i1] position[i2]; });double maxTime 0;int ret 0;for (const auto i : indexs) {double cur (target - (double)position[i]) / speed[i];ret (cur maxTime);maxTime max(maxTime, cur);}return ret;}};单元测试 int target;vectorint position, speed;TEST_METHOD(TestMethod1){target 12, position { 8,10 }, speed { 4,2 };auto res Solution().carFleet(target, position, speed);AssertEx(1, res);}TEST_METHOD(TestMethod11){target 12, position { 10,8,0,5,3 }, speed { 2,4,1,1,3 };auto res Solution().carFleet(target, position, speed);AssertEx(3, res);}TEST_METHOD(TestMethod12){target 10, position { 3 }, speed { 3 };auto res Solution().carFleet(target, position, speed);AssertEx(1, res);}TEST_METHOD(TestMethod13){target 100, position { 0,2,4 }, speed { 4,2,1 };auto res Solution().carFleet(target, position, speed);AssertEx(1, res);}扩展阅读
我想对大家说的话工作中遇到的问题可以按类别查阅鄙人的算法文章请点击《算法与数据汇总》。学习算法按章节学习《喜缺全书算法册》大量的题目和测试用例打包下载。重视操作有效学习明确的目标 及时的反馈 拉伸区难度合适 专注闻缺陷则喜(喜缺)是一个美好的愿望早发现问题早修改问题给老板节约钱。子墨子言之事无终始无务多业。也就是我们常说的专业的人做专业的事。如果程序是一条龙那算法就是他的是睛失败反思成功 成功反思成功
视频课程
先学简单的课程请移步CSDN学院听白银讲师也就是鄙人的讲解。 https://edu.csdn.net/course/detail/38771 如何你想快速形成战斗了为老板分忧请学习C#入职培训、C入职培训等课程 https://edu.csdn.net/lecturer/6176
测试环境
操作系统win7 开发环境 VS2019 C17 或者 操作系统win10 开发环境 VS2022 C17 如无特殊说明本算法用**C**实现。
