【C++排序 双指针】1996. 游戏中弱角色的数量|1996
本文涉及的基础知识点
排序
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(vector<vector<int>>& 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;}};
单元测试
vector<vector<int>> 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 C++17
或者 操作系统:win10 开发环境: VS2022 C++17
如无特殊说明,本算法用**C++**实现。

相关文章:
【C++排序 双指针】1996. 游戏中弱角色的数量|1996
本文涉及的基础知识点 排序 C算法:滑动窗口及双指针总结 本题其它解法 【C单调栈 排序】1996. 游戏中弱角色的数量|1996 LeetCode1996. 游戏中弱角色的数量 你正在参加一个多角色游戏,每个角色都有两个主要属性:攻击 和 防御 。给你一个…...
GESP4级考试语法知识(捕捉异常)
参考程序代码: #include <iostream> using namespace std;double divide(double a, double b) {if (b 0) {throw "Division by zero error"; // 抛出异常}return a / b; }int main() {double num1, num2;cout << "Enter two numbers:…...
HTML 基础标签——元数据标签 <meta>
文章目录 1. `<meta>` 标签概述2. 属性详解2.1 `charset` 属性2.2 `name` 属性2.3 `content` 属性2.4 `http-equiv` 属性3. 其他常见属性小结在 HTML 文档中,元数据标签 <meta> 是一种重要的标签,用于提供关于文档的信息,这些信息不直接显示在网页内容中,但对于…...
栈虚拟机和寄存器虚拟机,有什么不同?
本来这节内容是打算直接讲字节码指令的,但讲之前又必须得先讲指令集架构,而指令集架构又分为两种,一种是基于栈的,一种是基于寄存器的。 那不妨我们这节就单独来讲讲栈虚拟机和寄存器虚拟机,它们有什么不同࿰…...
Windows下基于fping进行批量IP测试
fping是Linux下一个很好用的IP测试工具,结合代码可以完成批量的IP测试,在网络调试中用途很广。本文是基于fping for Windows结合bat批处理,定制的测试脚本样例。 一、程序信息 本次测试使用fpingV5.1 for Windows版,版本信息如下…...
一款实用的Word文档图片转换与水印保护工具
目录 前言软件功能简介软件实现方法及关键代码 1. Word 文档转图片的实现2. 图片水印添加功能3. 生成数字指纹(哈希值)4. 保存图片信息到 JSON 文件 软件的实际使用场景软件操作指南 1. 下载和安装2. 操作流程 总结 1,前言 在日常办公和内…...
优化用于传感应用的衬底集成波导技术
ANSYS HFSS 是一款功能强大的电磁仿真软件,支持为微流体生物传感器应用设计和分析衬底集成波导 (SIW) 技术。它为快速设计优化、材料选择、系统集成和虚拟原型制作提供了一个强大的平台。借助 ANSYS HFSS,研究人员和工程师可以高效…...
Java多态特性的向上转型
Java的多态特性通过向上转型来实现。向上转型指的是将子类对象赋值给父类引用变量的操作。这样做的好处是可以使用父类引用变量来调用子类对象的方法。 例如,有一个父类Animal和一个子类Dog,可以这样进行向上转型: Animal animal new Dog(…...
C++ 判断语句的深入解析
C 判断语句的深入解析 C 是一种广泛使用的编程语言,以其高效性和灵活性著称。在 C 中,判断语句是控制程序流程的关键组成部分,它们允许程序根据不同的条件执行不同的代码路径。本文将深入探讨 C 中的判断语句,包括 if、else if、…...
15分钟学 Go 第 33 天:项目结构
第33天:项目结构 目标:了解Go项目的典型结构 在Go语言的开发中,项目结构的合理性直接影响着代码的可维护性、可扩展性和团队协作效率。本篇文章将深入探讨Go语言的典型项目结构,并提供实际示例代码和相关的流程图。 一、Go项目…...
conda迁移虚拟环境路径
方法一:使用软连接 ln -s ~/Anaconda3/envs /new/path/envs 方法二:修改~/.condarc文件 1.打开~/.condarc文件 #添加下面参数 envs_dirs: - /newpath/anaconda3/envs pkgs_dirs: - /newpath/anaconda3/pkgs 2. source ~/.bashrc 3.查看是否成功con…...
(八)JavaWeb后端开发——Tomcat
目录 1.Web服务器概念 2.tomcat 1.Web服务器概念 服务器:安装了服务器软件的计算机服务器软件:接收用户的请求,处理请求,做出响应web服务器软件:在web服务器软件中,可以部署web项目,让用户通…...
yocto中通常不直接修改提供的recipes的bb文件
不直接在 Yocto 官方提供的 recipe 中修改 通常是创建新的 metadata 和 recipe 来配置相关软件编译等过程 主要有以下几个原因: 1. 便于维护和升级 隔离自定义修改:Yocto 官方的 recipe 可能会随着版本更新而变化。如果直接修改官方 recipe࿰…...
智能座舱相关术语全解及多模态交互在智能座舱中的应用
文章目录 座舱相关术语全解1. 智能座舱2. UFS3. 多模态交互4. 3D虚拟引擎5. AR/VR6. GNSS7. TTS8. DPU9. 摄像头10. 屏幕/显示器11. 音频12. 无线连接13. 其他组件 多模态交互在智能座舱中有以下一些应用 座舱相关术语全解 1. 智能座舱 智能座舱(intelligent cabi…...
【Fastjson反序列化漏洞:深入了解与防范】
一、Fastjson反序列化漏洞概述 Fastjson是一款高性能的Java语言JSON处理库,广泛应用于Web开发、数据交换等领域。然而,由于fastjson在解析JSON数据时存在安全漏洞,攻击者可以利用该漏洞执行任意代码,导致严重的安全威胁。 二、F…...
【OJ题解】C++实现反转字符串中的每个单词
💵个人主页: 起名字真南 💵个人专栏:【数据结构初阶】 【C语言】 【C】 【OJ题解】 题目要求:给定一个字符串 s ,你需要反转字符串中每个单词的字符顺序,同时仍保留空格和单词的初始顺序。 题目链接: 反转字符串中的所…...
万字长文详解Hive聚合函数 grouping sets、cube、rollup原理、语法、案例和优化
目录 原理与语法 使用场景 多维度报表生成 复杂的数据分析 实际案例 原理与语法 与GROUPINGSETS的区别 实际案例 原理与语法 与CUBE的对比 实际案例 执行效率比较 优化建议 Hive提供了三个强大的高级聚合函数: GROUPING SETS 、 CUBE 和 ROLLUP ,用于处理复杂的…...
数列分块入门
本期是数列分块入门。其中的大部分题目来自hzwer在LOJ上提供的数列分块入门系列。 Blog:here (其实是对之前分块的 blog 的整理补充) sto hzwer orz %%% [转载] ---------------------------------------------------------------------------------…...
SPRD Android 14 Launcher 3 中添加长按桌面图标启动自由窗口模式功能
本文将介绍如何在SPRD Android 14 Launcher 3 中实现一个功能,使用户可以通过长按应用图标来启动自由窗口模式。这一功能的实现将提升多任务处理能力和应用使用体验。 修改的文件列表 以下是主要涉及的文件及其修改内容: QuickstepLauncher.java:添加自由窗口快捷方式的支…...
WebSocket详解:从前端到后端的全栈理解
文章目录 前言一、WebSocket简介1.1 WebSocket的特点 二、WebSocket的工作原理2.1 握手过程2.2 数据传输 三、WebSocket在前端的应用四、WebSocket在后端的应用五、WebSocket的局限与解决方案结语 前言 随着互联网技术的发展,传统的HTTP协议在某些场景下的局限性逐…...
别再手动画流程图了!用Flowable 6.8.1 + SpringBoot 3分钟搞定请假审批系统
3分钟集成Flowable 6.8.1:SpringBoot请假审批系统实战指南 当团队需要快速上线一个请假审批模块时,传统开发方式往往需要编写大量状态流转代码。去年我们团队就遇到过这种情况——产品经理突然要求三天内上线OA系统的请假功能,而当时我们连数…...
Element-UI+Axios:如何优雅处理Vue异步请求的Loading状态?
Element-UIAxios:企业级后台系统的Loading状态高阶实践 在数据密集型的后台管理系统开发中,异步请求的状态反馈直接影响用户体验。当页面需要同时处理数十个表单提交、图表数据加载和批量操作时,如何避免Loading状态的混乱闪烁?怎…...
MySQL 8.0在麒麟系统安装后,别忘了这几步:改密码、开远程、设自启
MySQL 8.0在麒麟系统安装后的关键配置指南 当你成功在麒麟V10 SP3系统上安装了MySQL 8.0数据库后,真正的挑战才刚刚开始。许多初学者往往忽视了安装后的关键配置步骤,导致数据库安全性不足或功能受限。本文将带你深入了解如何正确完成这些关键配置&…...
Symfony Doctrine Bridge 编译器传递深度解析:RegisterMappingsPass 与 RegisterUidTypePass 源码解读
Symfony Doctrine Bridge 编译器传递深度解析:RegisterMappingsPass 与 RegisterUidTypePass 源码解读 【免费下载链接】doctrine-bridge Provides integration for Doctrine with various Symfony components 项目地址: https://gitcode.com/gh_mirrors/do/doctr…...
SillyTavern角色系统全解析:从基础构建到高级定制
SillyTavern角色系统全解析:从基础构建到高级定制 【免费下载链接】SillyTavern LLM Frontend for Power Users. 项目地址: https://gitcode.com/GitHub_Trending/si/SillyTavern 引言:当AI角色拥有"灵魂" 想象一下,你正在…...
PHP 中的文件读写与上传
PHP 中的文件读写与上传 判断与信息获取 判断文件函数说明返回值file_exists($path)判断文件或目录是否存在boolis_file($path)判断是否是文件boolis_dir($path)判断是否是目录boolis_readable($path)判断是否可读boolis_writable($path)判断是否可写bool<?php $file ./co…...
提示词工程的应用解析
提示词工程全解析:从入门到精通,让AI精准读懂你的需求[TOC](提示词工程全解析:从入门到精通,让AI精准读懂你的需求)提示词工程全解析:从入门到精通,让AI精准读懂你的需求一、引言:为什么提示词工…...
4大维度优化Windows 11:给专业用户的系统减负指南
4大维度优化Windows 11:给专业用户的系统减负指南 【免费下载链接】Win11Debloat 一个简单的PowerShell脚本,用于从Windows中移除预装的无用软件,禁用遥测,从Windows搜索中移除Bing,以及执行各种其他更改以简化和改善你…...
dry快速入门:10个核心功能带你玩转Docker管理
dry快速入门:10个核心功能带你玩转Docker管理 【免费下载链接】dry moncho/dry: dry(Docker Run Commands)是一款命令行工具,旨在简化对Docker容器的操作管理,提供了一种简洁的方式创建、启动、停止和删除Docker容器。…...
BabelDOC终极指南:如何完美翻译PDF学术论文并保持原格式
BabelDOC终极指南:如何完美翻译PDF学术论文并保持原格式 【免费下载链接】BabelDOC Yet Another Document Translator 项目地址: https://gitcode.com/GitHub_Trending/ba/BabelDOC 还在为PDF翻译后格式混乱而烦恼吗?BabelDOC为您提供了一站式解决…...
