【LeetCode】870 . 优势洗牌
870 . 优势洗牌



方法:贪心
思路
-
这道题的思想类似于 “田忌赛马” ,把 nums1 当成是田忌的马,nums2 当成是齐威王的马。
-
讨论田忌的下等马(nums1 的最小值):
- 如果它能比过齐威王的下等马(nums2 的最小值),那这一分田忌直接拿下;
- 如果它比不过齐威王的下等马,则用田忌的下等马比齐威王的上等马(nums2 的最大值)。
-
去掉这两匹马,问题变成一个规模更小(n−1 )的子问题。重复上述过程,即得到了所有马的对应关系。
-
代码实现时,直接对 nums1 进行排序,由于我们后续还需用用到 nums2 的下标,因此不能直接对 nums2 排序。而是用 multiset 来保存 nums2 的值和下标,同时,该数据结构会对 nums2 自动排序(从小到大),且允许存在重复值。
-
注意:erase函数的使用
void erase ( iterator position ),它的参数只能是正向迭代器,我一开始使用了 rbegin() 用于删除最后一个值,而 rbegin 的类型是 reverse_iterator ,所以一直出错。
代码
class Solution {
public:vector<int> advantageCount(vector<int>& nums1, vector<int>& nums2) {// 创建一个答案数组vector<int> ans(nums1.size());// 先将nums1重新排序sort(nums1.begin(), nums1.end());// 创建一个多重映射,从小到大保存nums2的值及其下标// 这里需要使用multimap,因为nums2中可能存在重复的值multimap<int, int> mp;for(int i=0; i<nums2.size(); ++i){mp.insert({nums2[i], i});}for(int i=0; i<nums1.size(); ++i){// "田忌赛马" 如果nums1的最小值大于nums2的最小值,就以此赢他if(nums1[i] > mp.begin()->first){ans[mp.begin()->second] = nums1[i];mp.erase(mp.begin());}// 否则就用nums1的最小值和nums2的最大值相比else{ans[mp.rbegin()->second] = nums1[i];mp.erase(--mp.end());} }return ans;}
};
参考文献
- 田忌赛马(Python/Java/C++/Go)
相关文章:
【LeetCode】870 . 优势洗牌
870 . 优势洗牌 方法:贪心 思路 这道题的思想类似于 “田忌赛马” ,把 nums1 当成是田忌的马,nums2 当成是齐威王的马。 讨论田忌的下等马(nums1 的最小值): 如果它能比过齐威王的下等马(nums…...
现代C++中的从头开始深度学习【2/8】:张量编程
一、说明 初学者文本:此文本需要入门级编程背景和对机器学习的基本了解。张量是在深度学习算法中表示数据的主要方式。它们广泛用于在算法执行期间实现输入、输出、参数和内部状态。 在这个故事中,我们将学习如何使用特征张量 API 来开发我们的C算法。具…...
uniapp软键盘谈起遮住输入框和头部被顶起的问题解决
推荐: pages.json中配置如下可解决头部被顶起和表单被遮住的问题。 { "path": "pages/debug/protocol/tagWord", "style": { "app-plus": { "soft…...
安防监控视频汇聚EasyCVR平台的FLV视频流在VLC中无法播放的原因排查
众所周知,TSINGSEE青犀视频汇聚平台EasyCVR可支持多协议方式接入,包括主流标准协议国标GB28181、RTSP/Onvif、RTMP等,以及厂家私有协议与SDK接入,包括海康Ehome、海大宇等设备的SDK等。在视频流的处理与分发上,视频监控…...
虹科新闻 | 虹科与Power-MI正式建立合作伙伴关系
近日,虹科与Power-MI正式建立合作伙伴关系,双方就工业预测性维护领域进行深入的交流与合作,未来将共同致力于为亚洲市场提供完整的、更高质量的预测性维护解决方案,解决亚洲客户的工业自动化挑战。 虹科与Power-MI都表示十分期待…...
Xamarin.Android实现加载中的效果
目录 1、说明2、代码如下2.1 图1的代码2.1.1、创建一个Activity或者Fragment,如下:2.1.2、创建Layout2.1.3、如何使用 2.2 图2的代码 4、其他补充4.1 C#与Java中的匿名类4.2 、其他知识点 5、参考资料 1、说明 在实际使用过程中,常常会用到点…...
Leetcode.1559 二维网格图中探测环
题目链接 Leetcode.1559 二维网格图中探测环 rating : 1838 题目描述 给你一个二维字符网格数组 g r i d grid grid ,大小为 m x n ,你需要检查 g r i d grid grid 中是否存在 相同值 形成的环。 一个环是一条开始和结束于同一个格子的长度 大于等于…...
阿拉伯数字转中文数字字符,最高支持千京
直接上代码 UtilityClass public class NumberFormatUtil {/** 中文 -> 数字对应关系 */private static final Map<Character, Integer> DIGIT_CHINA new HashMap<>();/** 数字 -> 中文对应关系 */private static final Map<Integer, Character> DIGI…...
Python基础--序列操作/函数
Python基础 1.序列的操作 2.函数 1. 数据类型的具体操作 1.1 序列操作--列表具体操作: #定义列表 listA [] #定义一个空列表 listB [1,2.8,"你好",listA,[1,2,3]] # 访问列表 print(listB)#查看整个列表 print(listB[2])#查看单个…...
Kafka与Zookeeper版本对应关系
文章目录 了解版本对应Kafka安装包Kafka源码包 了解 比如: kafka_2.11-1.1.1.jar包 其中2.11表示的是Scala的版本,因为Kafka服务器端代码完全由Scala语音编写。”-“后面的1.1.1表示的kafka的版本信息。遵循一个基本原则,Kafka客户端版本和服…...
Arch Linux 使用桥接模式上网
如果我们想要将虚拟机与物理主机同一网段,并且像物理机器一样被其他设备访问,则需要以桥接模式上网,这个时候,物理主机就必须配置为使用网桥上网了。 注意:这里我们使用了 NetworkManager 网络管理工具中的 nmcli 来进…...
Vue 中使用 WebWorker
目录 安装 loader 应用场景 打包时错误处理 安装 loader npm install worker-loader -D 如果直接把worker.js放到public目录下,则不需要安装loader vue.config.js const { defineConfig } require(vue/cli-service)module.exports defineConfig({transpileDe…...
财务管理系统javaweb会计账房进销存jsp源代码mysql
本项目为前几天收费帮学妹做的一个项目,Java EE JSP项目,在工作环境中基本使用不到,但是很多学校把这个当作编程入门的项目来做,故分享出本项目供初学者参考。 一、项目描述 财务管理系统javaweb java,Struts2,bootstrap,mysql,…...
企业服务器被devos勒索病毒攻击后怎么处理,devos勒索病毒如何攻击的
众所周知,科学技术是第一生产力,科学技术的发展给企业与人们的生活带来了极大变化,但随之而来的网络安全威胁也不断增加。最近,我们收到很多企业的求助,企业的计算机服务器遭到了devos勒索病毒的攻击,导致企…...
React源码解析18(2)------ FilberNode,FilberRootNode结构关系
摘要 在上一篇,我们实现了通过JSX转换为ReactElement的方法,也看到了转换后React元素的结构。但是这个React元素,并不能很清楚的表达组件之间的关系,以及属性的处理。 所以在React内部,会将所有的React元素转换为Fil…...
什么是Session?它在SQLAlchemy中扮演什么角色?
让我们先来谈谈什么是“Session”。在你逛超市或者餐厅的时候,你可能会遇到一种叫做“前台”的东西。你知道那是干什么的吗?它是用来暂存你买的东西,这样你就可以从容地结账,而不必抱着满满一购物车的商品。 数据库的“Session”…...
Java 中 Set集合常用方法
.add() 添加元素 对象名.add() 向Set集合中添加元素 (但不能添加重复元素,Set集合中不允许元素重复) Set<String> s new HashSet<String>(); // 添加数据 s.add("aaa"); s.add("bbb"); addAll(Collectio…...
(MVC)SpringBoot+Mybatis+Mapper.xml
前言:本篇博客主要对MVC架构、Mybatis工程加深下理解,前面写过一篇博客:SprintBoothtml/css/jsmybatis的demo,里面涉及到了Mybatis的应用,此篇博客主要介绍一种将sql语句写到了配置文件里的方法,即Mybatis里…...
【Linux命令行与Shell脚本编程】第十九章 正则表达式
Linux命令行与Shell脚本编程 第十九章 正则表达式 文章目录 Linux命令行与Shell脚本编程 第十九章 正则表达式九.正则表达式9.1.正则表达式基础9.1.1.正则表达式的类型9.2.定义BRE模式9.2.1.普通文本9.2.2.特殊字符 9.2.3.锚点字符锚定行首^锚定行尾$组合锚点 9.2.4.点号字符\.…...
vue exceljs 实现导出excel并设置网格线、背景色、 垂直居中、分页打印
一、 下载 exceljs pnpm install exceljs二、 页面中使用 // 导出 exportExcelexportToExcel() {this.$confirm("此操作将导出excel文件, 是否继续?", "提示", {confirmButtonText: "确定",cancelButtonText: "取消",type: "wa…...
KubeSphere 容器平台高可用:环境搭建与可视化操作指南
Linux_k8s篇 欢迎来到Linux的世界,看笔记好好学多敲多打,每个人都是大神! 题目:KubeSphere 容器平台高可用:环境搭建与可视化操作指南 版本号: 1.0,0 作者: 老王要学习 日期: 2025.06.05 适用环境: Ubuntu22 文档说…...
业务系统对接大模型的基础方案:架构设计与关键步骤
业务系统对接大模型:架构设计与关键步骤 在当今数字化转型的浪潮中,大语言模型(LLM)已成为企业提升业务效率和创新能力的关键技术之一。将大模型集成到业务系统中,不仅可以优化用户体验,还能为业务决策提供…...
【Linux】shell脚本忽略错误继续执行
在 shell 脚本中,可以使用 set -e 命令来设置脚本在遇到错误时退出执行。如果你希望脚本忽略错误并继续执行,可以在脚本开头添加 set e 命令来取消该设置。 举例1 #!/bin/bash# 取消 set -e 的设置 set e# 执行命令,并忽略错误 rm somefile…...
Xshell远程连接Kali(默认 | 私钥)Note版
前言:xshell远程连接,私钥连接和常规默认连接 任务一 开启ssh服务 service ssh status //查看ssh服务状态 service ssh start //开启ssh服务 update-rc.d ssh enable //开启自启动ssh服务 任务二 修改配置文件 vi /etc/ssh/ssh_config //第一…...
边缘计算医疗风险自查APP开发方案
核心目标:在便携设备(智能手表/家用检测仪)部署轻量化疾病预测模型,实现低延迟、隐私安全的实时健康风险评估。 一、技术架构设计 #mermaid-svg-iuNaeeLK2YoFKfao {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg…...
解锁数据库简洁之道:FastAPI与SQLModel实战指南
在构建现代Web应用程序时,与数据库的交互无疑是核心环节。虽然传统的数据库操作方式(如直接编写SQL语句与psycopg2交互)赋予了我们精细的控制权,但在面对日益复杂的业务逻辑和快速迭代的需求时,这种方式的开发效率和可…...
Axios请求超时重发机制
Axios 超时重新请求实现方案 在 Axios 中实现超时重新请求可以通过以下几种方式: 1. 使用拦截器实现自动重试 import axios from axios;// 创建axios实例 const instance axios.create();// 设置超时时间 instance.defaults.timeout 5000;// 最大重试次数 cons…...
12.找到字符串中所有字母异位词
🧠 题目解析 题目描述: 给定两个字符串 s 和 p,找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义: 若两个字符串包含的字符种类和出现次数完全相同,顺序无所谓,则互为…...
Springboot社区养老保险系统小程序
一、前言 随着我国经济迅速发展,人们对手机的需求越来越大,各种手机软件也都在被广泛应用,但是对于手机进行数据信息管理,对于手机的各种软件也是备受用户的喜爱,社区养老保险系统小程序被用户普遍使用,为方…...
SAP学习笔记 - 开发26 - 前端Fiori开发 OData V2 和 V4 的差异 (Deepseek整理)
上一章用到了V2 的概念,其实 Fiori当中还有 V4,咱们这一章来总结一下 V2 和 V4。 SAP学习笔记 - 开发25 - 前端Fiori开发 Remote OData Service(使用远端Odata服务),代理中间件(ui5-middleware-simpleproxy)-CSDN博客…...
