当前位置: 首页 > news >正文

【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;}
};

参考文献

  1. 田忌赛马(Python/Java/C++/Go)

相关文章:

【LeetCode】870 . 优势洗牌

870 . 优势洗牌 方法&#xff1a;贪心 思路 这道题的思想类似于 “田忌赛马” &#xff0c;把 nums1 当成是田忌的马&#xff0c;nums2 当成是齐威王的马。 讨论田忌的下等马&#xff08;nums1 的最小值&#xff09;&#xff1a; 如果它能比过齐威王的下等马&#xff08;nums…...

现代C++中的从头开始深度学习【2/8】:张量编程

一、说明 初学者文本&#xff1a;此文本需要入门级编程背景和对机器学习的基本了解。张量是在深度学习算法中表示数据的主要方式。它们广泛用于在算法执行期间实现输入、输出、参数和内部状态。 在这个故事中&#xff0c;我们将学习如何使用特征张量 API 来开发我们的C算法。具…...

uniapp软键盘谈起遮住输入框和头部被顶起的问题解决

推荐&#xff1a; pages.json中配置如下可解决头部被顶起和表单被遮住的问题。 { "path": "pages/debug/protocol/tagWord", "style": { "app-plus": { "soft…...

安防监控视频汇聚EasyCVR平台的FLV视频流在VLC中无法播放的原因排查

众所周知&#xff0c;TSINGSEE青犀视频汇聚平台EasyCVR可支持多协议方式接入&#xff0c;包括主流标准协议国标GB28181、RTSP/Onvif、RTMP等&#xff0c;以及厂家私有协议与SDK接入&#xff0c;包括海康Ehome、海大宇等设备的SDK等。在视频流的处理与分发上&#xff0c;视频监控…...

虹科新闻 | 虹科与Power-MI正式建立合作伙伴关系

近日&#xff0c;虹科与Power-MI正式建立合作伙伴关系&#xff0c;双方就工业预测性维护领域进行深入的交流与合作&#xff0c;未来将共同致力于为亚洲市场提供完整的、更高质量的预测性维护解决方案&#xff0c;解决亚洲客户的工业自动化挑战。 虹科与Power-MI都表示十分期待…...

Xamarin.Android实现加载中的效果

目录 1、说明2、代码如下2.1 图1的代码2.1.1、创建一个Activity或者Fragment&#xff0c;如下&#xff1a;2.1.2、创建Layout2.1.3、如何使用 2.2 图2的代码 4、其他补充4.1 C#与Java中的匿名类4.2 、其他知识点 5、参考资料 1、说明 在实际使用过程中&#xff0c;常常会用到点…...

Leetcode.1559 二维网格图中探测环

题目链接 Leetcode.1559 二维网格图中探测环 rating : 1838 题目描述 给你一个二维字符网格数组 g r i d grid grid &#xff0c;大小为 m x n &#xff0c;你需要检查 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 序列操作--列表具体操作&#xff1a; #定义列表 listA [] #定义一个空列表 listB [1,2.8,"你好",listA,[1,2,3]] # 访问列表 print(listB)#查看整个列表 print(listB[2])#查看单个…...

Kafka与Zookeeper版本对应关系

文章目录 了解版本对应Kafka安装包Kafka源码包 了解 比如&#xff1a; kafka_2.11-1.1.1.jar包 其中2.11表示的是Scala的版本&#xff0c;因为Kafka服务器端代码完全由Scala语音编写。”-“后面的1.1.1表示的kafka的版本信息。遵循一个基本原则&#xff0c;Kafka客户端版本和服…...

Arch Linux 使用桥接模式上网

如果我们想要将虚拟机与物理主机同一网段&#xff0c;并且像物理机器一样被其他设备访问&#xff0c;则需要以桥接模式上网&#xff0c;这个时候&#xff0c;物理主机就必须配置为使用网桥上网了。 注意&#xff1a;这里我们使用了 NetworkManager 网络管理工具中的 nmcli 来进…...

Vue 中使用 WebWorker

目录 安装 loader 应用场景 打包时错误处理 安装 loader npm install worker-loader -D 如果直接把worker.js放到public目录下&#xff0c;则不需要安装loader vue.config.js const { defineConfig } require(vue/cli-service)module.exports defineConfig({transpileDe…...

财务管理系统javaweb会计账房进销存jsp源代码mysql

本项目为前几天收费帮学妹做的一个项目&#xff0c;Java EE JSP项目&#xff0c;在工作环境中基本使用不到&#xff0c;但是很多学校把这个当作编程入门的项目来做&#xff0c;故分享出本项目供初学者参考。 一、项目描述 财务管理系统javaweb java,Struts2,bootstrap,mysql,…...

企业服务器被devos勒索病毒攻击后怎么处理,devos勒索病毒如何攻击的

众所周知&#xff0c;科学技术是第一生产力&#xff0c;科学技术的发展给企业与人们的生活带来了极大变化&#xff0c;但随之而来的网络安全威胁也不断增加。最近&#xff0c;我们收到很多企业的求助&#xff0c;企业的计算机服务器遭到了devos勒索病毒的攻击&#xff0c;导致企…...

React源码解析18(2)------ FilberNode,FilberRootNode结构关系

摘要 在上一篇&#xff0c;我们实现了通过JSX转换为ReactElement的方法&#xff0c;也看到了转换后React元素的结构。但是这个React元素&#xff0c;并不能很清楚的表达组件之间的关系&#xff0c;以及属性的处理。 所以在React内部&#xff0c;会将所有的React元素转换为Fil…...

什么是Session?它在SQLAlchemy中扮演什么角色?

让我们先来谈谈什么是“Session”。在你逛超市或者餐厅的时候&#xff0c;你可能会遇到一种叫做“前台”的东西。你知道那是干什么的吗&#xff1f;它是用来暂存你买的东西&#xff0c;这样你就可以从容地结账&#xff0c;而不必抱着满满一购物车的商品。 数据库的“Session”…...

Java 中 Set集合常用方法

.add() 添加元素 对象名.add() 向Set集合中添加元素 &#xff08;但不能添加重复元素&#xff0c;Set集合中不允许元素重复&#xff09; Set<String> s new HashSet<String>(); // 添加数据 s.add("aaa"); s.add("bbb"); addAll(Collectio…...

(MVC)SpringBoot+Mybatis+Mapper.xml

前言&#xff1a;本篇博客主要对MVC架构、Mybatis工程加深下理解&#xff0c;前面写过一篇博客&#xff1a;SprintBoothtml/css/jsmybatis的demo&#xff0c;里面涉及到了Mybatis的应用&#xff0c;此篇博客主要介绍一种将sql语句写到了配置文件里的方法&#xff0c;即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…...

IDEA运行Tomcat出现乱码问题解决汇总

最近正值期末周&#xff0c;有很多同学在写期末Java web作业时&#xff0c;运行tomcat出现乱码问题&#xff0c;经过多次解决与研究&#xff0c;我做了如下整理&#xff1a; 原因&#xff1a; IDEA本身编码与tomcat的编码与Windows编码不同导致&#xff0c;Windows 系统控制台…...

业务系统对接大模型的基础方案:架构设计与关键步骤

业务系统对接大模型&#xff1a;架构设计与关键步骤 在当今数字化转型的浪潮中&#xff0c;大语言模型&#xff08;LLM&#xff09;已成为企业提升业务效率和创新能力的关键技术之一。将大模型集成到业务系统中&#xff0c;不仅可以优化用户体验&#xff0c;还能为业务决策提供…...

CTF show Web 红包题第六弹

提示 1.不是SQL注入 2.需要找关键源码 思路 进入页面发现是一个登录框&#xff0c;很难让人不联想到SQL注入&#xff0c;但提示都说了不是SQL注入&#xff0c;所以就不往这方面想了 ​ 先查看一下网页源码&#xff0c;发现一段JavaScript代码&#xff0c;有一个关键类ctfs…...

利用ngx_stream_return_module构建简易 TCP/UDP 响应网关

一、模块概述 ngx_stream_return_module 提供了一个极简的指令&#xff1a; return <value>;在收到客户端连接后&#xff0c;立即将 <value> 写回并关闭连接。<value> 支持内嵌文本和内置变量&#xff08;如 $time_iso8601、$remote_addr 等&#xff09;&a…...

2.Vue编写一个app

1.src中重要的组成 1.1main.ts // 引入createApp用于创建应用 import { createApp } from "vue"; // 引用App根组件 import App from ./App.vue;createApp(App).mount(#app)1.2 App.vue 其中要写三种标签 <template> <!--html--> </template>…...

《通信之道——从微积分到 5G》读书总结

第1章 绪 论 1.1 这是一本什么样的书 通信技术&#xff0c;说到底就是数学。 那些最基础、最本质的部分。 1.2 什么是通信 通信 发送方 接收方 承载信息的信号 解调出其中承载的信息 信息在发送方那里被加工成信号&#xff08;调制&#xff09; 把信息从信号中抽取出来&am…...

【Oracle】分区表

个人主页&#xff1a;Guiat 归属专栏&#xff1a;Oracle 文章目录 1. 分区表基础概述1.1 分区表的概念与优势1.2 分区类型概览1.3 分区表的工作原理 2. 范围分区 (RANGE Partitioning)2.1 基础范围分区2.1.1 按日期范围分区2.1.2 按数值范围分区 2.2 间隔分区 (INTERVAL Partit…...

C/C++ 中附加包含目录、附加库目录与附加依赖项详解

在 C/C 编程的编译和链接过程中&#xff0c;附加包含目录、附加库目录和附加依赖项是三个至关重要的设置&#xff0c;它们相互配合&#xff0c;确保程序能够正确引用外部资源并顺利构建。虽然在学习过程中&#xff0c;这些概念容易让人混淆&#xff0c;但深入理解它们的作用和联…...

C#学习第29天:表达式树(Expression Trees)

目录 什么是表达式树&#xff1f; 核心概念 1.表达式树的构建 2. 表达式树与Lambda表达式 3.解析和访问表达式树 4.动态条件查询 表达式树的优势 1.动态构建查询 2.LINQ 提供程序支持&#xff1a; 3.性能优化 4.元数据处理 5.代码转换和重写 适用场景 代码复杂性…...

在 Spring Boot 中使用 JSP

jsp&#xff1f; 好多年没用了。重新整一下 还费了点时间&#xff0c;记录一下。 项目结构&#xff1a; pom: <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0" xmlns:xsi"http://ww…...