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

算法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 题目链接&#xff1a;454.四数相加II 寻找两个数组之和&#xff0c;是否与另外两个数组之和有特定的关系。 因为数值可能跨度太大&#xff0c;选择使用下标表示为对应的数值大小&#xff0c;会很浪费…...

ps抠图、抠头发去背景等

方法一&#xff1a;背景橡皮擦 一、很早之前我们使用的是魔术棒工具&#xff0c;但现在我们可以使用Photoshop 有内置的“背景橡皮擦” 步骤&#xff1a; 第1步&#xff1a;在Photoshop中打开需要修的图。 第2步&#xff1a;单击并按住工具栏…...

计算机组成原理基础练习题第一章

有些计算机将一部分软件永恒地存于只读存储器中&#xff0c;称之为&#xff08;&#xff09; A.硬件    B.软件C.固件    D.辅助存储器输入、输出装置以及外界的辅助存储器称为&#xff08;&#xff09; A.操作系统    B.存储器 C.主机      D.外围设备完整的计算机系…...

[PyTorch][chapter 34][池化层与采样]

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

Java进阶-字符串的使用

1.API 1.1API概述 什么是API ​ API (Application Programming Interface) &#xff1a;应用程序编程接口 java中的API ​ 指的就是 JDK 中提供的各种功能的 Java类&#xff0c;这些类将底层的实现封装了起来&#xff0c;我们不需要关心这些类是如何实现的&#xff0c;只需要…...

接口自动化框架对比 | 质量工程

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

谷歌浏览器network error解决方法

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

自动化测试如何做?接口自动化测试框架必备的9个功能,测试老鸟总结...

目录&#xff1a;导读 前言一、Python编程入门到精通二、接口自动化项目实战三、Web自动化项目实战四、App自动化项目实战五、一线大厂简历六、测试开发DevOps体系七、常用自动化测试工具八、JMeter性能测试九、总结&#xff08;尾部小惊喜&#xff09; 前言 当你准备使用一个…...

ANR原理篇 - ANR原理总览

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

新版Mamba体验超快的软件安装

在一文掌握Conda软件安装&#xff1a;虚拟环境、软件通道、加速solving、跨服务器迁移中详细介绍的conda的基本使用和遇到问题的解决方式&#xff0c;也提到了mamba作为一个替代工具&#xff0c;可以很好的加速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 准备&#xff1a; ① Linux 环境 本文中Linux环境为 CentOS Linux 7 可使用以下命令查询 linux 系统版本&#xff1a; hostnamectl② 准备JDK包 进入官网 https://www.oracle.com/java/technologies/downloads/#java17下载对应jdk包 此处使用以前下载的旧…...

通胀数据回落助金价小幅回升

现货黄金窄幅震荡&#xff0c;目前交投于2032.92美元/盎司附近。隔夜美国通胀数据弱于市场预期&#xff0c;市场对美联储6月份加息预期降温&#xff0c;美元指数走弱&#xff0c;金价一度冲高至2050关口附近&#xff0c;不过&#xff0c;随后金价回吐全部涨幅&#xff0c;并一度…...

正则表达式的基本语法以及技巧和示例

正则表达式&#xff08;Regular Expression&#xff09;是一种强大的文本模式匹配工具&#xff0c;它使用特定的语法规则来描述和匹配字符串。在实际应用中&#xff0c;正则表达式可以用于搜索、替换、验证和分割文本数据。本文将详细解释正则表达式的语法和常用的使用示例。 …...

蓝牙耳机怎么挑选?小编分享2023畅销蓝牙耳机排行榜

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

Linux快照太有趣了!

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

【改进粒子群优化算法】自适应惯性权重粒子群算法(Matlab代码实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…...

ROS 下 激光扫描仪 YDLidar-G4 使用

环境配置&#xff1a; ubuntu20.04 LTS ROS noetic 编程工具&#xff1a;vs code&#xff0c;远程通过ssh访问 扫描仪&#xff1a;YDLidar-G4 YDLidar驱动&#xff1a; YDLidar SDK YDLidar ROS 功能包 此环境包含树莓派&#xff0c;以下过程在树莓派3B上测试通过&#xff0c…...

智能边缘:数字化时代的关键战略之一

随着物联网、云计算和人工智能等技术的快速发展&#xff0c;智能边缘已经成为了许多企业和组织中的重要部分。智能边缘旨在将物联网设备、应用程序和数据存储集成到一个统一的、移动的计算环境中&#xff0c;以提高效率、降低成本并增强数据安全性。在本文中&#xff0c;我们将…...

EasyRecovery16中文最新版电脑数据恢复软件下载使用教程

EasyRecovery如果需要使用它来恢复数据&#xff0c;请注意&#xff0c;尤其是当需要恢复的数据文件非常重要时&#xff0c;建议使用软件EasyRecovery以保障数据安全。共有三个版本&#xff0c;分别是个人版、专业版、企业版&#xff0c;这三种都可以免费下载并使用&#xff0c;…...

(二)TensorRT-LLM | 模型导出(v0.20.0rc3)

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

理解 MCP 工作流:使用 Ollama 和 LangChain 构建本地 MCP 客户端

&#x1f31f; 什么是 MCP&#xff1f; 模型控制协议 (MCP) 是一种创新的协议&#xff0c;旨在无缝连接 AI 模型与应用程序。 MCP 是一个开源协议&#xff0c;它标准化了我们的 LLM 应用程序连接所需工具和数据源并与之协作的方式。 可以把它想象成你的 AI 模型 和想要使用它…...

Leetcode 3577. Count the Number of Computer Unlocking Permutations

Leetcode 3577. Count the Number of Computer Unlocking Permutations 1. 解题思路2. 代码实现 题目链接&#xff1a;3577. Count the Number of Computer Unlocking Permutations 1. 解题思路 这一题其实就是一个脑筋急转弯&#xff0c;要想要能够将所有的电脑解锁&#x…...

家政维修平台实战20:权限设计

目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系&#xff0c;主要是分成几个表&#xff0c;用户表我们是记录用户的基础信息&#xff0c;包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题&#xff0c;不同的角色&#xf…...

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 中&#xff0c;元素的定位通过 position 属性控制&#xff0c;共有 5 种定位模式&#xff1a;static&#xff08;静态定位&#xff09;、relative&#xff08;相对定位&#xff09;、absolute&#xff08;绝对定位&#xff09;、fixed&#xff08;固定定位&#xff09;和…...

涂鸦T5AI手搓语音、emoji、otto机器人从入门到实战

“&#x1f916;手搓TuyaAI语音指令 &#x1f60d;秒变表情包大师&#xff0c;让萌系Otto机器人&#x1f525;玩出智能新花样&#xff01;开整&#xff01;” &#x1f916; Otto机器人 → 直接点明主体 手搓TuyaAI语音 → 强调 自主编程/自定义 语音控制&#xff08;TuyaAI…...

[Java恶补day16] 238.除自身以外数组的乘积

给你一个整数数组 nums&#xff0c;返回 数组 answer &#xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法&#xff0c;且在 O(n) 时间复杂度…...

算法:模拟

1.替换所有的问号 1576. 替换所有的问号 - 力扣&#xff08;LeetCode&#xff09; ​遍历字符串​&#xff1a;通过外层循环逐一检查每个字符。​遇到 ? 时处理​&#xff1a; 内层循环遍历小写字母&#xff08;a 到 z&#xff09;。对每个字母检查是否满足&#xff1a; ​与…...