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

LeetCode430周赛T3

news 来源：原创 2025/7/25 5:21:04

题目描述

给定一个只包含正整数的数组 nums，我们需要找到其中的特殊子序列。特殊子序列是一个长度为4的子序列，用下标 (p, q, r, s) 表示，它们满足以下条件：

索引顺序：p < q < r < s，且相邻坐标之间至少间隔一个数字，即 q - p > 1，r - q > 1，s - r > 1。
乘积关系：nums[p] * nums[r] == nums[q] * nums[s]。

子序列指的是从原数组中删除零个或多个元素后，剩下元素不改变顺序组成的序列。

示例 1：

输入：nums = [1,2,3,4,3,6,1]
输出：1
解释：
nums 中只有一个特殊子序列。
(p, q, r, s) = (0, 2, 4, 6) ：对应的元素为 (1, 3, 3, 1)。
nums[p] * nums[r] = 1 * 3 = 3
nums[q] * nums[s] = 3 * 1 = 3

示例 2：

输入：nums = [3,4,3,4,3,4,3,4]
输出：3
解释：
nums 中共有三个特殊子序列。
1. (p, q, r, s) = (0, 2, 4, 6) ：对应元素为 (3, 3, 3, 3)。nums[p] * nums[r] = 3 * 3 = 9nums[q] * nums[s] = 3 * 3 = 9
2. (p, q, r, s) = (1, 3, 5, 7) ：对应元素为 (4, 4, 4, 4)。nums[p] * nums[r] = 4 * 4 = 16nums[q] * nums[s] = 4 * 4 = 16
3. (p, q, r, s) = (0, 2, 5, 7) ：对应元素为 (3, 3, 4, 4)。nums[p] * nums[r] = 3 * 4 = 12nums[q] * nums[s] = 3 * 4 = 12

提示：

7 <= nums.length <= 1000
1 <= nums[i] <= 1000

解题思路

为了高效地解决这个问题，我们需要利用数学和数据结构的结合。以下是详细的解题步骤：

问题转换：

题目要求 nums[p] * nums[r] == nums[q] * nums[s]，我们用a,b,c,d定义nums[p],nums[q],nums[r],num[s],可以将其转换为分数的形式：
$\frac{a}{b} = \frac{d}{c}$

这样，a 和 b 都在 c 和 d 的左边，便于使用前缀和后缀的方法进行分解和统计。
统计后缀中的最简分数：

首先，统计下标 [4, n−1] 中所有满足间隔至少一个数的数对 (c, d) 的最简分数，并记录到一个哈希表 suf 中。最简分数是指分子和分母互质的分数。如果分子和分母不互质，可以通过它们的最大公约数（GCD）进行约简。例如，分数 4/6 的最简分数是 2/3。
枚举并统计前缀中的最简分数：

然后，枚举 b 的位置，以及 b 左边满足间隔条件的 a，计算 a/b 的最简分数，并在 suf 中查找相等的最简分数的数量，将其累加到结果中。
动态更新后缀哈希表：

在从左向右枚举 b 的过程中，动态地维护和更新 suf 中的最简分数的个数，以保证统计的准确性。

代码实现

以下是基于上述思路的C++代码实现：

typedef long long LL;
class Solution {
public:long long numberOfSubsequences(vector<int>& nums) {int n = nums.size();LL res = 0;unordered_map<int,int> mp;// 预先统计所有 (c, d) 的最简分数for(int c = 4; c < n - 2; c ++) {for(int d = c + 2; d < n; d ++) {int gcd_val = __gcd(nums[c], nums[d]);int x = nums[c] / gcd_val;int y = nums[d] / gcd_val;mp[y << 16 | x ] ++;}}// 枚举 b，并统计满足条件的 afor(int b = 2; b <= n - 5; b ++) {for(int a = 0; a <= b - 2; a ++) {int gcd_val = __gcd(nums[a], nums[b]);int x = nums[a] / gcd_val;int y = nums[b] / gcd_val;res += mp[x << 16 | y];}// 更新后缀哈希表，移除已经不满足间隔条件的 (c, d)for(int d = b + 4; d < n; d ++) {int gcd_val = __gcd(nums[b + 2], nums[d]);int x = nums[b + 2] / gcd_val;int y = nums[d] / gcd_val;mp[y << 16 | x] --;}}return res;}
};

代码解析

哈希表 mp 的使用：

我们使用一个 unordered_map<int, int> 来存储后缀中所有 (c, d) 对应的最简分数。为了高效存储分数，我们将分子和分母合并成一个整数，其中分母占高16位，分子占低16位。
预处理后缀部分：

在初始阶段，我们遍历数组中满足条件的 (c, d) 对，并将其最简分数存入哈希表 mp。
枚举 b 并统计符合条件的 a：

对于每一个可能的 b，我们枚举所有满足条件的 a，计算其最简分数，并在哈希表 mp 中查找相等的最简分数的数量，将其累加到结果 res 中。
动态更新哈希表 mp：

随着 b 的增大，一些 (c, d) 对将不再满足间隔条件，需要从哈希表中移除。这通过减小相应分数的计数来实现。

复杂度分析

时间复杂度：O(n²)，其中 n 是数组的长度。主要来自于两层嵌套循环，分别用于预处理后缀和枚举 b 以及 a。
空间复杂度：O(n²)，用于存储哈希表 mp 中可能的所有 (c, d) 对的最简分数。

总结

通过巧妙地将乘积关系转换为分数关系，并利用哈希表高效地统计和查找最简分数，我们成功地将原本可能的四重循环优化为两重循环，大大提升了算法的效率。这种方法不仅适用于本题，也为解决类似的组合类问题提供了有益的思路。

LeetCode430周赛T3

题目描述给定一个只包含正整数的数组 nums，我们需要找到其中的特殊子序列。特殊子序列是一个长度为4的子序列，用下标 (p, q, r, s) 表示，它们满足以下条件： 索引顺序：p < q < r < s，且相邻坐标…...

编程日记 2025/7/25 5:21:04

网络：常用的以太网PHY芯片

常用的以太网PHY芯片（物理层芯片）主要负责将数字信号转换为适合在物理介质上传输的模拟信号。它们是网络设备（如交换机、路由器、网卡等）中的关键组件，通常工作在OSI模型中的物理层和数据链路层之间。以下是一些常见…...

编程日记 2025/7/24 10:01:25

1.首先尝试解决思路 npm报错就切换yarn ， yarn报错就先切换npm删除 node_modules 跟 package-lock.json文件重新下载依 2. 报错信息： Module build failed: Error: Missing binding D:\vue-element-admin\node_modules\node-sass\vendor\win32-x64-8…...

编程日记 2025/7/20 18:24:51

小猫可以吃面包吗？

在宠物饲养日益普及的当下，小猫的饮食健康成为众多铲屎官关注的焦点。其中，小猫是否可以吃面包这一问题引发了不少讨论。从面包的成分来看，其主要原料是面粉、水、酵母和盐，部分还会添加糖、油脂、鸡蛋、牛奶等。面粉富含碳水化…...

编程日记 2025/7/24 19:01:36

ACPI PM Timer

ACPI PM Timer 概述： ACPI PM Timer是一个非常简单的计时器，它以 3.579545 MHz 运行，在计数器溢出时生成系统控制中断（SCI）。它精度较低，建议使用其他定时器，如HPET或APIC定时器。检测ACPI P…...

编程日记 2025/7/24 15:34:53

算法学习（19）—— 队列与 BFS

关于bfs bfs又称宽搜，全称是“宽度优先遍历”，然后就是关于bfs的三个说法：“宽度优先搜索”，“宽度优先遍历”，“层序遍历”，这三个都是同一个东西，前面我们介绍了大量的深度优先遍历的题目已经…...

编程日记 2025/7/25 9:04:20

python|利用ffmpeg按顺序合并指定目录内的ts文件

前言： 有的时候我们利用爬虫爬取到的ts文件很多，但ts文件只是视频片段，并且这些视频片段是需要按照一定的顺序合并的，通常ts文件合并输出格式为mp4格式因此，本文介绍利用python，调用ffmpeg来批量的按自己…...

编程日记 2025/7/23 21:52:30

腾讯音乐：说说Redis脑裂问题？

Redis 脑裂问题是指，在 Redis 哨兵模式或集群模式中，由于网络原因，导致主节点（Master）与哨兵（Sentinel）和从节点（Slave）的通讯中断，此时哨兵就会误以为主节点…...

编程日记 2025/7/24 20:02:04

jmeter并发用户逐步递增压测找性能拐点

jmeter并发用户逐步递增压测找性能拐点目的： 使用逐层递增的并发压力进行测试，找到单功能的性能拐点（一般需要包含四组测试结果，拐点前一组，拐点一组，拐点后两组），统计响应时间、…...

编程日记 2025/7/25 8:56:03

跟着问题学3.2——Fast R-CNN详解及代码实战

R-CNN的不足 2014年，Ross Girshick提出RCNN，成为目标检测领域的开山之作。一年后，借鉴空间金字塔池化思想，Ross Girshick推出设计更为巧妙的Fast RCNN（https://github.com/rbgirshick/fast-rcnn）&#xff…...

编程日记 2025/7/21 15:16:10

【yolov5】实现FPS游戏人物检测，并定位到矩形框上中部分，实现自瞄

介绍本人机器学习小白，通过语言大模型百度进行搜索，磕磕绊绊的实现了初步效果，能有一些锁头效果，但识别速度不是非常快，且没有做敌友区分，效果不是非常的理想，但在4399小游戏中爽一下还是可以…...

编程日记 2025/7/23 12:33:19

软考高级：磁盘阵列（RAID）

** 概念讲解 ** 磁盘阵列是由多个磁盘组合成的一个大容量存储设备。它主要有以下几个作用： 提高存储容量：通过将多个磁盘组合在一起，可以获得比单个磁盘更大的存储容量。比如，一个磁盘的容量是 1TB，使用四个磁盘组成…...

编程日记 2025/7/25 9:05:55

梳理你的思路(从OOP到架构设计)_介绍Android的Java层应用框架05

1、认识ContentProvider...

编程日记 2025/7/25 9:01:36

torch.nn.LSTM介绍

torch.nn.LSTM 是 PyTorch 提供的一个高级封装，用于构建长短时记忆网络（LSTM）。相比手动实现，torch.nn.LSTM 更高效且支持批量处理、双向 LSTM、多层 LSTM 等功能，适合大多数实际应用。 LSTM基本原理门控机制（Gating Mechanism）是深度学习中常见的一种设计，用于控制信…...

编程日记 2025/7/25 9:00:16

React 组件的通信方式

在 React 应用开发中，组件之间的通信是构建复杂用户界面和交互逻辑的关键。正确地实现组件通信能够让我们的应用更加灵活和易于维护。以下是几种常见的 React组件通信方式。一、父子组件通信 1. 通过 props 传递数据（父组件向子组件传递数据&#xff0…...

编程日记 2025/7/23 2:46:47

关于覆铜与导线之间间距较小需要增加间距的解决方法

若该文为原创文章，转载请注明原文出处本文章博客地址：https://hpzwl.blog.csdn.net/article/details/144776995 长沙红胖子Qt（长沙创微智科）博文大全：开发技术集合（包含Qt实用技术、树莓派、三维、OpenCV…...

编程日记 2025/7/25 9:01:36

使用seata实现分布式事务管理

配置版本说明：springCloud Alibaba组件版本关系我用的是spring cloud Alibaba 2.2.1.RELEASE 、springboot 2.2.1.RELEASE、nacos 2.0.1、seata1.2.0,jdk1.8 seata 主要用于在分布式系统中对数据库进行事务回滚，保证全局事务的一致性。 seata的使用…...

编程日记 2025/7/25 9:03:31

【机器学习】深度学习（DNN）

文章目录 1. 神经网络结构2. 训练步骤3. 反向传播4. 为什么深，而不是宽（模块化）5. 初始化参数能否全为0？ 1. 神经网络结构输入层隐藏层：用于特征转换输出层：用于分类技巧：将网络中的参数写成矩…...

编程日记 2025/7/25 8:56:58

C++ 设计模式：门面模式（Facade Pattern）

链接：C 设计模式链接：C 设计模式 - 代理模式链接：C 设计模式 - 中介者链接：C 设计模式 - 适配器门面模式（Facade Pattern）是一种结构型设计模式，它为子系统中的一组接口提供一个一致&#…...

编程日记 2025/7/23 0:35:52

自动化测试之Pytest框架（万字详解）

Pytest测试框架一、前言二、安装2.1 命令行安装2.2 验证安装三、pytest设计测试用例注意点3.1 命名规范3.2 断言清晰3.3 fixture3.4 参数化设置3.5 测试隔离3.6 异常处理3.7 跳过或者预期失败3.8 mocking3.9 标记测试四、以案例初入pytest4.1 第一个pytest测试4.2 多个测试分…...

编程日记 2025/7/24 17:59:30

YOLOv10-1.1部分代码阅读笔记-conv.py

conv.py ultralytics\nn\modules\conv.py 目录 conv.py 1.所需的库和模块 2.def autopad(k, pNone, d1): 3.class Conv(nn.Module): 4.class Conv2(Conv): 5.class LightConv(nn.Module): 6.class DWConv(Conv): 7.class DWConvTranspose2d(nn.ConvTranspose2d)…...

编程日记 2025/7/24 5:17:12

大模型-Ollama使用相关的笔记

大模型-Ollama使用相关的笔记解决Ollama外网访问问题（配置ollama跨域访问）Postman请求样例解决Ollama外网访问问题（配置ollama跨域访问） 安装Ollama完毕后， /etc/systemd/system/ollama.service进行如下修改&#…...

编程日记 2025/7/22 8:17:45

【机器学习】概述

文章目录 1. 机器学习三步骤2. 机器学习图谱2.1 任务类型 (Task)2.2 模型选择 (Methods)2.3 学习场景 (Scenario) 1. 机器学习三步骤定义一个模型 (Define a set of function) 选择一组合适的函数来表示模型。评估模型好坏 (Goodness of function) 找到一个损失函数&#xf…...

编程日记 2025/7/19 11:56:37

什么是网络安全（Cybersecurity）？

不同组织机构对网络安全（Cybersecurity或Cyber Security）的定义不尽相同。从目标上来说，网络安全主要用于保护网络、计算机、移动设备、应用程序及数据等资产免受网络攻击，避免造成数据泄露、业务中断等安全问题。网络钓鱼、勒索…...

编程日记 2025/7/21 11:58:20

3_TCP/IP连接三次握手与断开四次挥手

TCP/IP 通信是网络通信的基础协议，分为以下主要步骤： 1、建立连接（三次握手） 目的：保证双方建立可靠的通信连接。过程： 1>客户端发送 SYN：客户端向服务器发送一个 SYN（同步&…...

编程日记 2025/7/24 20:26:28

基于单片机的电梯模拟控制系统

摘要：文章主要针对基于单片机的电梯模拟控制系统进行研究，指出基于单片机的电梯模拟控制系统应用优点，并在此基础上介绍单片机控制技术，分析单片机在电梯模拟控制系统中的具体应用。关键词：单片机；电梯；模拟控制系统 1 基于单片机的电梯模拟控制系统应用优点概述 1…...

编程日记 2025/7/23 18:17:38

区块链安全常见的攻击——ERC777 重入漏洞 (ERC777 Reentrancy Vulnerability)【5】

区块链安全常见的攻击分析——ERC777 重入漏洞 ERC777 Reentrancy Vulnerability【5】区块链安全常见的攻击合约和简单复现，附带详细分析——ERC777 重入漏洞 (ERC777 Reentrancy Vulnerability)【5】1.1 漏洞合约1.2 漏洞分析1.3 攻击分析1.4 攻击合约1.5 hardhat…...

编程日记 2025/7/23 0:19:08

MusicFree - 免费播放全网歌曲！无广告开源网络音乐聚合播放器 (安卓电脑版)

大家平常听歌可能都会在 QQ 音乐、网易云音乐、酷狗、喜马拉雅等不同平台来回切换，体验其实很烦。曾经推荐过不少“聚合”音乐应用，比如洛雪音乐助手、Listen1 等等。最近又有一个新选择了！MusicFree 是一款免费开源清爽无广告的音乐播放器…...

编程日记 2025/7/23 16:03:51

html+css+js网页设计美食美拾9个页面

htmlcssjs网页设计美食美拾9个页面网页作品代码简单，可使用任意HTML辑软件（如：Dreamweaver、HBuilder、Vscode 、Sublime 、Webstorm、Text 、Notepad 等任意html编辑软件进行运行及修改编辑等操作）。获取源码 1&#xff0…...

编程日记 2025/7/25 4:52:03

RustDesk内置ID服务器，Key教程

RustDesk内置ID服务器，Key教程首先需要准备一个域名，并将其指定到你的 rustdesk 服务器 ip 地址上，这里编译采用的是Github Actions ，说白了是就workflows，可以创建一些自动化的工作流程，例如代码的检查&a…...

编程日记 2025/7/21 6:51:00

Python学生管理系统（MySQL）

上篇文章介绍的Python学生管理系统GUI有不少同学觉得不错来找博主要源码，也有同学提到老师要增加数据库管理数据的功能，本篇文章就来介绍下python操作数据库，同时也对上次分享的学生管理系统进行了改进了，增加了数据库&#xff0c…...

编程日记 2025/7/20 12:53:49

Spring Boot 学习笔记

学习代码第一步：如何写 Hello world ？ 1、新建项目新建一个 Maven Java 工程，在 pom.xml 文件中添加 Spring Boot Maven 依赖： <parent><groupId>org.springframework.boot</groupId><artifactId>spri…...

编程日记 2025/7/24 1:54:38

UML统一建模语言测试题汇总

2-UML概念模型测试 (单选题, 1.0 分) UML中的关系不包括（）。 A. 抽象 B. 实现 C. 依赖 D. 关联我的答案:A正确答案: A 知识点： UML的构成 1.0分 (单选题, 1.0 分) 下列事物不属于UML结构事物的是（）。 A. 组件 B.…...

编程日记 2025/7/23 11:14:59

【微服务】SpringBoot 自定义消息转换器使用详解

目录一、前言二、SpringBoot 内容协商介绍 2.1 什么是内容协商 2.2 内容协商机制深入理解 2.2.1 内容协商产生的场景 2.3 内容协商实现的常用方式 2.3.1 前置准备 2.3.2 通过HTTP请求头 2.3.2.1 操作示例 2.3.3 通过请求参数三、SpringBoot 消息转换器介绍 3.1 H…...

编程日记 2025/7/24 4:48:25

数据结构（哈希表（中）纯概念版）

前言哈希表（Hash Table）是计算机科学中的一个基础而重要的数据结构，它广泛评估各种算法和系统中，尤其是在需要快速查找、插入和删除操作的场景中。由于其O( 1)的平均时间复杂度，存储表在性能要求较高的应用中表现得非…...

编程日记 2025/7/23 9:22:33

Node.js 工具：在 Windows 11 中配置 Node.js 的详细步骤

一、概述记录时间 [2024-12-25] 本文讲述如何在 Windows 11 中进行 Node.js 工具的安装和配置。以下是详细的步骤和说明。二、安装 Node.js 1. 官网下载通过官网，下载 Node.js，上面有好几种下载方式，文中下载的是 zip 压缩包。如图&…...

编程日记 2025/7/24 7:36:20

工作流并行网关退回思路

问题描述在设计工作流时遇到并行的流程，会出现并行流程的退回，这里记录下想到的解决思路，后续问题会记录在这里。流程图这里是一个简单的流程图： 并行退回思路若是正常流程退回，流程是： 获取回退…...

编程日记 2025/7/20 21:48:18

C#数学相关开发性能优化方法

本文Github地址：CSharp-MathOptimization.md 华为公司的C语言编程规范在开头就强调了： 一般情况下，代码的可阅读性高于性能，只有确定性能是瓶颈时，才应该主动优化。本文讲述的方法没有经过大项目和大公司的检验&…...

编程日记 2025/7/22 1:45:57

vulnhub jangow靶机

1.扫描靶机IP arp-scan -l如果扫不到靶机的话根据以下配置启动时点击第二个按回车继续选择第二个按e进入编辑删除"recovery nomodeset" 在末尾添加"quiet splash rw init/bin/bash" Ctrlx 启动进入如下界面 passwd修改root密码重启电脑登录root修…...

编程日记 2025/7/21 20:40:48

配置搜索无人机

升级ubuntu内核 https://www.bilibili.com/video/BV11X4y1h7qN/?spm_id_from333.337.search-card.all.click 进入四个内核文件并安装 sudo dpkg -i *.deb安装ROS，PX4，XTDrone，QGC https://blog.csdn.net/qq_45493236/article/details/13…...

编程日记 2025/7/24 13:47:05

2-6-1-1 QNX编程入门之进程和线程（四）

阅读前言本文以QNX系统官方的文档英文原版资料“Getting Started with QNX Neutrino: A Guide for Realtime Programmers”为参考，翻译和逐句校对后，对在QNX操作系统下进行应用程序开发及进行资源管理器编写开发等方面，进行了深度整理&…...

编程日记 2025/7/18 22:14:05

Vue开发环境搭建上篇：安装NVM和NPM(cpnm、pnpm)

文章目录引言I 安装NVM1.1 Windows系统安装NVM，实现Node.js多版本管理1.2 配置下载镜像1.3 NVM常用操作命令II NPM永久使用淘宝源安装 cnpm安装pnpm【推荐】see also: vscode常用插件引言淘宝镜像：http://npm.taobao.org 和 http://registry.npm.taobao.org 已在 2022.06.3…...

编程日记 2025/7/22 6:50:31

2.微服务灰度发布落地实践(agent实现)

文章目录前言java agent的介绍基础实现agent端 http服务实现agent端api接口前言据上一篇，设计方案的分析，综合考虑，最终决定,客户端采用agent方案实现，具本原因不再赘述， 感觉兴趣的小伙伴可以回头了解一下.该篇主…...

编程日记 2025/7/23 11:29:28

网络安全专业术语

网络安全专有名词详解 1.肉鸡被黑客操控的终端设备（电脑、服务器、移动设备等等），黑客可以随心所欲的操作这些终端设备而不会被发觉。 2.木马表面上伪装成正常的程序，但是当这些程序运行时候就会获取整个系统的控制权限&#…...

编程日记 2025/7/21 18:11:41

SpringMVC核心、两种视图解析方法、过滤器拦截器 “ / “ 的意义

SpringMVC的执行流程 1. Spring MVC 的视图解析机制 Spring MVC 的核心职责之一是将数据绑定到视图并呈现给用户。它通过视图解析器（View Resolver） 来将逻辑视图名称解析为具体的视图文件（如 HTML、JSP）。核心流程 Controlle…...

编程日记 2025/7/21 18:20:06

ubuntu快速入门

1.进入某个文件夹 cd workspace/2.tab自动补全 3.列出当前文件夹所有文件 ls列出所有文件包括隐藏文件 ls -a 4.创建文件夹 mkdir linuxLearn 5.创建文件 gedit command.sh在commmand.sh键入 echo hello echo hi? echo how are you? PS:touch hello.txt(也可以创建新…...

编程日记 2025/7/20 7:51:22

HarmonyOS NEXT应用开发实战：一分钟写一个网络接口，JsonFormat插件推荐

在开发鸿蒙操作系统应用时，网络接口的实现往往是一个繁琐且重复的过程。为了提高开发效率，坚果派(nutpi.net)特别推出了一个非常实用的插件——JsonFormat。这款插件的主要功能是将JSON格式的数据直接转换为arkts的结构定义，让我们在编写接口…...

编程日记 2025/7/25 1:27:51

光谱相机与普通相机的区别

一、成像目的普通相机：主要目的是记录物体的外观形态，生成人眼可见的、直观的二维图像，重点在于还原物体的形状、颜色和纹理等视觉特征，以供人们进行观赏、记录场景或人物等用途。例如，拍摄旅游风景照片、人物肖像等…...

编程日记 2025/7/22 19:30:08

贝叶斯神经网络（Bayesian Neural Network）

最近在研究贝叶斯神经网络，一些概念一直搞不清楚，这里整理一下相关内容，方便以后查阅。贝叶斯神经网络（Bayesian Neural Network）贝叶斯神经网络（Bayesian Neural Network）1. BNN 的核心思想2. BNN 的优化目标3. BNN 的结构与特点4. BNN 的训练过程5. BNN 的优缺点6. …...

编程日记 2025/7/20 15:38:21

使用FFmpeg进行拉流和推流操作

FFmpeg是一款强大的多媒体处理工具，可以用于视频的录制、转换、推流和拉流等操作。下面将详细介绍如何使用FFmpeg进行拉流和推流操作。 1. FFmpeg推流操作推流是将本地的音视频流推送到流媒体服务器上，例如主播将本地电脑上的画面推流到直播平台的流媒…...

编程日记 2025/7/23 11:14:09

题目描述

解题思路

代码实现

代码解析

复杂度分析

总结

相关文章：