【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 ,表示两个物品集合。每个数组 items 有以下特质: items[i] [valuei, weighti] 其中 valuei 表示第 i 件物品的 价值 ,weighti 表示第 i 件物品的 重量 。items 中每…...

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

【人脸识别】DDL:数据分布知识蒸馏思想,提升困难样本(遮挡、低分辨率等)识别效果
论文题目:《Improving Face Recognition from Hard Samples via Distribution Distillation Loss》 论文地址:https://arxiv.org/pdf/2002.03662v3.pdf 代码地址:https://github.com/HuangYG123/DDL 1.前言及相关工作 Large facial variatio…...

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

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

Android仿网易云音乐歌单详情页
效果图实现思路:1、Activity设置自定义Shared Element切换动画2、透明状态栏(透明Toolbar,使背景图上移)3、Toolbar底部增加和背景一样的高斯模糊图,并上移图片(为了使背景图的底部作为Toolbar的背景)4、上…...

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

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

【软考——系统架构师】UML 建模与架构文档化
🔎这里是【软考——系统架构师】,关注我考试轻松过线 👍如果对你有帮助,给博主一个免费的点赞以示鼓励 欢迎各位🔎点赞👍评论收藏⭐️ 文章目录UML 基础UML 软件开发过程系统架构文档化送书福利UML 基础 U…...
Spring中常用注解
声明 bean 的注解 Component:泛指各种组件 Controller、Service、Repository 都可以称为Component Controller:控制层 Service:业务层 Repository:数据访问层Bean 的生命周期属性 Scope 设置类型包括:设置 Spring 容器…...

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

Python Flask + Echarts 轻松制作动态酷炫大屏( 附代码)
目录一、确定需求方案二、整体架构设计三、编码实现 (关键代码)四、完整代码五、运行效果1.动态实时更新数据效果图 说明: 其中 今日抓拍,抓拍总数,预警信息统计,监控点位统计图表 做了动态实时更新处理。 2.静态…...
Wepack(1):SourceMap讲解以及使用
今天我们来讲讲定位源码的工具 Sourcemap , 我们先讲最简单的配置,之后才补充 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 管理和运行容器的对象,是一个物理概念 在集群上管理和运行容器的对象 2、Pod和Controller之间的关系 Pod是通过controller来实现应用的运维 比如伸缩、滚动升级等等操作Pod和Controller之间通过 label 标签建立关系…...
采购文件中 RFI、RFQ、RFP、IFB的区别
【PMBOK的描述】 采购文件用于征求潜在卖方的建议书。如果主要依据价格来选择卖方(如购买商业或标准产品时),通常就使用标书、投标或报价等术语。如果主要依据其他考虑(如技术能力或技术方法)来选择卖方࿰…...

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

NBA Top Shot 跌落神坛
近日,美国职业篮球联盟(NBA)授权的NFT 项目“NBA Top Shot Moments”被纽约法院初步裁定为“可能符合证券的定义”,虽然这不是对2021年用户指控该项目违法的最终判决,但这个裁定引发了市场担忧,部分NFT的地…...
状态管理Pinia使用详解(带你入门)
状态管理Pinia使用详解(带你从入门到入神) 序: 如果你之前使用过 vuex 进行状态管理的话,那么 pinia 就是一个类似的插件。它是最新一代的轻量级状态管理插件。你可以通过defineStore来简单创建一个存储管理。 与 vuex 相比,pinia 提…...

Linux系统基础命令(一)
一、图形界面和终端界面 图形界面:是指采用图形方式显示的计算机操作用户界面。 终端界面:是指黑底白字的命令行界面。 什么是tty呢? tty:终端设备的统称。 tty一词源于Teletypes,或者teletypewriters,…...

Linux应用开发之网络套接字编程(实例篇)
服务端与客户端单连接 服务端代码 #include <sys/socket.h> #include <sys/types.h> #include <netinet/in.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <arpa/inet.h> #include <pthread.h> …...
Java多线程实现之Callable接口深度解析
Java多线程实现之Callable接口深度解析 一、Callable接口概述1.1 接口定义1.2 与Runnable接口的对比1.3 Future接口与FutureTask类 二、Callable接口的基本使用方法2.1 传统方式实现Callable接口2.2 使用Lambda表达式简化Callable实现2.3 使用FutureTask类执行Callable任务 三、…...
HTML前端开发:JavaScript 常用事件详解
作为前端开发的核心,JavaScript 事件是用户与网页交互的基础。以下是常见事件的详细说明和用法示例: 1. onclick - 点击事件 当元素被单击时触发(左键点击) button.onclick function() {alert("按钮被点击了!&…...
工业自动化时代的精准装配革新:迁移科技3D视觉系统如何重塑机器人定位装配
AI3D视觉的工业赋能者 迁移科技成立于2017年,作为行业领先的3D工业相机及视觉系统供应商,累计完成数亿元融资。其核心技术覆盖硬件设计、算法优化及软件集成,通过稳定、易用、高回报的AI3D视觉系统,为汽车、新能源、金属制造等行…...
css3笔记 (1) 自用
outline: none 用于移除元素获得焦点时默认的轮廓线 broder:0 用于移除边框 font-size:0 用于设置字体不显示 list-style: none 消除<li> 标签默认样式 margin: xx auto 版心居中 width:100% 通栏 vertical-align 作用于行内元素 / 表格单元格ÿ…...

佰力博科技与您探讨热释电测量的几种方法
热释电的测量主要涉及热释电系数的测定,这是表征热释电材料性能的重要参数。热释电系数的测量方法主要包括静态法、动态法和积分电荷法。其中,积分电荷法最为常用,其原理是通过测量在电容器上积累的热释电电荷,从而确定热释电系数…...
iOS性能调优实战:借助克魔(KeyMob)与常用工具深度洞察App瓶颈
在日常iOS开发过程中,性能问题往往是最令人头疼的一类Bug。尤其是在App上线前的压测阶段或是处理用户反馈的高发期,开发者往往需要面对卡顿、崩溃、能耗异常、日志混乱等一系列问题。这些问题表面上看似偶发,但背后往往隐藏着系统资源调度不当…...

(一)单例模式
一、前言 单例模式属于六大创建型模式,即在软件设计过程中,主要关注创建对象的结果,并不关心创建对象的过程及细节。创建型设计模式将类对象的实例化过程进行抽象化接口设计,从而隐藏了类对象的实例是如何被创建的,封装了软件系统使用的具体对象类型。 六大创建型模式包括…...

stm32wle5 lpuart DMA数据不接收
配置波特率9600时,需要使用外部低速晶振...
基于鸿蒙(HarmonyOS5)的打车小程序
1. 开发环境准备 安装DevEco Studio (鸿蒙官方IDE)配置HarmonyOS SDK申请开发者账号和必要的API密钥 2. 项目结构设计 ├── entry │ ├── src │ │ ├── main │ │ │ ├── ets │ │ │ │ ├── pages │ │ │ │ │ ├── H…...