上上佳食品 网站建设,自媒体wordpress主题,湖南太平洋建设集团网站,北京房产网站建设本文涉及的基础知识点
排序 C算法#xff1a;滑动窗口及双指针总结
本题其它解法
【C单调栈 排序】1996. 游戏中弱角色的数量|1996
LeetCode1996. 游戏中弱角色的数量
你正在参加一个多角色游戏#xff0c;每个角色都有两个主要属性#xff1a;攻击 和 防御 。给你一个…本文涉及的基础知识点
排序 C算法滑动窗口及双指针总结
本题其它解法
【C单调栈 排序】1996. 游戏中弱角色的数量|1996
LeetCode1996. 游戏中弱角色的数量
你正在参加一个多角色游戏每个角色都有两个主要属性攻击 和 防御 。给你一个二维整数数组 properties 其中 properties[i] [attacki, defensei] 表示游戏中第 i 个角色的属性。 如果存在一个其他角色的攻击和防御等级 都严格高于 该角色的攻击和防御等级则认为该角色为 弱角色 。更正式地如果认为角色 i 弱于 存在的另一个角色 j 那么 attackj attacki 且 defensej defensei 。 返回 弱角色 的数量。 示例 1 输入properties [[5,5],[6,3],[3,6]] 输出0 解释不存在攻击和防御都严格高于其他角色的角色。 示例 2 输入properties [[2,2],[3,3]] 输出1 解释第一个角色是弱角色因为第二个角色的攻击和防御严格大于该角色。 示例 3 输入properties [[1,5],[10,4],[4,3]] 输出1 解释第三个角色是弱角色因为第二个角色的攻击和防御严格大于该角色。 提示 2 properties.length 105 properties[i].length 2 1 attacki, defensei 105
排序双指针
i从大到小处理第i个角色attack[j] attack[i]且j最小。 maxDefen 是defen[j…n-1]的最大值。 由于attack是升序,如果attack[j] attack[i]。 性质一x j 则attack[x] attack[i]。 性质二x j attack[j-1] attack[i]则attack[x] attack[j]。 根据性质一和性质二有且只有 [j…n-1]的攻击大于i。 性质三x i → \rightarrow → attack[x] attack[j]。 ⟺ \iff ⟺ 随着i变小j不会被移除。 时间复杂度O(nlogn) 瓶颈在排序
代码
核心代码
class Solution {public:int numberOfWeakCharacters(vectorvectorint properties) {sort(properties.begin(), properties.end());int maxD 0;const int N properties.size();int ans 0;for (int i N - 1, j N; i 0; i--) {while (j (properties[j-1][0] properties[i][0])) {maxD max(maxD, properties[--j][1]);}ans properties[i][1] maxD;}return ans;}};单元测试 vectorvectorint properties;TEST_METHOD(TestMethod11){properties { {5,5},{6,3},{3,6} };auto res Solution().numberOfWeakCharacters(properties);AssertEx(0, res);}TEST_METHOD(TestMethod12){properties { {2,2},{3,3} };auto res Solution().numberOfWeakCharacters(properties);AssertEx(1, res);}TEST_METHOD(TestMethod13){properties { {1,5},{10,4},{4,3} };auto res Solution().numberOfWeakCharacters(properties);AssertEx(1, res);}TEST_METHOD(TestMethod14){properties { {1,1},{2,1},{2,2},{1,2} };auto res Solution().numberOfWeakCharacters(properties);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**实现。
