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

【LeetCode】2363. 合并相似的物品

2363. 合并相似的物品

题目描述

给你两个二维整数数组 items1 和 items2 ,表示两个物品集合。每个数组 items 有以下特质:

  • items[i] = [valuei, weighti] 其中 valuei 表示第 i 件物品的 价值 ,weighti 表示第 i 件物品的 重量 。
  • items 中每件物品的价值都是 唯一的 。

请你返回一个二维数组 ret,其中 ret[i] = [valuei, weighti], weighti 是所有价值为 valuei 物品的 重量之和 。

注意:ret 应该按价值 升序 排序后返回。


示例 1

输入:items1 = [[1,1],[4,5],[3,8]], items2 = [[3,1],[1,5]]
输出:[[1,6],[3,9],[4,5]]
解释:
value = 1 的物品在 items1 中 weight = 1 ,在 items2 中 weight = 5 ,总重量为 1 + 5 = 6 。
value = 3 的物品再 items1 中 weight = 8 ,在 items2 中 weight = 1 ,总重量为 8 + 1 = 9 。
value = 4 的物品在 items1 中 weight = 5 ,总重量为 5 。
所以,我们返回 [[1,6],[3,9],[4,5]] 。


示例 2

输入:items1 = [[1,1],[3,2],[2,3]], items2 = [[2,1],[3,2],[1,3]]
输出:[[1,4],[2,4],[3,4]]
解释:
value = 1 的物品在 items1 中 weight = 1 ,在 items2 中 weight = 3 ,总重量为 1 + 3 = 4 。
value = 2 的物品在 items1 中 weight = 3 ,在 items2 中 weight = 1 ,总重量为 3 + 1 = 4 。
value = 3 的物品在 items1 中 weight = 2 ,在 items2 中 weight = 2 ,总重量为 2 + 2 = 4 。
所以,我们返回 [[1,4],[2,4],[3,4]] 。


示例 3

输入:items1 = [[1,3],[2,2]], items2 = [[7,1],[2,2],[1,4]]
输出:[[1,7],[2,4],[7,1]]
解释:
value = 1 的物品在 items1 中 weight = 3 ,在 items2 中 weight = 4 ,总重量为 3 + 4 = 7 。
value = 2 的物品在 items1 中 weight = 2 ,在 items2 中 weight = 2 ,总重量为 2 + 2 = 4 。
value = 7 的物品在 items2 中 weight = 1 ,总重量为 1 。
所以,我们返回 [[1,7],[2,4],[7,1]] 。


提示

  • 1 <= items1.length, items2.length <= 1000
  • items1[i].length == items2[i].length == 2
  • 1 <= valuei, weighti <= 1000
  • items1 中每个 valuei 都是 唯一的 。
  • items2 中每个 valuei 都是 唯一的 。

算法一:map 和 vector 的转化

思路

  • 首先将 items1 里的 value 和 weight 转换为 map 对应的 键值对,由于 map 会默认对 key 升序排序,因此此时的顺序已经满足了题目的要求。
  • 接着遍历 items2 ,将 items2 中对应的物品也加入到 map 中。
  • 此时 map 里存储的键值对就是答案,但是这道题要求我们返回二维 vector ,因此还需要将 map 转化为 二维 vector。

收获

  • 一开始想要哈希表,但是如果用下标存储 value ,太浪费空间了;如果是使用二维数组作为哈希表,遍历 items2 的时候又难以获得 value ,最后看了提示,可以用 map 。
  • map 访问对象 , key - map.first , value - map.second;
  • 如何将 map 转化为 二维 vector :这个我想了很久,后来发现可以创建一维 vector,将 map.first 和 map.second 放入,再将一维数组 push_back 到二维数组 ans 中,得到最终答案。

算法情况

  • 时间复杂度:O(n + m), 其中 n 和 m 分别为 items1 和 items2 的长度;

  • 空间复杂度:O(n + m), 其中 n 和 m 分别为 items1 和 items2 的长度。

    在这里插入图片描述

代码

class Solution {
public:vector<vector<int>> mergeSimilarItems(vector<vector<int>>& items1, vector<vector<int>>& items2) {// map默认对key升序排序map<int, int> mp;// 转化为mapfor(auto t : items1){mp[t[0]] = t[1];}for(auto t2: items2){mp[t2[0]] += t2[1];}vector<vector<int>> ans;// map 转化为 vector<vector<int>>for(auto s : mp){vector<int> temp = {s.first, s.second};ans.push_back(temp);}return ans;}
};

相关文章:

【LeetCode】2363. 合并相似的物品

2363. 合并相似的物品 题目描述 给你两个二维整数数组 items1 和 items2 &#xff0c;表示两个物品集合。每个数组 items 有以下特质&#xff1a; items[i] [valuei, weighti] 其中 valuei 表示第 i 件物品的 价值 &#xff0c;weighti 表示第 i 件物品的 重量 。items 中每…...

华为OD机试题,用 Java 解【出租车计费】问题

最近更新的博客 华为OD机试题,用 Java 解【停车场车辆统计】问题华为OD机试题,用 Java 解【字符串变换最小字符串】问题华为OD机试题,用 Java 解【计算最大乘积】问题华为OD机试题,用 Java 解【DNA 序列】问题华为OD机试 - 组成最大数(Java) | 机试题算法思路 【2023】使…...

【人脸识别】DDL:数据分布知识蒸馏思想,提升困难样本(遮挡、低分辨率等)识别效果

论文题目&#xff1a;《Improving Face Recognition from Hard Samples via Distribution Distillation Loss》 论文地址&#xff1a;https://arxiv.org/pdf/2002.03662v3.pdf 代码地址&#xff1a;https://github.com/HuangYG123/DDL 1.前言及相关工作 Large facial variatio…...

如何管理好仓库/库房?

仓库管理是企业管理中不可缺少的一部分&#xff0c;事关企业能否正常运行的关键之一&#xff0c;古人有云&#xff1a;“三军未动粮草先行”&#xff0c;一个企业仓库管理做不好&#xff0c;他的生产管理肯定也是做不好的&#xff0c;不是说生产管理人员的管理能力不具备&#…...

Unity Lighting -- Unity的光源简介

在主菜单栏中&#xff0c;点击Window -> Rendering -> Light Explorer打开光源管理器&#xff0c;这个标签页可以看到场景中所有的光源&#xff0c;包括每个光源的类型&#xff0c;形状&#xff0c;模式&#xff0c;颜色&#xff0c;强度&#xff0c;阴影等信息。 在主菜…...

Android仿网易云音乐歌单详情页

效果图实现思路&#xff1a;1、Activity设置自定义Shared Element切换动画2、透明状态栏&#xff08;透明Toolbar,使背景图上移&#xff09;3、Toolbar底部增加和背景一样的高斯模糊图&#xff0c;并上移图片&#xff08;为了使背景图的底部作为Toolbar的背景&#xff09;4、上…...

linux基本功系列之free命令实战

文章目录前言一. free命令介绍二. 语法格式及常用选项三. 参考案例3.1 查看free相关的信息3.2 以MB的形式显示内存的使用情况3.3 以总和的形式显示内存的使用情况3.4 周期性的查询内存的使用情况3.5 以更人性化的形式来查看内存的结果输出总结前言 大家好&#xff0c;又见面了…...

华为OD机试模拟题 用 C++ 实现 - 连续子串(2023.Q1)

最近更新的博客 【华为OD机试模拟题】用 C++ 实现 - 最多获得的短信条数(2023.Q1)) 文章目录 最近更新的博客使用说明连续子串题目输入输出示例一输入输出说明Code使用说明 参加华为od机试,一定要注意不要完全背诵代码,需要理解之后模仿写出,通过率才会高。 华为 OD …...

【软考——系统架构师】UML 建模与架构文档化

&#x1f50e;这里是【软考——系统架构师】&#xff0c;关注我考试轻松过线 &#x1f44d;如果对你有帮助&#xff0c;给博主一个免费的点赞以示鼓励 欢迎各位&#x1f50e;点赞&#x1f44d;评论收藏⭐️ 文章目录UML 基础UML 软件开发过程系统架构文档化送书福利UML 基础 U…...

Spring中常用注解

声明 bean 的注解 Component&#xff1a;泛指各种组件 Controller、Service、Repository 都可以称为Component Controller&#xff1a;控制层 Service&#xff1a;业务层 Repository&#xff1a;数据访问层Bean 的生命周期属性 Scope 设置类型包括&#xff1a;设置 Spring 容器…...

基于SpringCloud的可靠消息最终一致性06:轮询事务消息

上一节把可靠消息最终一致性的正常逻辑代码顺序执行了一次,并且对于同一个事务消息,在正常情况下它要被发送至少两次。 这是因为在发送消息之前,TransactionMessageService就已经把消息保存到了数据库中。而在首次消费完消息后,TransactionMessageListener并没有从数据库中…...

Python Flask + Echarts 轻松制作动态酷炫大屏( 附代码)

目录一、确定需求方案二、整体架构设计三、编码实现 &#xff08;关键代码&#xff09;四、完整代码五、运行效果1.动态实时更新数据效果图 说明: 其中 今日抓拍&#xff0c;抓拍总数&#xff0c;预警信息统计&#xff0c;监控点位统计图表 做了动态实时更新处理。 ​ 2.静态…...

Wepack(1):SourceMap讲解以及使用

今天我们来讲讲定位源码的工具 Sourcemap &#xff0c; 我们先讲最简单的配置&#xff0c;之后才补充 sourcemap 的其他属性 Sourcemap 作用 可以在打包的代码直接对应相应源码 例如 vue2 , vue3可以把对应的错误上传到相关服务器 使用 webpack.config.js const config …...

华为OD机试题,用 Java 解【最多等和不相交连续子序列】问题

最近更新的博客 华为OD机试题,用 Java 解【停车场车辆统计】问题华为OD机试题,用 Java 解【字符串变换最小字符串】问题华为OD机试题,用 Java 解【计算最大乘积】问题华为OD机试题,用 Java 解【DNA 序列】问题华为OD机试 - 组成最大数(Java) | 机试题算法思路 【2023】使…...

Kubernetes06:Controller

Kubernetes06:Controller 1、什么是controller 管理和运行容器的对象&#xff0c;是一个物理概念 在集群上管理和运行容器的对象 2、Pod和Controller之间的关系 Pod是通过controller来实现应用的运维 比如伸缩、滚动升级等等操作Pod和Controller之间通过 label 标签建立关系…...

采购文件中 RFI、RFQ、RFP、IFB的区别

【PMBOK的描述】   采购文件用于征求潜在卖方的建议书。如果主要依据价格来选择卖方&#xff08;如购买商业或标准产品时&#xff09;&#xff0c;通常就使用标书、投标或报价等术语。如果主要依据其他考虑&#xff08;如技术能力或技术方法&#xff09;来选择卖方&#xff0…...

linux升级gcc版本详细教程

0.前言一般linux操作系统默认的gcc版本都比较低&#xff0c;例如centos7系统默认的gcc版本为4.8.5。gcc是从4.7版本开始支持C11的&#xff0c;4.8版本对C11新特性的编译支持还不够完善&#xff0c;因此如果需要更好的体验C11以及以上版本的新特性&#xff0c;需要升级gcc到一个…...

NBA Top Shot 跌落神坛

近日&#xff0c;美国职业篮球联盟&#xff08;NBA&#xff09;授权的NFT 项目“NBA Top Shot Moments”被纽约法院初步裁定为“可能符合证券的定义”&#xff0c;虽然这不是对2021年用户指控该项目违法的最终判决&#xff0c;但这个裁定引发了市场担忧&#xff0c;部分NFT的地…...

状态管理Pinia使用详解(带你入门)

状态管理Pinia使用详解(带你从入门到入神) 序&#xff1a; ​ 如果你之前使用过 vuex 进行状态管理的话&#xff0c;那么 pinia 就是一个类似的插件。它是最新一代的轻量级状态管理插件。你可以通过defineStore来简单创建一个存储管理。 ​ 与 vuex 相比&#xff0c;pinia 提…...

Linux系统基础命令(一)

一、图形界面和终端界面 图形界面&#xff1a;是指采用图形方式显示的计算机操作用户界面。 终端界面&#xff1a;是指黑底白字的命令行界面。 什么是tty呢&#xff1f; tty&#xff1a;终端设备的统称。 tty一词源于Teletypes&#xff0c;或者teletypewriters&#xff0c;…...

基于FPGA的PID算法学习———实现PID比例控制算法

基于FPGA的PID算法学习 前言一、PID算法分析二、PID仿真分析1. PID代码2.PI代码3.P代码4.顶层5.测试文件6.仿真波形 总结 前言 学习内容&#xff1a;参考网站&#xff1a; PID算法控制 PID即&#xff1a;Proportional&#xff08;比例&#xff09;、Integral&#xff08;积分&…...

质量体系的重要

质量体系是为确保产品、服务或过程质量满足规定要求&#xff0c;由相互关联的要素构成的有机整体。其核心内容可归纳为以下五个方面&#xff1a; &#x1f3db;️ 一、组织架构与职责 质量体系明确组织内各部门、岗位的职责与权限&#xff0c;形成层级清晰的管理网络&#xf…...

【JavaSE】绘图与事件入门学习笔记

-Java绘图坐标体系 坐标体系-介绍 坐标原点位于左上角&#xff0c;以像素为单位。 在Java坐标系中,第一个是x坐标,表示当前位置为水平方向&#xff0c;距离坐标原点x个像素;第二个是y坐标&#xff0c;表示当前位置为垂直方向&#xff0c;距离坐标原点y个像素。 坐标体系-像素 …...

听写流程自动化实践,轻量级教育辅助

随着智能教育工具的发展&#xff0c;越来越多的传统学习方式正在被数字化、自动化所优化。听写作为语文、英语等学科中重要的基础训练形式&#xff0c;也迎来了更高效的解决方案。 这是一款轻量但功能强大的听写辅助工具。它是基于本地词库与可选在线语音引擎构建&#xff0c;…...

免费PDF转图片工具

免费PDF转图片工具 一款简单易用的PDF转图片工具&#xff0c;可以将PDF文件快速转换为高质量PNG图片。无需安装复杂的软件&#xff0c;也不需要在线上传文件&#xff0c;保护您的隐私。 工具截图 主要特点 &#x1f680; 快速转换&#xff1a;本地转换&#xff0c;无需等待上…...

JavaScript 数据类型详解

JavaScript 数据类型详解 JavaScript 数据类型分为 原始类型&#xff08;Primitive&#xff09; 和 对象类型&#xff08;Object&#xff09; 两大类&#xff0c;共 8 种&#xff08;ES11&#xff09;&#xff1a; 一、原始类型&#xff08;7种&#xff09; 1. undefined 定…...

C++ 设计模式 《小明的奶茶加料风波》

&#x1f468;‍&#x1f393; 模式名称&#xff1a;装饰器模式&#xff08;Decorator Pattern&#xff09; &#x1f466; 小明最近上线了校园奶茶配送功能&#xff0c;业务火爆&#xff0c;大家都在加料&#xff1a; 有的同学要加波霸 &#x1f7e4;&#xff0c;有的要加椰果…...

Bean 作用域有哪些?如何答出技术深度?

导语&#xff1a; Spring 面试绕不开 Bean 的作用域问题&#xff0c;这是面试官考察候选人对 Spring 框架理解深度的常见方式。本文将围绕“Spring 中的 Bean 作用域”展开&#xff0c;结合典型面试题及实战场景&#xff0c;帮你厘清重点&#xff0c;打破模板式回答&#xff0c…...

WPF八大法则:告别模态窗口卡顿

⚙️ 核心问题&#xff1a;阻塞式模态窗口的缺陷 原始代码中ShowDialog()会阻塞UI线程&#xff0c;导致后续逻辑无法执行&#xff1a; var result modalWindow.ShowDialog(); // 线程阻塞 ProcessResult(result); // 必须等待窗口关闭根本问题&#xff1a…...

深度剖析 DeepSeek 开源模型部署与应用:策略、权衡与未来走向

在人工智能技术呈指数级发展的当下&#xff0c;大模型已然成为推动各行业变革的核心驱动力。DeepSeek 开源模型以其卓越的性能和灵活的开源特性&#xff0c;吸引了众多企业与开发者的目光。如何高效且合理地部署与运用 DeepSeek 模型&#xff0c;成为释放其巨大潜力的关键所在&…...