当前位置: 首页 > 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…...

微信小程序之bind和catch

这两个呢&#xff0c;都是绑定事件用的&#xff0c;具体使用有些小区别。 官方文档&#xff1a; 事件冒泡处理不同 bind&#xff1a;绑定的事件会向上冒泡&#xff0c;即触发当前组件的事件后&#xff0c;还会继续触发父组件的相同事件。例如&#xff0c;有一个子视图绑定了b…...

测试markdown--肇兴

day1&#xff1a; 1、去程&#xff1a;7:04 --11:32高铁 高铁右转上售票大厅2楼&#xff0c;穿过候车厅下一楼&#xff0c;上大巴车 &#xffe5;10/人 **2、到达&#xff1a;**12点多到达寨子&#xff0c;买门票&#xff0c;美团/抖音&#xff1a;&#xffe5;78人 3、中饭&a…...

【项目实战】通过多模态+LangGraph实现PPT生成助手

PPT自动生成系统 基于LangGraph的PPT自动生成系统&#xff0c;可以将Markdown文档自动转换为PPT演示文稿。 功能特点 Markdown解析&#xff1a;自动解析Markdown文档结构PPT模板分析&#xff1a;分析PPT模板的布局和风格智能布局决策&#xff1a;匹配内容与合适的PPT布局自动…...

Python爬虫(二):爬虫完整流程

爬虫完整流程详解&#xff08;7大核心步骤实战技巧&#xff09; 一、爬虫完整工作流程 以下是爬虫开发的完整流程&#xff0c;我将结合具体技术点和实战经验展开说明&#xff1a; 1. 目标分析与前期准备 网站技术分析&#xff1a; 使用浏览器开发者工具&#xff08;F12&…...

解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错

出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上&#xff0c;所以报错&#xff0c;到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本&#xff0c;cu、torch、cp 的版本一定要对…...

c#开发AI模型对话

AI模型 前面已经介绍了一般AI模型本地部署&#xff0c;直接调用现成的模型数据。这里主要讲述讲接口集成到我们自己的程序中使用方式。 微软提供了ML.NET来开发和使用AI模型&#xff0c;但是目前国内可能使用不多&#xff0c;至少实践例子很少看见。开发训练模型就不介绍了&am…...

Java多线程实现之Thread类深度解析

Java多线程实现之Thread类深度解析 一、多线程基础概念1.1 什么是线程1.2 多线程的优势1.3 Java多线程模型 二、Thread类的基本结构与构造函数2.1 Thread类的继承关系2.2 构造函数 三、创建和启动线程3.1 继承Thread类创建线程3.2 实现Runnable接口创建线程 四、Thread类的核心…...

Device Mapper 机制

Device Mapper 机制详解 Device Mapper&#xff08;简称 DM&#xff09;是 Linux 内核中的一套通用块设备映射框架&#xff0c;为 LVM、加密磁盘、RAID 等提供底层支持。本文将详细介绍 Device Mapper 的原理、实现、内核配置、常用工具、操作测试流程&#xff0c;并配以详细的…...

Web 架构之 CDN 加速原理与落地实践

文章目录 一、思维导图二、正文内容&#xff08;一&#xff09;CDN 基础概念1. 定义2. 组成部分 &#xff08;二&#xff09;CDN 加速原理1. 请求路由2. 内容缓存3. 内容更新 &#xff08;三&#xff09;CDN 落地实践1. 选择 CDN 服务商2. 配置 CDN3. 集成到 Web 架构 &#xf…...

docker 部署发现spring.profiles.active 问题

报错&#xff1a; org.springframework.boot.context.config.InvalidConfigDataPropertyException: Property spring.profiles.active imported from location class path resource [application-test.yml] is invalid in a profile specific resource [origin: class path re…...