第421场周赛:数组的最大因子得分、
Q1、数组的最大因子得分
1、题目描述
给你一个整数数组 nums
。
因子得分 定义为数组所有元素的最小公倍数(LCM)与最大公约数(GCD)的 乘积。
在 最多 移除一个元素的情况下,返回 nums
的 最大因子得分。
注意,单个数字的 LCM
和 GCD
都是其本身,而 空数组 的因子得分为 0。
2、解题思路
为了解决这个问题,我们将使用 前缀和后缀数组 的方法,动态计算移除每个元素后的因子得分。
-
数学性质
-
单个数字的 GCD 和 LCM:
- 对于单个数字
x
,其GCD
和LCM
都是x
,因此因子得分为 x × x = x 2 x \times x = x^2 x×x=x2。
- 对于单个数字
-
空数组的 GCD 和 LCM:
- 空数组的 GCD 和 LCM 均为 0,因此因子得分为 0。
-
GCD 和 LCM 的计算公式:
-
最大公约数(GCD):
gcd(a, b)
。 -
最小公倍数(LCM):
lcm(a, b) = a / gcd(a, b) * b
。
-
-
-
前缀和后缀数组
为了高效地计算移除每个元素后的 GCD 和 LCM,我们使用前缀和后缀数组:
- 后缀数组:
sufGCD[i]
表示从索引i
到数组末尾所有元素的 GCD。sufLCM[i]
表示从索引i
到数组末尾所有元素的 LCM。
- 前缀变量:
preGCD
表示从数组开头到当前索引的 GCD。preLCM
表示从数组开头到当前索引的 LCM。
利用前缀和后缀信息,我们可以在 O(1) 的时间内计算移除某个元素后的剩余数组的 GCD 和 LCM。
- 后缀数组:
-
动态更新因子得分
-
对于每个索引 i:
-
计算移除元素
nums[i]
后,剩余数组的 GCD 和 LCM: $\text{remainingGCD} = \text{gcd(preGCD, sufGCD[i + 1])} $
remainingLCM = lcm(preLCM, sufLCM[i + 1]) \text{remainingLCM} = \text{lcm(preLCM, sufLCM[i + 1])} remainingLCM=lcm(preLCM, sufLCM[i + 1])
-
更新最大因子得分:
maxFactorScore = max ( maxFactorScore , remainingGCD × remainingLCM ) \text{maxFactorScore} = \max(\text{maxFactorScore}, \text{remainingGCD} \times \text{remainingLCM}) maxFactorScore=max(maxFactorScore,remainingGCD×remainingLCM)
-
更新前缀 GCD 和前缀 LCM。
-
3、代码实现
class Solution {
public:long long maxScore(vector<int>& nums) {int n = nums.size();// 后缀数组:// sufGCD[i] 表示从索引 i 到末尾所有元素的 GCD// sufLCM[i] 表示从索引 i 到末尾所有元素的 LCMvector<int> sufGCD(n + 1, 0); // 初始化为 0, 表示 GCDvector<long long> sufLCM(n + 1, 1); // 初始化为 1, 表示 LCM// 计算后缀 GCD 和后缀 LCMfor (int i = n - 1; i >= 0; i--) {sufGCD[i] = gcd(sufGCD[i + 1], nums[i]);sufLCM[i] = lcm(sufLCM[i + 1], nums[i]);}// 初始答案: 不移除任何元素时的因子得分long long maxFactorScore = static_cast<long long>(sufGCD[0]) * sufLCM[0];// 前缀变量: preGCD 和 preLCMint preGCD = 0; // 前缀 GCD, 初始为 0long long preLCM = 1; // 前缀 LCM, 初始为 1// 枚举每个元素作为移除目标for (int i = 0; i < n; i++) {// 移除 nums[i] 后, 剩余部分的 GCD 和 LCMint remainingGCD = gcd(preGCD, sufGCD[i + 1]);long long remainingLCM = lcm(preLCM, sufLCM[i + 1]);// 更新最大因子得分maxFactorScore = max(maxFactorScore, static_cast<long long>(remainingGCD) * remainingLCM);// 更新前缀 GCD 和前缀 LCMpreGCD = gcd(preGCD, nums[i]);preLCM = lcm(preLCM, nums[i]);}return maxFactorScore;}
};
4、复杂度分析
-
时间复杂度:
-
后缀数组计算需要 O(n)。
-
遍历每个元素更新前缀和计算剩余数组的 GCD 和 LCM,也需要 O(n)。
-
总体复杂度为 O(n)。
-
-
空间复杂度:
- 使用了
sufGCD
和sufLCM
两个数组,空间复杂度为 O(n)。
- 使用了
相关文章:
第421场周赛:数组的最大因子得分、
Q1、数组的最大因子得分 1、题目描述 给你一个整数数组 nums。 因子得分 定义为数组所有元素的最小公倍数(LCM)与最大公约数(GCD)的 乘积。 在 最多 移除一个元素的情况下,返回 nums 的 最大因子得分。 注意&…...
COMSOL 与人工智能融合的多物理场应用:28个案例的思路、方法与工具概述
应用案例概述 基于 COMSOL 与人工智能(AI)结合的应用案例涵盖了 28 个多领域场景,包括工程(如热传导优化、结构力学预测)、能源(如电池热管理、燃料电池性能)、生物医学(如药物传递…...
【算法】插入排序
算法系列五:插入排序 一、直接插入排序 1.原理 2.实现 3.性质 3.1时间复杂度 3.2空间复杂度 3.3稳定性 二、希尔排序 1.原理 1.1优化方向 1.2优化原理 2.设计 2.1比较无序时 2.2比较有序时 3.实现 4.性质 4.1时间复杂度 4.2空间复杂度 4.3稳定性…...
企业展示型网站模板HTML5网站模板下载指南
在当今数字化浪潮中,企业网站已成为企业展示形象、推广产品和服务的重要窗口。一个设计精美、功能完善的企业展示型网站,不仅能提升企业的品牌形象,还能吸引潜在客户,促进业务增长。而HTML5网站模板,凭借其跨平台兼容性…...
C盘清理——快速处理
C盘清理 | 快速处理 软件:小番茄C盘清理 https://ccleancdn.xkbrowser.com/cleanmaster/FanQieClean_13054_st.exe 前言:为什么需要专业的C盘清理工具? 作为一位长期与Windows系统打交道的技术博主,我深知C盘空间不足带来的痛苦…...
什么是模型驱动开发MDD?有哪些应用场景?
模型驱动开发(Model-Driven Development,MDD)是一种以模型为核心的软件开发方法,其核心思想是通过创建高层次的抽象模型来描述系统的结构和行为,而非直接编写代码。这些模型经过自动化工具的转换或生成,最终…...
uniapp小程序生成海报/图片并保存分享
调研结果: 方法一:canvasuni.canvasToTempFilePath耗时太长,现在卡在canvas的绘制有问题,canvas绘制的部分东西不生效但是找不到原因 方法二:使用wxml-to-canvas其实也差不多是用canvas手动绘制,可能会卡在…...
从IoT到AIoT:智能边界的拓展与AI未来趋势预测
文章目录 引言:从连接万物到感知万物1. AIoT的本质:将智能嵌入万物2. AIoT的推动力量与挑战2.1 推动力量2.2 关键挑战 3. 五大AIoT未来趋势预测趋势一:边缘智能将成为主流架构趋势二:AI模型将向自适应与多任务演进趋势三ÿ…...
2012年-全国大学生数学建模竞赛(CUMCM)试题速浏、分类及浅析
2012年-全国大学生数学建模竞赛(CUMCM)试题速浏、分类及浅析 全国大学生数学建模竞赛(China Undergraduate Mathematical Contest in Modeling)是国家教委高教司和中国工业与应用数学学会共同主办的面向全国大学生的群众性科技活动,目的在于激励学生学习数学的积极性,提高学…...
2140 星期计算
2140 星期计算 ⭐️难度:中等 🌟考点:2022、思维、省赛 📖 📚 1️⃣法一: 同余定理, import java.util.Scanner;public class Main2 {public static void main(String[] args) {Scanner sc …...
NVIDIA Jetson 环境安装指导 PyTorch | Conda | cudnn | docker
本文适用于Jetson Nano、TX1/TX2、Xavier 和 Orin系列的设备,供大家参考。 1、PyTorch不同版本安装 这里适用于Jetson Nano、TX1/TX2、Xavier 和 Orin ,需要JetPack 4.2以上。 下载地址:PyTorch for Jetson - Jetson & Embedded System…...
理解 Rust 中的 String 分配机制
在 Rust 中,哪怕是一行再普通不过的代码,也可能暗藏玄机。这次我们就来剖析这样一句看似简单的代码: let s "hello world".to_string();这行代码触发了 只读数据段(.rodata)、堆(heap࿰…...
园区网拓扑练习
1.拓扑图要求 1.按照图示的VLAN及IP地址需求,完成相关配需 2、要求SW1为VLAN 2/3的主根及主网关,SW2为vlan 20/30的主根及主网关,SW1和SW2互为备份 3.上层通过静态路由协议完成数据通信过程 4.AR1为企业出口路由器 5.要求全网可达 2.需求分…...
CentralCache
目录 一、Span和Spanlist 二、CentralCache 一、Span和Spanlist CentralCache其实也是哈希桶结构,只不过他是一个个的Span(Span是管理一定数量的页的结构),而且Span会管理一个freelist,用来挂起一个个的小内存块给Th…...
STM32 基础1
什么是GPIO的上拉和下拉电阻 下拉电阻:把一个不确定的信号通过电阳连接到地,其实就是初始化为低电平。 上拉电阻:把一个不确定的信号通过电连接到高电平,其实就是初始化为高电平。 本质:上拉地注入电流,下…...
Python爬虫第5节-urllib的异常处理、链接解析及 Robots 协议分析
目录 一、处理异常 1.1 URLError 1.2 HTTPError 二、解析链接 2.1 urlparse() 2.2 urlunparse() 2.3 urlsplit() 2.4 urlunsplit() 2.5 urljoin() 2.6 urlencode() 2.7 parse_qs() 2.8 parse_qsl() 2.9 quote() 2.10 unquote() 三、分析网站Robots协议 3.1 R…...
STM32——DAC转换
DAC简介 DAC,全称:Digital-to-Analog Converter,扑指数字/模拟转换器 ADC和DAC是模拟电路与数字电路之间的桥梁 DAC的特性参数 1.分辨率: 表示模拟电压的最小增量,常用二进制位数表示,比如:…...
因果推断【Causal Inference】(一)
文章目录 1. 什么是因果推断?2. 为什么要提出因果推断?Motivation:辛普森悖论Scenario 1Scenario 2 3. 【Note】相关性≠因果3.1 混淆(Confounding)——共同原因3.2 样本选择偏差(Selection Bias)——共同结果 4. 潜在结果(Potential Outcome…...
人工智能通识速览(Part5. 大语言模型)
五、大语言模型 1.NLP 自然语言处理(Natural Language Processing, NLP)是人工智能领域的一个重要分支,专注于研究 计算机如何理解、生成和处理人类语言。它的目标是让机器能够像人类一样“读懂”文本或语音,并执 行翻译、问答、摘…...
优化 Django 数据库查询
优化 Django 数据库查询 推荐超级课程: 本地离线DeepSeek AI方案部署实战教程【完全版】Docker快速入门到精通Kubernetes入门到大师通关课AWS云服务快速入门实战目录 优化 Django 数据库查询**理解 N+1 查询问题****`select_related`:外键的急加载**示例何时使用 `select_re…...
MCP AI:下一代智能微服务控制平台 (.NET Core)
平台概述 MCP AI (Microservice Control Platform AI) 是基于.NET Core构建的下一代智能微服务控制平台,旨在为企业级微服务架构提供智能化、自动化的管理和控制能力。 核心特性 智能服务编排 AI驱动的动态服务路由 自适应负载均衡算法 预测性扩展与收缩 统一…...
计算机网络基础:系列教程汇总
计算机网络基础:系列教程汇总 一、前言二、计算机网络基础概要三、计算机网络基础3.1 计算机网络基础:揭开网络世界的神秘面纱3.2 计算机网络基础:剖析网络的构成要素3.3 计算机网络基础:认识网络拓扑结构3.4 计算机网络基础:解析网络协议3.5 计算机网络基础:了解网络类型…...
互联网三高-高性能之JVM调优
1 运行时数据区 JVM运行时数据区是Java虚拟机管理的内存核心模块,主要分为线程共享和线程私有两部分。 (1)线程私有 ① 程序计数器:存储当前线程执行字节码指令的地址,用于分支、循环、异常处理等流程控制 ② 虚拟机…...
学习比较JVM篇(六):解读GC日志
一、前言 在之前的文章中,我们对JVM的结构、垃圾回收算法、垃圾回收器做了一些列的讲解,同时也使用了JVM自带的命令行工具进行了实际操作。今天我们继续讲解JVM。 我们学习JVM的目的是为了了解JVM,然后优化对应的参数。那么如何了解JVM运行…...
说说你对python的理解,有什么特性?
Python是一种高级、解释型、通用的编程语言,由Guido van Rossum于1991年首次发布。经过30多年的发展,Python已成为最受欢迎的编程语言之一,在Web开发、数据分析、人工智能、自动化运维等多个领域都有广泛应用。 Python的核心特性 1. 简洁优…...
【C语言】编译和链接
一、编译环境和运行环境 在ANSI C的任何一种实现中,存在着两个不同的环境: 1、翻译环境:在翻译环境中,其会通过编译和链接两个大的步骤,其中编译又分为了预处理(这 个我们后面还会详细讲解&#x…...
Spark,IDEA编写Maven项目
IDEA中编写Maven项目 1.打开IDEA新建项目 2.选择java语言,构建系统选择Maven 3.IDEA中配置Maven 注:这些文件都是我们老师帮我们在网上找了改动后给我们的,大家可自行在网上查找 编写代码测试HDFS连接 1.在之前创建的pom.xml文件中添加下列…...
【HFP】蓝牙HFP服务层连接与互操作性核心技术研究
目录 一、互操作性设计哲学 二、服务级别连接(SLC)架构设计 2.1 连接建立流程总览 2.2 核心交互时序图 2.3 关键阶段技术实现 2.4 RFCOMM连接:通信的基石 2.5 特征交换与编解码协商 2.6 指示器状态同步 三、状态同步机制深度优化 3…...
VSCode使用Remote-SSH连接服务器时启动失败glibc不符合
问题 远程主机可能不符合glibc和libstdc VS Code服务器的先决条件 原因 VSCode更新后,如果服务端GLIBC低于v2.28.0版本将不再满足需求 查看服务端GLIBC版本: ~$ ldd --version ldd (Ubuntu GLIBC 2.23-0ubuntu11.3) 2.23解决 下载V1.85版本 下载链…...
InceptionNeXt:When Inception Meets ConvNeXt论文翻译
论文名称:InceptionNeXt:WhenInceptionMeetsConvNeXt 论文地址:https://arxiv.org/pdf/2303.16900.pdf 摘要: 受视觉Transformer(ViTs)长距离建模能力的启发,大核卷积因能扩大感受野、提升模型性能而受到广泛研究与应用&#x…...
windows下,cursor连接MCP服务器
1.下载并安装node 安装后,在cmd命令框中,输入命令node -v可以打印版本号,证明安装完成 2.下载MCP服务器项目 在MCP服务器找到对应项目,这里以server-sequential-thinking为例子 在本地cmd命令窗口,使用下面命令下载…...
从零开始:使用 kubeadm 部署 Kubernetes 集群的详细指南
使用kubeadmin 部署k8s集群 目录 硬件要求 前期准备 Master 检查 API 服务器证书 清理并重新初始化 查 kubeadm 初始化日志 配置 crictl 的 endpoint 硬件要求 主机名 ip 硬件最低要求 建议,跑的块 master 10.1.1.7 2核,2G 内存给个6G node2 …...
rancher 采用ingerss ssl 部署nginx+php项目
rancher 采用ingerss ssl 部署nginxphp项目 一、创建nginx dockerfile,上传到阿里云镜像仓库(公有,不需要密码) 二、 创建php7.4 dockerfile,需要必须扩展, 上传到阿里云镜像仓库(公有&#x…...
开源聚合平台 Websoft9:开源创新已成为中小企业数字化转型、数据驱动企业的基础
引言:开源软件正在重塑企业数字化未来 根据2024年OpenLogic报告,94.57%的企业已使用开源软件,其中34.07%的机构加大了对开源技术的投入。开源软件凭借其灵活性、成本优势和生态协作能力,成为中小企业(SMB)数字化转型的…...
IntelliJ IDEA 中通义灵码插件使用指南
IntelliJ IDEA 中通义灵码插件使用指南 通义灵码(TONGYI Lingma)是阿里云推出的一款基于通义大模型的智能编码辅助工具,支持 IntelliJ IDEA 等主流 IDE。它提供了代码补全、自然语言生成代码、单元测试生成、代码注释与解释等功能࿰…...
如何免费使用Meta Llama 4?
周六, Meta发布了全新开源的Llama 4系列模型。 架构介绍查看上篇文章。 作为开源模型,Llama 4存在一个重大限制——庞大的体积。该系列最小的Llama 4 Scout模型就拥有1090亿参数,如此庞大的规模根本无法在本地系统运行。 不过别担心!即使你没有GPU,我们也找到了通过网页…...
introduceHLSL
最近打算好好学习一下ue的shader,跟着下面的视频,打算每天至少更新一集 https://www.youtube.com/watch?vlsXB1PQdGx0&t494s 通过下面的蓝图方式我们就可以得到一个变化的材质 alpha参数的生成实际上就是下面的式子 custom节点允许直接的写入hlsl…...
Module模块化
导出:export关键字 export var color "red"; 重命名导出 在模块中使用as用导出名称表示本地名称。 import { add } from "./05-module-out.js"; 导入: import关键字 导入单个绑定 import { sum } from "./05-module-out.js&…...
使用 Rsync + Lsyncd 实现 CentOS 7 实时文件同步
文章目录 🌀使用 Rsync Lsyncd 实现 CentOS 7 实时文件同步前言介绍架构图🧱系统环境🔧Rsync配置(两台都需安装)关闭SELinux(两台都需) 📦配置目标端(client)…...
软件工程第三章习题
一、选择题 1. (1)答案:D 解析:可行性研究是对项目在技术、经济、操作等多方面进行全面评估论证,也称为项目论证 。技术可行性研究、操作可行性研究、经济可行性研究只是可行性研究的部分内容,不能涵盖整体概念。 2. (2)答案&…...
基于ElasticSearch的向量检索技术实践
基于ElasticSearch的向量检索技术实践 作者:Tableau 原文地址:https://zhuanlan.zhihu.com/p/620260383 图片、视频、语音、文本等非结构化数据可以通过人工智能技术(深度学习算法)提取特征向量,然后通过对这些特征向量…...
Spring Boot 项目日志系统全攻略:Logback、Log4j2、Log4j与SLF4J整合指南
Spring Boot 项目日志系统全攻略:Logback、Log4j2、Log4j与SLF4J整合指南 日志系统是应用程序不可或缺的组成部分,良好的日志实践能极大提升开发调试和线上问题排查的效率。本文将全面介绍Spring Boot项目中各种日志框架的配置与使用方案,包…...
【设计模式】责任链模式
简介 很多公司都有请假的流程,当员工提交请假申请时,请求会沿着 组长 → 经理 → CEO 的链条传递,直到有对应层级的领导处理。 适用场景 一个请求需要多个对象中的一个或多个处理(如审批流程、过滤器链)。处理对象和…...
智能气候前沿:AI Agent结合机器学习与深度学习在全球气候变化驱动因素预测
全球气候变化已成为21世纪最严峻的环境挑战,其复杂的驱动因素如温室气体排放、气溶胶浓度、野火、海冰融化以及农业和生态系统变化等,交织影响着全球的气候格局。 第一:气候变化驱动因素与数据科学基础 1.1气候变化 全球气候变化 中国碳中…...
es 原生linux部署集群
背景 目的: 1. 理解不同部署方式的架构差异 2. 对比环境配置的复杂度 3. 评估性能与资源管理 4. 探索扩展性与高可用性 5. 学习安全与隔离机制 6. 实践监控与维护 7. 掌握混合部署与云原生场景 实验的最终目标 技能提升: 全面掌握Elasticsear…...
Springboot 同时支持不同的数据库,Oracle,Postgresql
## 关键字 Java,Springboot,Vscode,支持多种数据库 ## 背景环境 我在实际项目开发工程中遇到这样一个问题,用户 A 使用 Oracle 数据库,用户 B 使用 Postgresql 数据库,但是用户 AB 都使用我们的项目。所以…...
go --- go run main.go 和 go run .
目录 go run main.gogo run .示例 go run main.go 功能:只编译和运行指定的文件(main.go),忽略同目录下的其他文件。适用场景: 当你只需要运行一个独立的文件,且该文件不依赖其他文件时。适合单文件程序或…...
关于Spring MVC中@RequestMapping注解的详细解析,涵盖其核心功能、属性、使用场景及最佳实践
以下是关于Spring MVC中RequestMapping注解的详细解析,涵盖其核心功能、属性、使用场景及最佳实践: 1. 基础概念 RequestMapping是Spring MVC的核心注解,用于将HTTP请求映射到控制器(Controller)的方法上。它支持类级…...
deepseek使用记录26——从体力异化到脑力异化
我们的一切发现和进步,似乎结果是使物质力量具有理智生命,而人的生命则化为愚钝的物质力量。AI快速发展的现实中,人面临着比工业革命更深刻的异化。在工业革命中,人的身躯沦为了机器的一部分,而现在人的脑袋沦为了AI的…...
Ubertool 的详细介绍、安装指南及使用说明
Ubertool:多协议网络分析与调试平台 一、Ubertool 简介 Ubertool 是一款开源的 多协议网络分析工具,专为物联网(IoT)、嵌入式系统和工业自动化领域设计。它支持蓝牙、Wi-Fi、LoRa、CAN总线等多种通信协议的实时监控、数据包捕获…...