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

【算法刷题】Day10

文章目录

  • 15. 三数之和
    • 题干:
    • 算法原理:
      • 1、排序 + 暴力枚举 + 利用set 去重
      • 2、排序 + 双指针
    • 代码:
  • 18. 18. 四数之和
    • 题干:
    • 算法原理:
      • 1、排序 + 暴力枚举 + 利用set 去重
      • 2、排序 + 双指针
    • 代码:

15. 三数之和

在这里插入图片描述
在这里插入图片描述
原题链接

题干:

存在一个三元组,满足
i != j、i != k 且 j != k
nums[i] + nums[j] + nums[k] == 0

算法原理:

1、排序 + 暴力枚举 + 利用set 去重

这个方法就是先循环,用几个 for 循环暴力枚举,然后放到 HashSet 中去重
但是这个方法时间复杂度很高,达到了O(N3)

2、排序 + 双指针

(1)排序
这里进行排序是为了从前向后遍历的时候,可以更好的用双指针进行操作
在这里插入图片描述
(2)固定一个数 a
这个 a 必须要大于等于 0,因为题目要求三数相加等于 0

(3)在该数后面的区间内,利用“双指针算法”快速找到两个数的和等于 -a 即可
在这里插入图片描述

(4)处理细节问题

  • 不要漏任何一个组合
    在 left 和 right 向中间走的时候,找到一个数等于固定的数的负数,不能停下,继续缩小区间,寻找下一个

  • 去重
    由于题目要求,不能返回相同的数组,所以要求去重
    这样就可以找到一种结果之后,left 和 right 指针要跳过重复元素
    当使用完一次双指正算法之后,也要跳过重复元素
    但要注意避免越界!!!
    在这里插入图片描述

代码:

   public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> ret = new ArrayList<>();//1.排序Arrays.sort(nums);int n = nums.length;//2.利用双指针for (int i = 0; i < n;) {int left = i + 1;int right = n - 1;int target = -nums[i];if (nums[i] > 0) {break;}while (left < right) {int sum = nums[left] + nums[right];if (sum < target) {left++;}else if (sum > target) {right--;}else {ret.add(new ArrayList<Integer>(Arrays.asList(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--;}}}i++;while (i < n && nums[i] == nums[i-1]) {i++;}}return ret;}

在这里插入图片描述

18. 18. 四数之和

在这里插入图片描述

题干:

这道题跟上面的三数之和非常相似,因此下面的解题思路也是非常相似

nums[a] + nums[b] + nums[c] + nums[d] == target

算法原理:

1、排序 + 暴力枚举 + 利用set 去重

这个算法依然是超时的,我们主要看第二种

2、排序 + 双指针

(1)排序

(2)在 a 后面的区间内,利用“三数之和”找到三个数(和上面题的方法一样),使这三个数的和等于 target - a

(3)处理细节问题

  • 不漏
  • 去重

代码:

public List<List<Integer>> fourSum(int[] nums, int target) {List<List<Integer>> ret = new ArrayList<>();int n = nums.length;//1.排序Arrays.sort(nums);//2.双指针for (int i = 0; i < n;) {long t1 = (long)target - nums[i];for (int j = i + 1; j < n;) {long t2 = t1 - nums[j];int left = j + 1;int right = n - 1;while (left < right) {int sum = nums[left] + nums[right];if (sum > t2) {right--;}else if (sum < t2) {left++;}else {ret.add(Arrays.asList(nums[i],nums[j],nums[left],nums[right]));left++;right--;while (left < right && nums[left] == nums[left-1]) {left++;}while (left < right && nums[right] == nums[right+1]) {right--;}}}j++;while (j < n && nums[j] == nums[j-1]) {j++;}}i++;while (i < n && nums[i] == nums[i-1]) {i++;}}return ret;}

在这里插入图片描述

相关文章:

【算法刷题】Day10

文章目录 15. 三数之和题干&#xff1a;算法原理&#xff1a;1、排序 暴力枚举 利用set 去重2、排序 双指针 代码&#xff1a; 18. 18. 四数之和题干&#xff1a;算法原理&#xff1a;1、排序 暴力枚举 利用set 去重2、排序 双指针 代码&#xff1a; 15. 三数之和 原题链…...

SAP 如何检查已安装的SAP UI5 版本

第一个方法是直接从FLP中查看 但是部分高版本的FLP中没有这个about&#xff0c; 那么在当前界面可以使用&#xff1a;CTRL ALT SHIFT S 查看当前版本 根据此版本&#xff0c;去进行你的UI5的开发吧...

15、 深度学习之正向传播和反向传播

上一节介绍了训练和推理的概念,这一节接着训练和推理的概念讲一下,神经网络的正向传播和反向传播。 其实单看正向传播和反向传播这两个概念,很好理解。 正向传播(Forward Propagation)是指从输入层到输出层的数据流动过程,而反向传播(Backpropagation)是指数据从输出…...

微信小程序中复制文本

在微信小程序中&#xff0c;可以使用wx.setClipboardData()方法来实现复制文本内容的功能。以下是一个示例代码&#xff1a; // 点击按钮触发复制事件 copyText: function() {var that this;wx.setClipboardData({data: 要复制的文本内容,success: function(res) {wx.showToa…...

vue3学习--初始

...

cmake和vscode 下的cmake的使用详解(二)

第四讲&#xff1a; GDB 调试器 前言&#xff1a; GDB(GNU Debugger) 是一个用来 调试 C/C 程序 的功能强大的 调试器 &#xff0c;是 Linux 系统开发 C/C 最常用的调试器 程序员可以 使用 GDB 来跟踪程序中的错误 &#xff0c;从而减少程序员的工作量。 Linux 开发 C/C …...

集成开发环境 PyCharm 的安装【侯小啾python领航班系列(二)】

集成开发环境PyCharm的安装【侯小啾python领航计划系列(二)】 大家好,我是博主侯小啾, 🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹…...

mysql从库设置为只读

直奔主题&#xff0c;mysql设置为只读后&#xff0c;无法增删改。 设置命令&#xff1a; mysql> set global read_only1; #1是只读&#xff0c;0是读写 mysql> show global variables like %read_only%; 以下是相关说明&#xff1a; 1、对于数据库读写状态&#xf…...

.NET6实现破解Modbus poll点表配置文件

📢欢迎点赞 :👍 收藏 ⭐留言 📝 如有错误敬请指正,赐人玫瑰,手留余香!📢本文作者:由webmote 原创📢作者格言:新的征程,我们面对的不仅仅是技术还有人心,人心不可测,海水不可量,唯有技术,才是深沉黑夜中的一座闪烁的灯塔 !序言 Modbus 协议是工控领域常见…...

【零基础入门Docker】Dockerfile中的USER指令以及dockerfile命令详解

✍面向读者&#xff1a;所有人 ✍所属专栏&#xff1a;Docker零基础入门专栏 目录 第 1 步&#xff1a;创建 Dockerfile 第 2 步&#xff1a;构建 Docker 镜像 第 3 步&#xff1a;运行 Docker 容器 第 4 步&#xff1a;验证输出 dockerfile命令详解 最佳实践 默认情况下…...

R语言期末考试复习二

上篇文章的后续&#xff01;&#xff01;&#xff01;&#xff01; http://t.csdnimg.cn/sqvYD 1.给向量vec1设置名为"A","B","C","D","E","F","G"。 2.将矩阵mat1的行名设置为"Row1"&#…...

golang Pool实战与底层实现

使用的go版本为 go1.21.2 首先我们写一个简单的Pool的使用代码 package mainimport "sync"var bytePool sync.Pool{New: func() interface{} {b : make([]byte, 1024)return &b}, }func main() {for j : 0; j < 10; j {obj : bytePool.Get().(*[]byte) // …...

WPF使用Prism框架批量注册Page,Window,UserControl等视图组件

前言 为了提高Prism框架下面的注册视图资源的简单性和提高后期可维护性,本文将使用prism自带的通过反射来批量注册视图资源,帮助我们快速高效的完成开发任务。 我们平常注册前端视图资源,一般都是在RegisterTypes方法里面,使用IContainerRegistry 的RegisterForNavigation…...

网络安全应急响应-Server2228(环境+解析)

网络安全应急响应 任务环境说明: 服务器场景:Server2228(开放链接)用户名:root,密码:p@ssw0rd123...

[WP] ISCTF2023 Web 部分题解

圣杯战争!!! 反序列化伪协议读取 where_is_the_flag 环境变量根目录当前目录 绕进你的心里 利用正则最大回溯绕过 easy_website or select 用双写绕过 空格用/**/绕&#xff0c;报错注入 wafr codesystem(ca\t /f*) webinclude 扫描得到index.bak备份文件打开为加密的代码 写…...

uniapp之Vue3配置跨域(代理)

在uni-app中&#xff0c;我们可以使用vue.config.js文件来配置跨域&#xff08;代理&#xff09;。以下是一个示例&#xff1a; // vue.config.js module.exports {devServer: {proxy: {/api: { // 这里填写你要代理的接口前缀&#xff0c;例如/apitarget: http://localhost:…...

单片机实验(三)

前言 实验一&#xff1a;利用定时器T1的中断控制P1.7引脚输出音频信号&#xff0c;启动蜂鸣器发出一段熟悉的与众不同的具有10个音节的音乐音频。 实验二&#xff1a;使用定时器/计数器来实现一个LCD显示年、月、日、星期 、时、分、秒的电子表&#xff0c;要求时和分可以方便…...

Python 2进制按位取反

根据一checksum算法需要将一些参数按位取反 例&#xff1a;参数 13 数字13二进制为1101 [((x)) for x in str(bin(13))] [0, b, 1, 1, 0, 1] 除去0b字符串然后按位取反得到0010 [(1^int(x)) for x in str(bin(13)).replace(0b,)] [0, 0, 1, 0]然后将得到的2进制转换成十进制…...

【用Python根据用户名和手机号码生成Hash值并创建.cs .h和xlsx文件】

用Python根据用户名和手机号码生成Hash值并创建C Sharp .cs、嵌入式.h和xlsx表格文件 用Python根据用户名和手机号码生成Hash值并创建C Sharp .cs、嵌入式.h和xlsx表格文件&#xff0c;主要是为每个用户创建一个pubkey&#xff0c;并输出C Sharp C#和嵌入式 Keil的工程文件 pub…...

<Linux>(极简关键、省时省力)《Linux操作系统原理分析之存储管理(2)》(15)

[TOC](《Linux操作系统原理分析之存储管理&#xff08;2&#xff09;》&#xff08;15&#xff09; 5 存储管理5.4 分页存储管理5.4.1 纯分页存储管理a.页&#xff08;页面&#xff09;和物理块&#xff08;帧&#xff09;b. 页面大小c. 逻辑地址结构 5.5 存储扩充技术5.5.2 交…...

【大模型RAG】拍照搜题技术架构速览:三层管道、两级检索、兜底大模型

摘要 拍照搜题系统采用“三层管道&#xff08;多模态 OCR → 语义检索 → 答案渲染&#xff09;、两级检索&#xff08;倒排 BM25 向量 HNSW&#xff09;并以大语言模型兜底”的整体框架&#xff1a; 多模态 OCR 层 将题目图片经过超分、去噪、倾斜校正后&#xff0c;分别用…...

零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?

一、核心优势&#xff1a;专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发&#xff0c;是一款收费低廉但功能全面的Windows NAS工具&#xff0c;主打“无学习成本部署” 。与其他NAS软件相比&#xff0c;其优势在于&#xff1a; 无需硬件改造&#xff1a;将任意W…...

Linux 文件类型,目录与路径,文件与目录管理

文件类型 后面的字符表示文件类型标志 普通文件&#xff1a;-&#xff08;纯文本文件&#xff0c;二进制文件&#xff0c;数据格式文件&#xff09; 如文本文件、图片、程序文件等。 目录文件&#xff1a;d&#xff08;directory&#xff09; 用来存放其他文件或子目录。 设备…...

【人工智能】神经网络的优化器optimizer(二):Adagrad自适应学习率优化器

一.自适应梯度算法Adagrad概述 Adagrad&#xff08;Adaptive Gradient Algorithm&#xff09;是一种自适应学习率的优化算法&#xff0c;由Duchi等人在2011年提出。其核心思想是针对不同参数自动调整学习率&#xff0c;适合处理稀疏数据和不同参数梯度差异较大的场景。Adagrad通…...

渲染学进阶内容——模型

最近在写模组的时候发现渲染器里面离不开模型的定义,在渲染的第二篇文章中简单的讲解了一下关于模型部分的内容,其实不管是方块还是方块实体,都离不开模型的内容 🧱 一、CubeListBuilder 功能解析 CubeListBuilder 是 Minecraft Java 版模型系统的核心构建器,用于动态创…...

Frozen-Flask :将 Flask 应用“冻结”为静态文件

Frozen-Flask 是一个用于将 Flask 应用“冻结”为静态文件的 Python 扩展。它的核心用途是&#xff1a;将一个 Flask Web 应用生成成纯静态 HTML 文件&#xff0c;从而可以部署到静态网站托管服务上&#xff0c;如 GitHub Pages、Netlify 或任何支持静态文件的网站服务器。 &am…...

【android bluetooth 框架分析 04】【bt-framework 层详解 1】【BluetoothProperties介绍】

1. BluetoothProperties介绍 libsysprop/srcs/android/sysprop/BluetoothProperties.sysprop BluetoothProperties.sysprop 是 Android AOSP 中的一种 系统属性定义文件&#xff08;System Property Definition File&#xff09;&#xff0c;用于声明和管理 Bluetooth 模块相…...

CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云

目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...

ios苹果系统,js 滑动屏幕、锚定无效

现象&#xff1a;window.addEventListener监听touch无效&#xff0c;划不动屏幕&#xff0c;但是代码逻辑都有执行到。 scrollIntoView也无效。 原因&#xff1a;这是因为 iOS 的触摸事件处理机制和 touch-action: none 的设置有关。ios有太多得交互动作&#xff0c;从而会影响…...

第 86 场周赛:矩阵中的幻方、钥匙和房间、将数组拆分成斐波那契序列、猜猜这个单词

Q1、[中等] 矩阵中的幻方 1、题目描述 3 x 3 的幻方是一个填充有 从 1 到 9 的不同数字的 3 x 3 矩阵&#xff0c;其中每行&#xff0c;每列以及两条对角线上的各数之和都相等。 给定一个由整数组成的row x col 的 grid&#xff0c;其中有多少个 3 3 的 “幻方” 子矩阵&am…...