【算法-哈希表3】四数相加2 和 赎金信
今天,带来哈希表相关算法的讲解。文中不足错漏之处望请斧正!
理论基础点这里
1. 四数相加2
分析题意
求符合条件的四元组的出现次数,条件:
- nums1
- nums2
- nums3
- nums4
从四个数组中的每一个数组取一个数 num1, num2, num3, num4,满足num1 + num2 + num3 + num4 == 0,则这是一个满足条件的四元组,可以记上它的出现次数。
题意转化
可以简单转化为 直接遍历取得4个数, 判断是否满足条件.但太慢,时间复杂度O(n^4)。
其实可以动动脑筋,将题意转化为 是否存在 两个两数之和 sum1 和 sum2 相加为0。
解决思路
四个数组该怎样去遍历,建立映射?
我们可以先遍历前两个数组,将数组中的元素两两求和得到sum1,把sum1和其出现次数建立映射得到哈希表sums1。接着遍历后两个数组,也两两求和得到sum2,在sums1中O(1)查找是否有一个和,和当前sum相加为0。
但为什么要这样遍历,我先遍历一个建立映射,再遍历三个不行吗?
这样我们在最终搜索比对的时候需要3层for来玩儿,那就是O(n^3)。而我们两两遍历只需要O(2 * n^2),这才是更好的。
编程实现
class Solution {
public:// 四数之和的判断 拆分为 两数之和的判断// 先遍历两个数组并求得所有两数之和sums1, 再遍历两个数组求剩下的两数之和, 查找是否有sum1 = -sum2int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {unordered_map<int, int> sums1; // <sum1, cnt> -- 题目不要求返回下标, 只用返回次数int sum1 = 0;int sum2 = 0;// 先遍历两个数组并求得所有两数之和sums1for (int &num1 : nums1) {for (int &num2 : nums2) {sum1 = num1 + num2;++sums1[sum1];}}// 再遍历两个数组求剩下的两数之和, 查找是否有sum1 = -sum2int cnt = 0;for (int &num3 : nums3) {for (int &num4 : nums4) {sum2 = num3 + num4;auto iter = sums1.find(-sum2);if (iter != sums1.end()) cnt += iter->second;}}return cnt;}
};
时间复杂度:O(n^2)
2. 赎金信
分析题意
“给你两个字符串:ransomNote 和 magazine ,判断 ransomNote 能不能由 magazine 里面的字符构成。”
题意转化
判断ransomNote的组成字符是否全部都在magazine中有足够的字符与之对应。
解决思路
查找,上哈希。遍历magazine,用哈希表描述magazine中的字符出现过多少次。
编程实现
class Solution {
public:bool canConstruct(string ransomNote, string magazine) {int appeared[26] = {0};// 用哈希表(数组)描述magazine中的哪些字符出现过.for (char &ch : magazine) ++appeared[ch - 'a'];// 在magazine中查找ransomNote的所有字符, 所有都能找到才是赎金信.for (char &ch : ransomNote) {--appeared[ch - 'a'];if (appeared[ch - 'a'] < 0) return false; // magazine中没有足够字符构成ransomNote}return true;}
};
时间复杂度:O(n)
空间复杂度:O(1)
今天的分享就到这里了,感谢您能看到这里。
这里是培根的blog,期待与你共同进步!
相关文章:
【算法-哈希表3】四数相加2 和 赎金信
今天,带来哈希表相关算法的讲解。文中不足错漏之处望请斧正! 理论基础点这里 1. 四数相加2 分析题意 求符合条件的四元组的出现次数,条件: nums1nums2nums3nums4 从四个数组中的每一个数组取一个数 num1, num2, num3, num4&am…...
wpf devexpress自定义编辑器
打开前一个例子 步骤1-自定义FirstName和LastName编辑器字段 如果运行程序,会通知编辑器是空。对于例子,这两个未命名编辑器在第一个LayoutItem(Name)。和最终用户有一个访客左右编辑器查阅到First Name和Last Name字段,分别。如果你看到Go…...
文档向量化工具(一):Apache Tika介绍
Apache Tika是什么?能干什么? Apache Tika是一个内容分析工具包。 该工具包可以从一千多种不同的文件类型(如PPT、XLS和PDF)中检测并提取元数据和文本。 所有这些文件类型都可以通过同一个接口进行解析,这使得Tika在…...
学习c#的第二十一天
目录 C# 泛型(Generic) 泛型类型参数 类型参数的约束 约束多个参数 未绑定的类型参数 类型参数作为约束 notnull 约束 class 约束 default 约束 非托管约束 委托约束 枚举约束 类型参数实现声明的接口 泛型类 泛型方法 泛型和数组 泛型…...
Michael Jordan最新报告:去中心化机器学习中的契约、不确定性和激励
导读 11月3日,智源研究院学术顾问委员会委员、机器学习泰斗Michael Jordan在以“新一代人工智能前沿”为主题的2023北京论坛 新工科专题论坛上,发表了题为Contracts, Uncertainty, and Incentives in Decentralized Machine Learning(去…...
3ds Max渲染用专业显卡还是游戏显卡?
使用3dsmax建模时,会面临诸多选择,除了用vr还是cr的决策,硬件选择上也存在着疑问,比如用专业显卡还是消费级游戏显卡?一般来说,除非是特别专业的大型项目和软件,且预算在5位数以上,常…...
airlearning-ue4安装的踩坑记录
最近要安装airlearning-ue4,用于实现无人机仿真环境,该项目地址为:GitHub - harvard-edge/airlearning-ue4: Environment Generator for Air Learning Project. This version is build on top of UE4 game engine 由于这个项目已经完成好几年…...
uniapp优化h5项目-摇树优化,gzip压缩和删除console.log
1.摇树优化 勾选摇树优化,打包删除死代码 2.gzip压缩和删除console.log 安装插件webpack和compression-webpack-plugin webpack插件 npm install webpack4.46.0 --save-devcompression-webpack-plugin插件 npm install compression-webpack-plugin6.1.1 --save-devconst Com…...
Pycharm之配置python虚拟环境
最近给身边的人写了脚本,在自己电脑可以正常运行。分享给我身边的人,却运行不起来,然后把报错的截图给我看了,所以难道不会利用pycharm搭建虚拟的环境?记录一下配置的过程。 第一步:右键要打开的python的代…...
如何使用MybatisPlus进行数据分页显示
如何使用MybatisPlus进行数据的分页呢? 使用Mybatis Plus提供的分页插件来简化开发,在MybatisPlusInterceptor的拦截器中添加自动分页的PaginationInnerInterceptor拦截器,当前配置需要交给spring的bean管理,类上添加注解Configu…...
代码随想录 Day49 单调栈01 LeetCode LeetCodeT739每日温度 T496 下一个最大元素I
前言 折磨的死去活来的动态规划终于结束啦,今天秋秋给大家带来两题非常经典的单调栈问题,可能你不清楚单调栈是什么,可以用来解决什么问题,今天我们就来一步一步的逐渐了解单调栈,到能够灵活使用单调栈.注意以下讲解中,顺序的描述为 从栈头到栈底的顺序 什么时候用单…...
高可用--限流熔断降级
熔断 熔断是应对微服务雪崩效应的一种链路保护机制。 场景 服务端出现问题 服务指标:响应时间、错误率、连续错误数等,超过阈值出发熔断。硬件指标:CPU、网络IO、内存 目的 服务端恢复需要时间、服务端需要休息避免全调用链路崩溃&…...
win10电脑无法联网,设置IPv4,点击属性无法打开,闪退
win10设置IPv4,点击属性无法打开,闪退 问题:win10设置IPv4,点击属性无法打开,闪退 问题:win10设置IPv4,点击属性无法打开,闪退 第1步:用管理员打开cmd命令窗口,然后输入下面的命令&…...
【数据结构】邻接表与邻接矩阵的转换
一.基本思想 1.邻接矩阵转换为邻接表: 先设置一个空的邻接表,然后查找邻接矩阵的值不为零元素,找到后在邻接表的单链表对应位置加入表边节点。 2.邻接表转换为邻接矩阵: 在邻接表上顺序取出每个表边结点,将邻接矩阵…...
VR智慧景区:VR赋能文旅产业,激活消费潜能
随着国家数字化战略的不断深入实施,文旅产业数字化转型的步伐也在逐渐加快,以VR技术赋能文旅产业,让文旅景区线上线下双渠道融合,进一步呈现文化底蕴、激活消费潜能。 VR智慧景区以沉浸式、互动式、科技感的方式,将景区…...
Spring Boot EasyPOI 使用指定模板导出Excel
相信大家都遇到过,用户提出要把界面上的数据导成一个Excel,还得是用户指定的Excel格式,用原生的POI,需要自己去实现,相信是比较麻烦的,所以我们可以使用开源的EasyPOI. 先上个图,看看是不是大家…...
postgresql:记录表膨胀引起的io问题的处理
文章目录 1. io异常2.查看profile报告2.1 生成事发时间段的pgprofile2.2 查看报告 3.检查table是否膨胀4.执行vacuum full5.总结 1. io异常 iostat -x 1 20 Device r/s w/s rkB/s wkB/s rrqm/s wrqm/s %rrqm %wrqm r_await w_await aqu-sz rareq…...
Windows下安装RabbitMQ
1.安装Erlang 因为RabbitMQ是用Erlang语言编写的,所以在安装RabbitMQ之前需要先安装Erlang。 如果还未安装Erlang,官方下载安装包,点击Download Windows installer下载Erlang Downloads - Erlang/OTP 下载Erlang/OTP后,双击otp的…...
广州华锐互动VRAR:利用VR开展刑事案件公安取证培训,沉浸式体验提升实战能力
随着科技的飞速发展,虚拟现实(VR)技术为我们的生活和工作带来了前所未有的便利。近年来,VR技术在刑事案件公安取证培训中的应用逐渐显现出其独特优势。通过模拟真实的犯罪现场,VR技术为学员提供了沉浸式的体验,使他们在安全的环境…...
消息消费过程
前言 本文介绍下Kafka消费过程, 内容涉及消费与消费组, 主题与分区, 位移提交,分区再平衡和消费者拦截器等内容。 消费者与消费组 Kafka将消费者组织为消费组, 消息只会被投递给消费组中的1个消费者。因此, 从不同消费组中的消费者来看, Kafka是多播(Pub/Sub)模式…...
树莓派超全系列教程文档--(62)使用rpicam-app通过网络流式传输视频
使用rpicam-app通过网络流式传输视频 使用 rpicam-app 通过网络流式传输视频UDPTCPRTSPlibavGStreamerRTPlibcamerasrc GStreamer 元素 文章来源: http://raspberry.dns8844.cn/documentation 原文网址 使用 rpicam-app 通过网络流式传输视频 本节介绍来自 rpica…...
Nuxt.js 中的路由配置详解
Nuxt.js 通过其内置的路由系统简化了应用的路由配置,使得开发者可以轻松地管理页面导航和 URL 结构。路由配置主要涉及页面组件的组织、动态路由的设置以及路由元信息的配置。 自动路由生成 Nuxt.js 会根据 pages 目录下的文件结构自动生成路由配置。每个文件都会对…...
土地利用/土地覆盖遥感解译与基于CLUE模型未来变化情景预测;从基础到高级,涵盖ArcGIS数据处理、ENVI遥感解译与CLUE模型情景模拟等
🔍 土地利用/土地覆盖数据是生态、环境和气象等诸多领域模型的关键输入参数。通过遥感影像解译技术,可以精准获取历史或当前任何一个区域的土地利用/土地覆盖情况。这些数据不仅能够用于评估区域生态环境的变化趋势,还能有效评价重大生态工程…...
【HTTP三个基础问题】
面试官您好!HTTP是超文本传输协议,是互联网上客户端和服务器之间传输超文本数据(比如文字、图片、音频、视频等)的核心协议,当前互联网应用最广泛的版本是HTTP1.1,它基于经典的C/S模型,也就是客…...
分布式增量爬虫实现方案
之前我们在讨论的是分布式爬虫如何实现增量爬取。增量爬虫的目标是只爬取新产生或发生变化的页面,避免重复抓取,以节省资源和时间。 在分布式环境下,增量爬虫的实现需要考虑多个爬虫节点之间的协调和去重。 另一种思路:将增量判…...
CSS设置元素的宽度根据其内容自动调整
width: fit-content 是 CSS 中的一个属性值,用于设置元素的宽度根据其内容自动调整,确保宽度刚好容纳内容而不会超出。 效果对比 默认情况(width: auto): 块级元素(如 <div>)会占满父容器…...
【从零学习JVM|第三篇】类的生命周期(高频面试题)
前言: 在Java编程中,类的生命周期是指类从被加载到内存中开始,到被卸载出内存为止的整个过程。了解类的生命周期对于理解Java程序的运行机制以及性能优化非常重要。本文会深入探寻类的生命周期,让读者对此有深刻印象。 目录 …...
HubSpot推出与ChatGPT的深度集成引发兴奋与担忧
上周三,HubSpot宣布已构建与ChatGPT的深度集成,这一消息在HubSpot用户和营销技术观察者中引发了极大的兴奋,但同时也存在一些关于数据安全的担忧。 许多网络声音声称,这对SaaS应用程序和人工智能而言是一场范式转变。 但向任何技…...
LangFlow技术架构分析
🔧 LangFlow 的可视化技术栈 前端节点编辑器 底层框架:基于 (一个现代化的 React 节点绘图库) 功能: 拖拽式构建 LangGraph 状态机 实时连线定义节点依赖关系 可视化调试循环和分支逻辑 与 LangGraph 的深…...
6个月Python学习计划 Day 16 - 面向对象编程(OOP)基础
第三周 Day 3 🎯 今日目标 理解类(class)和对象(object)的关系学会定义类的属性、方法和构造函数(init)掌握对象的创建与使用初识封装、继承和多态的基本概念(预告) &a…...
