算法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以保障数据安全。共有三个版本,分别是个人版、专业版、企业版,这三种都可以免费下载并使用,…...

(二)TensorRT-LLM | 模型导出(v0.20.0rc3)
0. 概述 上一节 对安装和使用有个基本介绍。根据这个 issue 的描述,后续 TensorRT-LLM 团队可能更专注于更新和维护 pytorch backend。但 tensorrt backend 作为先前一直开发的工作,其中包含了大量可以学习的地方。本文主要看看它导出模型的部分&#x…...

理解 MCP 工作流:使用 Ollama 和 LangChain 构建本地 MCP 客户端
🌟 什么是 MCP? 模型控制协议 (MCP) 是一种创新的协议,旨在无缝连接 AI 模型与应用程序。 MCP 是一个开源协议,它标准化了我们的 LLM 应用程序连接所需工具和数据源并与之协作的方式。 可以把它想象成你的 AI 模型 和想要使用它…...
Leetcode 3577. Count the Number of Computer Unlocking Permutations
Leetcode 3577. Count the Number of Computer Unlocking Permutations 1. 解题思路2. 代码实现 题目链接:3577. Count the Number of Computer Unlocking Permutations 1. 解题思路 这一题其实就是一个脑筋急转弯,要想要能够将所有的电脑解锁&#x…...

家政维修平台实战20:权限设计
目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系,主要是分成几个表,用户表我们是记录用户的基础信息,包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题,不同的角色…...

Vue2 第一节_Vue2上手_插值表达式{{}}_访问数据和修改数据_Vue开发者工具
文章目录 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染2. 插值表达式{{}}3. 访问数据和修改数据4. vue响应式5. Vue开发者工具--方便调试 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染 准备容器引包创建Vue实例 new Vue()指定配置项 ->渲染数据 准备一个容器,例如: …...
Neo4j 集群管理:原理、技术与最佳实践深度解析
Neo4j 的集群技术是其企业级高可用性、可扩展性和容错能力的核心。通过深入分析官方文档,本文将系统阐述其集群管理的核心原理、关键技术、实用技巧和行业最佳实践。 Neo4j 的 Causal Clustering 架构提供了一个强大而灵活的基石,用于构建高可用、可扩展且一致的图数据库服务…...
css的定位(position)详解:相对定位 绝对定位 固定定位
在 CSS 中,元素的定位通过 position 属性控制,共有 5 种定位模式:static(静态定位)、relative(相对定位)、absolute(绝对定位)、fixed(固定定位)和…...

涂鸦T5AI手搓语音、emoji、otto机器人从入门到实战
“🤖手搓TuyaAI语音指令 😍秒变表情包大师,让萌系Otto机器人🔥玩出智能新花样!开整!” 🤖 Otto机器人 → 直接点明主体 手搓TuyaAI语音 → 强调 自主编程/自定义 语音控制(TuyaAI…...
[Java恶补day16] 238.除自身以外数组的乘积
给你一个整数数组 nums,返回 数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法,且在 O(n) 时间复杂度…...

算法:模拟
1.替换所有的问号 1576. 替换所有的问号 - 力扣(LeetCode) 遍历字符串:通过外层循环逐一检查每个字符。遇到 ? 时处理: 内层循环遍历小写字母(a 到 z)。对每个字母检查是否满足: 与…...