算法Day07 | 454.四数相加II,383. 赎金信,15. 三数之和, 18. 四数之和
Day07
- 454.四数相加II
- 383. 赎金信
- 15. 三数之和
- 18. 四数之和
454.四数相加II
题目链接:454.四数相加II
寻找两个数组之和,是否与另外两个数组之和有特定的关系。
因为数值可能跨度太大,选择使用下标表示为对应的数值大小,会很浪费内存空间。
target
减去后两个数组之和的结果,是否存在与前两个数组之和组成的集合中。又要返回满足题意的次数,因此决定使用map
而不是set
。
class Solution {
public:int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {unordered_map<int, int> map;for (auto& i: nums1) {for (auto& j: nums2) {map[i + j]++;//nums1 nums2之和存入map}}int cnt = 0;for (auto& i: nums3) {for (auto& j: nums4) {int target = 0 - (i + j);//查找target是否存在与map中if (map.find(target) != map.end()) {cnt += map[target];//target对应存在多少个,都加入}}}return cnt;}
};
383. 赎金信
题目链接:383. 赎金信
判断ransomNote
中的字符是否出现在magazine
中。
class Solution {
public:bool canConstruct(string ransomNote, string magazine) {if (ransomNote.size() > magazine.size()) {return false;}int record['z' - 'A' + 1] = {};//个数别查错了。+1for (auto& i : magazine) {record[i - 'A']++;}for (auto& i : ransomNote) {record[i - 'A']--;//出现就直接返回,不用在该循环之后再遍历recordif (record[i - 'A'] < 0) return false;}return true;}
};
15. 三数之和
题目链接:15. 三数之和
两个数之和,第三个数与目标值运算之后,是否出现在两个数之和中。
但是,时间复杂度为 O ( n 2 ) O(n^2) O(n2),且要去重操作。
选择使用双指针,注意去重操作。
class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {vector<vector<int> > ret;sort(nums.begin(), nums.end());for (int i = 0; i < nums.size(); i++) {if (nums[i] > 0) break;//剪枝。没有不影响结果//i指针的去重if (i > 0 && nums[i] == nums[i - 1]) continue;int left = i + 1, right = nums.size() - 1;while (left < right) {if (nums[i] + nums[left] + nums[right] > 0) {right--;} else if (nums[i] + nums[left] + nums[right] < 0) {left++;} else {ret.push_back(vector<int>{nums[i], nums[left], nums[right]});//left和right指针的去重。移动时,注意满足边界条件while (left < right && nums[left] == nums[left + 1])left++;while (left < right && nums[right] == nums[right - 1])right--;left++;right--;}}}return ret;}
};
其中
while (left < right && nums[left] == nums[left + 1]) left++;
while (left < right && nums[right] == nums[right - 1]) right--;left++;
right--;
前两行和后两行顺序不能调换。
18. 四数之和
题目链接: 18. 四数之和
三数之和再多套一个遍历。不用哈希理由三数之和。
注意剪枝条件不同于三数之和,因为三数的target
是0
class Solution {
public:vector<vector<int>> fourSum(vector<int>& nums, int target) {vector<vector<int>> ret;sort(nums.begin(), nums.end());//排序for (int k = 0; k < nums.size(); k++) {if (nums[k] > target && nums[k] >= 0) break;//剪枝if (k > 0 && nums[k] == nums[k - 1]) continue;//k去重for (int i = k + 1; i < nums.size(); i++) {if (nums[k] + nums[i] > target && nums[k] + nums[i] >= 0) break;//剪枝。k+i是一个整体if (i > k + 1 && nums[i] == nums[i - 1]) continue;//i去重int left = i + 1, right = nums.size() - 1;while (left < right) {if ((long) nums[k] + nums[i] + nums[left] + nums[right] > target) right--;else if ((long) nums[k] + nums[i] + nums[left] + nums[right] < target) left++;else {ret.push_back(vector<int>{nums[k], nums[i], nums[left], nums[right]});while (left < right && nums[left] == nums[left + 1]) left++;//left去重while (left < right && nums[right] == nums[right - 1]) right--;//right去重right--;left++;}}}}return ret;}
};
if ((long) nums[k] + nums[i] + nums[left] + nums[right] > target)
long
是因为nums数组中的元素超过int
范围,导致溢出了。
相关文章:
算法Day07 | 454.四数相加II,383. 赎金信,15. 三数之和, 18. 四数之和
Day07 454.四数相加II383. 赎金信15. 三数之和18. 四数之和 454.四数相加II 题目链接:454.四数相加II 寻找两个数组之和,是否与另外两个数组之和有特定的关系。 因为数值可能跨度太大,选择使用下标表示为对应的数值大小,会很浪费…...
ps抠图、抠头发去背景等
方法一:背景橡皮擦 一、很早之前我们使用的是魔术棒工具,但现在我们可以使用Photoshop 有内置的“背景橡皮擦” 步骤: 第1步:在Photoshop中打开需要修的图。 第2步:单击并按住工具栏…...

计算机组成原理基础练习题第一章
有些计算机将一部分软件永恒地存于只读存储器中,称之为() A.硬件 B.软件C.固件 D.辅助存储器输入、输出装置以及外界的辅助存储器称为() A.操作系统 B.存储器 C.主机 D.外围设备完整的计算机系…...

[PyTorch][chapter 34][池化层与采样]
前言: 这里主要讲解一下卷积神经网络中的池化层与采样 目录 DownSampleMax poolingavg poolingupsampleReLu 1: DownSample 下采样,间隔一定行或者列进行采样,达到降维效果 早期LeNet-5 就采样该采样方式。 LeNet-5 2 Max pooling 最大值采样…...

Java进阶-字符串的使用
1.API 1.1API概述 什么是API API (Application Programming Interface) :应用程序编程接口 java中的API 指的就是 JDK 中提供的各种功能的 Java类,这些类将底层的实现封装了起来,我们不需要关心这些类是如何实现的,只需要…...

接口自动化框架对比 | 质量工程
一、前言 自动化测试是把将手工驱动的测试行为转化为机器自动执行,通常操作是在某一框架下进行代码编写,实现用例自动发现与执行,托管在CI/CD平台上,通过条件触发或手工触发,进行回归测试&线上监控,代替…...

谷歌浏览器network error解决方法
很多用户在使用谷歌浏览器时候会出现network error网页提示,很多用户不知道该如何处理这一问题,其实解决方法不止一种,小编整理了两种谷歌浏览器network error解决方法,一起来看看吧~ 谷歌浏览器network error解决方法࿱…...

自动化测试如何做?接口自动化测试框架必备的9个功能,测试老鸟总结...
目录:导读 前言一、Python编程入门到精通二、接口自动化项目实战三、Web自动化项目实战四、App自动化项目实战五、一线大厂简历六、测试开发DevOps体系七、常用自动化测试工具八、JMeter性能测试九、总结(尾部小惊喜) 前言 当你准备使用一个…...

ANR原理篇 - ANR原理总览
系列文章目录 提示:这里可以添加系列文章的所有文章的目录,目录需要自己手动添加 例如:第一章 Python 机器学习入门之pandas的使用 文章目录 系列文章目录前言ANR流程概览ANR触发机制一、service超时机制二、broadcast超时机制三、provider超…...

新版Mamba体验超快的软件安装
在一文掌握Conda软件安装:虚拟环境、软件通道、加速solving、跨服务器迁移中详细介绍的conda的基本使用和遇到问题的解决方式,也提到了mamba作为一个替代工具,可以很好的加速conda的solving environemnt过程。但有时也会遇到一个很尴尬的问题…...

LDAP配置与安装
LDAP配置与安装 一、安装LDAP1、安装OpenLDAP及相关依赖包2、查看OpenLDAP版本3、配置OpenLDAP数据库4、设置OpenLDAP的管理员密码5、修改配置文件5.1. 修改{2}hdb.ldif文件5.2. 修改{1}monitor.ldif文件5.3. 修改{-1}frontend.ldif文件 6、验证LDAP的基本配置7、修改LDAP文件权…...

1-Linux环境安装JDK
Linux环境安装JDK 准备: ① Linux 环境 本文中Linux环境为 CentOS Linux 7 可使用以下命令查询 linux 系统版本: hostnamectl② 准备JDK包 进入官网 https://www.oracle.com/java/technologies/downloads/#java17下载对应jdk包 此处使用以前下载的旧…...
通胀数据回落助金价小幅回升
现货黄金窄幅震荡,目前交投于2032.92美元/盎司附近。隔夜美国通胀数据弱于市场预期,市场对美联储6月份加息预期降温,美元指数走弱,金价一度冲高至2050关口附近,不过,随后金价回吐全部涨幅,并一度…...
正则表达式的基本语法以及技巧和示例
正则表达式(Regular Expression)是一种强大的文本模式匹配工具,它使用特定的语法规则来描述和匹配字符串。在实际应用中,正则表达式可以用于搜索、替换、验证和分割文本数据。本文将详细解释正则表达式的语法和常用的使用示例。 …...

蓝牙耳机怎么挑选?小编分享2023畅销蓝牙耳机排行榜
蓝牙耳机怎么挑选?蓝牙、音质、续航、佩戴是蓝牙耳机选购时最重要的四大维度,这几年随着技术的成熟体验有了很大改善,但挑选的时候仍然要仔细对比,不然容易踩雷。小编根据销量整理了蓝牙耳机排行榜,一起看看最受消费者…...

Linux快照太有趣了!
1.首先介绍一下什么是Linux快照 VMware 的菜单栏中有虚拟机快照这个选项,形象来说快照就相当于一个备份文件,记录的是虚拟机运行到某一节点时的状态,在虚拟机的使用过程中如果发生了意外,比如系统崩溃或系统异常,此时…...

【改进粒子群优化算法】自适应惯性权重粒子群算法(Matlab代码实现)
💥💥💞💞欢迎来到本博客❤️❤️💥💥 🏆博主优势:🌞🌞🌞博客内容尽量做到思维缜密,逻辑清晰,为了方便读者。 ⛳️座右铭&a…...

ROS 下 激光扫描仪 YDLidar-G4 使用
环境配置: ubuntu20.04 LTS ROS noetic 编程工具:vs code,远程通过ssh访问 扫描仪:YDLidar-G4 YDLidar驱动: YDLidar SDK YDLidar ROS 功能包 此环境包含树莓派,以下过程在树莓派3B上测试通过,…...
智能边缘:数字化时代的关键战略之一
随着物联网、云计算和人工智能等技术的快速发展,智能边缘已经成为了许多企业和组织中的重要部分。智能边缘旨在将物联网设备、应用程序和数据存储集成到一个统一的、移动的计算环境中,以提高效率、降低成本并增强数据安全性。在本文中,我们将…...

EasyRecovery16中文最新版电脑数据恢复软件下载使用教程
EasyRecovery如果需要使用它来恢复数据,请注意,尤其是当需要恢复的数据文件非常重要时,建议使用软件EasyRecovery以保障数据安全。共有三个版本,分别是个人版、专业版、企业版,这三种都可以免费下载并使用,…...
挑战杯推荐项目
“人工智能”创意赛 - 智能艺术创作助手:借助大模型技术,开发能根据用户输入的主题、风格等要求,生成绘画、音乐、文学作品等多种形式艺术创作灵感或初稿的应用,帮助艺术家和创意爱好者激发创意、提高创作效率。 - 个性化梦境…...
多模态商品数据接口:融合图像、语音与文字的下一代商品详情体验
一、多模态商品数据接口的技术架构 (一)多模态数据融合引擎 跨模态语义对齐 通过Transformer架构实现图像、语音、文字的语义关联。例如,当用户上传一张“蓝色连衣裙”的图片时,接口可自动提取图像中的颜色(RGB值&…...

Module Federation 和 Native Federation 的比较
前言 Module Federation 是 Webpack 5 引入的微前端架构方案,允许不同独立构建的应用在运行时动态共享模块。 Native Federation 是 Angular 官方基于 Module Federation 理念实现的专为 Angular 优化的微前端方案。 概念解析 Module Federation (模块联邦) Modul…...

C++ 求圆面积的程序(Program to find area of a circle)
给定半径r,求圆的面积。圆的面积应精确到小数点后5位。 例子: 输入:r 5 输出:78.53982 解释:由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982,因为我们只保留小数点后 5 位数字。 输…...

用机器学习破解新能源领域的“弃风”难题
音乐发烧友深有体会,玩音乐的本质就是玩电网。火电声音偏暖,水电偏冷,风电偏空旷。至于太阳能发的电,则略显朦胧和单薄。 不知你是否有感觉,近两年家里的音响声音越来越冷,听起来越来越单薄? —…...
代码随想录刷题day30
1、零钱兑换II 给你一个整数数组 coins 表示不同面额的硬币,另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回 0 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带…...

C# 表达式和运算符(求值顺序)
求值顺序 表达式可以由许多嵌套的子表达式构成。子表达式的求值顺序可以使表达式的最终值发生 变化。 例如,已知表达式3*52,依照子表达式的求值顺序,有两种可能的结果,如图9-3所示。 如果乘法先执行,结果是17。如果5…...
怎么让Comfyui导出的图像不包含工作流信息,
为了数据安全,让Comfyui导出的图像不包含工作流信息,导出的图像就不会拖到comfyui中加载出来工作流。 ComfyUI的目录下node.py 直接移除 pnginfo(推荐) 在 save_images 方法中,删除或注释掉所有与 metadata …...
在 Spring Boot 项目里,MYSQL中json类型字段使用
前言: 因为程序特殊需求导致,需要mysql数据库存储json类型数据,因此记录一下使用流程 1.java实体中新增字段 private List<User> users 2.增加mybatis-plus注解 TableField(typeHandler FastjsonTypeHandler.class) private Lis…...
面试高频问题
文章目录 🚀 消息队列核心技术揭秘:从入门到秒杀面试官1️⃣ Kafka为何能"吞云吐雾"?性能背后的秘密1.1 顺序写入与零拷贝:性能的双引擎1.2 分区并行:数据的"八车道高速公路"1.3 页缓存与批量处理…...