建设文明网站包括哪些内容,专门做拼花网站,西安网页设计培训班价格,青岛做网站需要多少钱本文涉及知识点
栈
LeetCode2751. 机器人碰撞
现有 n 个机器人#xff0c;编号从 1 开始#xff0c;每个机器人包含在路线上的位置、健康度和移动方向。 给你下标从 0 开始的两个整数数组 positions、healths 和一个字符串 directions#xff08;directions[i] 为 ‘L’ …本文涉及知识点
栈
LeetCode2751. 机器人碰撞
现有 n 个机器人编号从 1 开始每个机器人包含在路线上的位置、健康度和移动方向。 给你下标从 0 开始的两个整数数组 positions、healths 和一个字符串 directionsdirections[i] 为 ‘L’ 表示 向左 或 ‘R’ 表示 向右。 positions 中的所有整数 互不相同 。 所有机器人以 相同速度 同时 沿给定方向在路线上移动。如果两个机器人移动到相同位置则会发生 碰撞 。 如果两个机器人发生碰撞则将 健康度较低 的机器人从路线中 移除 并且另一个机器人的健康度 减少 1 。幸存下来的机器人将会继续沿着与之前 相同 的方向前进。如果两个机器人的健康度相同则将二者都从路线中移除。 请你确定全部碰撞后幸存下的所有机器人的 健康度 并按照原来机器人编号的顺序排列。即机器人 1 如果幸存的最终健康度机器人 2 如果幸存的最终健康度等。 如果不存在幸存的机器人则返回空数组。 在不再发生任何碰撞后请你以数组形式返回所有剩余机器人的健康度按机器人输入中的编号顺序。 注意位置 positions 可能是乱序的。
示例 1 输入positions [5,4,3,2,1], healths [2,17,9,15,10], directions “RRRRR” 输出[2,17,9,15,10] 解释在本例中不存在碰撞因为所有机器人向同一方向移动。所以从第一个机器人开始依序返回健康度[2, 17, 9, 15, 10] 。 示例 2
输入positions [3,5,2,6], healths [10,10,15,12], directions “RLRL” 输出[14] 解释本例中发生 2 次碰撞。首先机器人 1 和机器人 2 将会碰撞因为二者健康度相同二者都将被从路线中移除。接下来机器人 3 和机器人 4 将会发生碰撞由于机器人 4 的健康度更小则它会被移除而机器人 3 的健康度变为 15 - 1 14 。仅剩机器人 3 所以返回 [14] 。 示例 3 输入positions [1,2,5,6], healths [10,10,11,11], directions “RLRL” 输出[] 解释机器人 1 和机器人 2 将会碰撞因为二者健康度相同二者都将被从路线中移除。机器人 3 和机器人 4 将会碰撞因为二者健康度相同二者都将被从路线中移除。所以返回空数组 [] 。
提示
1 positions.length healths.length directions.length n 105 1 positions[i], healths[i] 109 directions[i] ‘L’ 或 directions[i] ‘R’ positions 中的所有值互不相同
栈
向右的机器人入栈下标、健康度处理向左的机器人。 如果栈用向量v1模拟更简洁为空则将当前机器人放到v2中否则循环处理 如果栈顶元素的健康度和当前机器人的健康度相等出栈循环结束。 如果小于 ⋯ \cdots ⋯ ,出栈当前机器人健康减1。机器人至少健康1大于说明至少2减少1后至少1。 如果大于栈顶机器人健康度减少1。循环结束。 对v1 和 v2合并并排序到v3。 复制v3的健康度到结果。 注意不能用归并排序因为i并不是升序pos[i]才是升序。
代码
核心代码
class Solution {
public:vectorint survivedRobotsHealths(vectorint positions, vectorint healths, string directions) {vectorint indexs(positions.size());iota(indexs.begin(), indexs.end(), 0);sort(indexs.begin(), indexs.end(), [](int i1, int i2) {return positions[i1] positions[i2]; });vectorpairint, int v1, v2;for (int i : indexs) {if (R directions[i]) {v1.emplace_back(pairint, int{ i, healths[i] }); continue;}int hea healths[i];while (v1.size() (hea 0)) {if (v1.back().second hea) {v1.pop_back();hea -1;}else if (v1.back().second hea){v1.pop_back();hea--;}else {v1.back().second--;hea -1;}}if (hea 0) {v2.emplace_back(make_pair(i, hea));}}auto v3 v1;v3.insert(v3.end(), v2.begin(), v2.end());sort(v3.begin(), v3.end());vectorint ret; for (const auto [tmp, hea] : v3) {ret.emplace_back(hea);}return ret;}
};单元测试
templateclass T1,class T2
void AssertEx(const T1 t1, const T2 t2)
{Assert::AreEqual(t1 , t2);
}templateclass T
void AssertEx(const vectorT v1, const vectorT v2)
{Assert::AreEqual(v1.size(), v2.size()); for (int i 0; i v1.size(); i){Assert::AreEqual(v1[i], v2[i]);}
}templateclass T
void AssertV2(vectorvectorT vv1, vectorvectorT vv2)
{sort(vv1.begin(), vv1.end());sort(vv2.begin(), vv2.end());Assert::AreEqual(vv1.size(), vv2.size());for (int i 0; i vv1.size(); i){AssertEx(vv1[i], vv2[i]);}
}namespace UnitTest
{vectorint positions;vectorint healths;string directions;TEST_CLASS(UnitTest){public:TEST_METHOD(TestMethod0){positions { 5,4,3,2,1 }, healths { 2,17,9,15,10 }, directions RRRRR;auto res Solution().survivedRobotsHealths(positions, healths, directions);AssertEx({ 2,17,9,15,10 },res);}TEST_METHOD(TestMethod00){positions { 5,4,3,2,1 }, healths { 2,17,9,15,10 }, directions LLLLL;auto res Solution().survivedRobotsHealths(positions, healths, directions);AssertEx({ 2,17,9,15,10 }, res);}TEST_METHOD(TestMethod1){positions { 3,5,2,6 }, healths { 10,10,15,12 }, directions RLRL;auto res Solution().survivedRobotsHealths(positions, healths, directions);AssertEx({14 }, res);}TEST_METHOD(TestMethod2){positions { 1,2,5,6 }, healths { 10,10,11,11 }, directions RLRL;auto res Solution().survivedRobotsHealths(positions, healths, directions);AssertEx({ }, res);} };
}扩展阅读
视频课程
有效学习明确的目标 及时的反馈 拉伸区难度合适可以先学简单的课程请移步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 如无特殊说明本算法用**C**实现。
