Leetcode 3569. Maximize Count of Distinct Primes After Split
- Leetcode 3569. Maximize Count of Distinct Primes After Split
- 1. 解题思路
- 2. 代码实现
- 题目链接:3569. Maximize Count of Distinct Primes After Split
1. 解题思路
这一题的话思路倒是还好,显然,要找出所有distinct的质数的切分,我们首先就是先将 10 5 10^5 105以内的所有质数找出来,这样,我们就能够快速的找出原始的数组当中的所有的质数的位置了。
然后,我们考察最优的切分方式,注意到:
- 所有仅出现一次的质数,无论怎么切分,其贡献值都为一;
- 对于出现过多次的质数,考察其第一次出现的位置与最后一次出现的位置,我们只要在其中间任意位置切一刀,则其贡献值就会由1变成2。
因此,这道题事实上也就变成了,给定若干个区域 [ l i , r i ] [l_i, r_i] [li,ri],找出一个位置 p p p,使之同时存在的区域最多。这个的话我们只需要依次将所有的 [ l i , r i ] [l_i, r_i] [li,ri]上的元素加一,然后考察线段当中的最大值即可。
但是,我们需要频繁地对对元素进行修改以及query,因此我们需要不断地修改整段区间 [ l k , r k ] [l_k, r_k] [lk,rk]上的值,然后再去进行query,这个就是一个标准的Lazy Segment Tree的题目了,虽然我还是不能熟练地写出对应的代码,不过相关的内容网上多的是,deepseek也能很快速地给出对应的代码实现,所以这里就不过多赘述了。
事实上,对应的Lazy Segment Tree的算法实现,我也是直接让deepseek帮我写作完成的……
2. 代码实现
给出python代码实现如下:
def get_primes(n):status = [0 for _ in range(n+1)]primes = set()for i in range(2, n+1):if status[i] != 0:continueprimes.add(i)for j in range(i, n+1, i):status[j] = 1return primesPRIMES = get_primes(10**5)class LazySegmentTree:def __init__(self, arr):"""根据数组 arr 构建惰性线段树:param arr: 输入数组"""self.n = len(arr)self.arr = arr# 初始化线段树和惰性标记数组(4倍原始数组大小)self.size = 4 * self.nself.tree = [-float('inf')] * self.size # 存储区间最大值self.lazy = [0] * self.size # 存储惰性标记self._build(0, 0, self.n - 1) # 从根节点开始建树def _build(self, node, start, end):"""递归构建线段树:param node: 当前节点索引:param start: 当前节点表示的区间起始索引:param end: 当前节点表示的区间结束索引"""if start == end:# 叶子节点,直接存储数组值self.tree[node] = self.arr[start]returnmid = (start + end) // 2left_node = 2 * node + 1 # 左子节点索引right_node = 2 * node + 2 # 右子节点索引# 递归构建左右子树self._build(left_node, start, mid)self._build(right_node, mid + 1, end)# 当前节点值为左右子树的最大值self.tree[node] = max(self.tree[left_node], self.tree[right_node])def _push_down(self, node, start, end):"""下推惰性标记到子节点:param node: 当前节点索引:param start: 当前节点表示的区间起始索引:param end: 当前节点表示的区间结束索引"""if self.lazy[node] != 0:# 更新当前节点的值self.tree[node] += self.lazy[node]if start != end: # 非叶子节点,标记下推left_node = 2 * node + 1right_node = 2 * node + 2# 将惰性标记添加到子节点self.lazy[left_node] += self.lazy[node]self.lazy[right_node] += self.lazy[node]# 清除当前节点的惰性标记self.lazy[node] = 0def update(self, l, r, val):"""将闭区间 [l, r] 内的所有元素增加 val:param l: 区间左边界:param r: 区间右边界:param val: 要增加的值"""self._update(0, 0, self.n - 1, l, r, val)def _update(self, node, start, end, l, r, val):"""递归执行区间更新:param node: 当前节点索引:param start: 当前节点表示的区间起始索引:param end: 当前节点表示的区间结束索引:param l: 更新区间左边界:param r: 更新区间右边界:param val: 要增加的值"""# 先下推当前节点的惰性标记self._push_down(node, start, end)# 当前节点区间与更新区间无交集if start > r or end < l:return# 当前节点区间完全包含在更新区间内if l <= start and end <= r:# 更新当前节点值self.tree[node] += valif start != end: # 非叶子节点,更新子节点惰性标记left_node = 2 * node + 1right_node = 2 * node + 2self.lazy[left_node] += valself.lazy[right_node] += valreturn# 部分重叠,递归更新子区间mid = (start + end) // 2left_node = 2 * node + 1right_node = 2 * node + 2self._update(left_node, start, mid, l, r, val)self._update(right_node, mid + 1, end, l, r, val)# 更新当前节点值为左右子树的最大值self.tree[node] = max(self.tree[left_node], self.tree[right_node])def query(self, l, r):"""查询闭区间 [l, r] 内的最大元素值:param l: 查询区间左边界:param r: 查询区间右边界:return: 区间内的最大值"""return self._query(0, 0, self.n - 1, l, r)def _query(self, node, start, end, l, r):"""递归执行区间查询:param node: 当前节点索引:param start: 当前节点表示的区间起始索引:param end: 当前节点表示的区间结束索引:param l: 查询区间左边界:param r: 查询区间右边界:return: 区间内的最大值"""# 先下推当前节点的惰性标记self._push_down(node, start, end)# 当前节点区间与查询区间无交集if start > r or end < l:return -float('inf')# 当前节点区间完全包含在查询区间内if l <= start and end <= r:return self.tree[node]# 部分重叠,递归查询子区间mid = (start + end) // 2left_node = 2 * node + 1right_node = 2 * node + 2left_max = self._query(left_node, start, mid, l, r)right_max = self._query(right_node, mid + 1, end, l, r)return max(left_max, right_max)class Solution:def maximumCount(self, nums: List[int], queries: List[List[int]]) -> List[int]:primes_locs = defaultdict(list)for i, x in enumerate(nums):if x in PRIMES:primes_locs[x].append(i)n = len(nums)segment_tree = LazySegmentTree([0 for _ in range(n)])for p, locs in primes_locs.items():if len(locs) > 1:segment_tree.update(locs[0], locs[-1], 1)def query(idx, val):nonlocal primes_locs, segment_tree, numsold_val = nums[idx]nums[idx] = valif old_val == val:return len(primes_locs) + segment_tree.query(0, n-1)if old_val in PRIMES:l, r = primes_locs[old_val][0], primes_locs[old_val][-1]primes_locs[old_val].pop(bisect.bisect_left(primes_locs[old_val], idx))if l == r:primes_locs.pop(old_val)passelif len(primes_locs[old_val]) == 1:segment_tree.update(l, r, -1)elif l == idx:new_l = primes_locs[old_val][0]segment_tree.update(idx, new_l-1, -1)elif r == idx:new_r = primes_locs[old_val][-1]segment_tree.update(new_r+1, idx, -1)if val in PRIMES:if val not in primes_locs:primes_locs[val] = [idx]else:l, r = primes_locs[val][0], primes_locs[val][-1]bisect.insort(primes_locs[val], idx)if len(primes_locs[val]) == 2:l, r = primes_locs[val][0], primes_locs[val][-1]segment_tree.update(l, r, 1)elif idx < l:segment_tree.update(idx, l-1, 1)elif idx > r:segment_tree.update(r+1, idx, 1)return len(primes_locs) + segment_tree.query(0, n-1)return [query(idx, val) for idx, val in queries]
提交代码评测得到:耗时7026ms,占用内存46.94MB。
相关文章:
Leetcode 3569. Maximize Count of Distinct Primes After Split
Leetcode 3569. Maximize Count of Distinct Primes After Split 1. 解题思路2. 代码实现 题目链接:3569. Maximize Count of Distinct Primes After Split 1. 解题思路 这一题的话思路倒是还好,显然,要找出所有distinct的质数的切分&…...

用好 ImageFX,解锁游戏素材生成新姿势:从入门到进阶
用好 ImageFX,解锁游戏素材生成新姿势:从入门到进阶 (备注)大陆ip无法访问到imagefx 地址:https://labs.google/fx/zh/tools/image-fx 对于独立游戏开发者和小型团队而言,美术资源往往是项目推进中的一大痛点。预算有限、专业美术人员缺乏…...
unix/linux,sudo,其基本属性、语法、操作、api
现在我们要深入到sudo的“微观结构”了——它的属性、语法、操作以及是否有传统意义上的“API”。这就像我们从宏观的宇宙现象深入到基本粒子的相互作用一样,充满了探索的乐趣! 一、 sudo 的基本属性 (Fundamental Attributes) 这些属性是sudo作为一款软件和系统工具的核心…...
文本内容变化引起布局尺寸变化 导致的 UI 适配问题
在使用 Flutter 开发应用时,配合 easy_localization 实现多语言切换是一个非常常见的做法。但正如你所说,在不同语言下文字长度差异较大(如英文和中文、阿拉伯语等)会导致界面布局错位、UI 不美观的问题。 这个问题本质上是 文本…...

01-Redis介绍与安装
01-Redis介绍与安装 SQL与NoSQL SQLNoSQL数据结构结构化非结构化数据关联关联的非关联的查询方式SQL查询非SQL事务特性ACIDBASE存储方式磁盘内存拓展性垂直水平使用场景1、数据结构固定2、相关业务对数据安全性、一致性要求较高1、数据结构不固定2、对安全性、一致性要求不高…...
十六、【前端强化篇】完善 TestCase 编辑器:支持 API 结构化定义与断言配置
【前端强化篇】完善 TestCase 编辑器:支持 API 结构化定义与断言配置 前言准备工作第一步:更新前端 `TestCase` 类型定义第二步:改造 `TestCaseEditView.vue` 表单第三步:修改后端代码中的TestCase模型和序列化器第四步:测试强化后的用例编辑器总结前言 在之前的后端文章…...
Kafka broker 写消息的过程
Producer → Kafka Broker → Replication → Consumer|Partition chosen (by key or round-robin)|Message appended to end of log (commit log)上面的流程是kafka 写操作的大体流程。 kafka 不会特意保留message 在内存中,而是直接写入了disk。 那么消费的时候&…...

VR博物馆推动现代数字化科技博物馆
VR博物馆:推动现代数字化科博馆新篇章 随着科技的飞速发展,虚拟现实(Virtual Reality, VR)技术已经逐渐渗透到我们生活的方方面面,其中,VR博物馆作为现代数字化科博馆的重要形式之一,以独特的优…...

Python爬虫之数据提取
本章节主要会去学习在爬虫中的如何去解析数据的方法,要学习的内容有: 响应数据的分类结构化数据如何提取非结构化数据如何提取正则表达式的语法以及使用jsonpath解析嵌套层次比较复杂的json数据XPath语法在Python代码中借助lxml模块使用XPath语法提取非…...

第2讲、Odoo深度介绍:开源ERP的领先者
一、Odoo深度介绍:开源ERP的领先者 Odoo,其前身为OpenERP,是一款在全球范围内广受欢迎的开源企业管理软件套件。它不仅仅是一个ERP系统,更是一个集成了客户关系管理(CRM)、电子商务、网站构建、项目管理、…...

【TCP/IP和OSI模型以及区别——理论汇总】
参考小林code和卡尔哥,感恩! 网络基础篇 面试官您好!OSI和TCP/IP是网络通信中两个关键模型,本质都是分层处理数据传输,但设计理念和应用场景差异很大。 OSI模型是理论上的七层架构,从下到上依次是物理层…...
【HarmonyOS 5】生活与服务开发实践详解以及服务卡片案例
一、金融场景创新实践 智慧银行网点转型 通过统一设备方案整合国产芯片与鸿蒙系统,支持智能柜员机、移动展业终端等设备的弹性硬件组合,降低25%硬件成本。利用元服务框架实现卡片式交互(如客户画像、风险评估一键调取)&a…...
LEAP模型能源需求/供应预测、能源平衡表核算、空气污染物排放预测、碳排放建模预测、成本效益分析、电力系统优化
🌐 LEAP模型(Long-range Energy Alternatives Planning System),即长期能源替代规划系统,是由斯德哥尔摩环境研究所与美国波士顿大学共同开发的基于情景分析的自底向上的能源—环境核算工具。该模型采用自底向上的架构…...

STM32 I2C通信外设
1、外设简介 可变多主机 7位/10位寻址 10位寻址:起始之后的两个字节都作为寻址,第一个字节前5位是11110作为10位寻址的标志位 SMBus:系统管理总线,主要用于电源管理,与I2C类似 2、外设结构框图 比较器、自身地址寄…...

13. springCloud AlibabaSeata处理分布式事务
目录 一、分布式事务面试题 1.多个数据库之间如何处理分布式事务? 2.若拿出如下场景,阁下将如何应对? 3.阿里巴巴的Seata-AT模式如何做到对业务的无侵入? 4.对于分布式事务问题,你知道的解决方案有哪些?请你谈谈? 二、分布式事务问题…...

MySQL 表的内连和外连
一、内连接 内连接实际上就是利用 where 子句对两种表形成的笛卡儿积进行筛选,前面学习的查询都是内连接,也是在开发过程中使用的最多的连接查询。 select 字段 from 表1 inner join 表2 on 连接条件 and 其他条件; 注意:前面学习的都是内连…...

VR线上展厅特点分析与优势
VR线上展厅:特点、优势与实际应用 VR线上展厅,作为虚拟现实(VR)技术在展示行业的创新应用,正逐步改变着传统的展览方式。通过模拟真实的物理环境,为参观者提供身临其境的展览体验,成为展示行业…...

Python基于SVM技术的手写数字识别问题项目实战
说明:这是一个机器学习实战项目(附带数据代码文档),如需数据代码文档可以直接到文章最后关注获取。 1.项目背景 在当今数字化转型加速的时代,手写数字识别作为图像处理与机器学习领域的一个经典问题,具有广…...
Elasticsearch的写入性能优化
优化Elasticsearch的写入性能需要从多维度入手,包括集群配置、索引设计、数据处理流程和硬件资源等。以下是一些关键优化策略和最佳实践: 一、索引配置优化 合理设置分片数与副本数分片数(Shards):过少会导致写入瓶颈(无法并行),过多会增加集群管理开销。公式参考:分…...

2024年数维杯国际大学生数学建模挑战赛A题飞行器激光测速中的频率估计问题解题全过程论文及程序
2024年数维杯国际大学生数学建模挑战赛 A题 复合直升机的建模与优化控制问题 原题再现: (一) 问题的背景 空速,即飞机相对于空气的速度,是飞行期间需要监控的关键参数。空速与飞行状态密切相关,如迎角…...
AWS 成本异常检测IAM策略
问题 审计人员需要看AWS 成本异常检测,则需要开通这个权限。 IAM 自定义策略 {"Version": "2012-10-17","Statement": [{"Action": ["ce:Get*"],"Effect": "Allow","Resource"…...
解决Vue3+uni-app导航栏高亮自动同步方案
路由跳转自动识别导航高亮实现方法 以下代码使用wd-tabbar组件实现路由跳转时自动同步导航栏高亮状态,适用于所有的Vue3uni-app项目。 请根据自身使用框架类型完成,也可根据我使用的UI组件进行完成地址如下: Tabbar 标签栏 | Wot UI &#…...

DeepSeek+SpringAI实现流式对话
大模型的响应速度通常是很慢的,为了避免用户用户能够耐心等待输出的结果,我们通常会使用流式输出一点点将结果输出给用户。 那么问题来了,想要实现流式结果输出,后端和前端要如何配合?后端要使用什么技术实现流式输出呢…...

【Spark征服之路-2.1-安装部署Spark(一)】
实验目标: 本节课实验将完成Spark 4种部署模式的其中2种,分别是Local、Standalone模式。 实验准备工作: 三台linux虚拟机spark的压缩包 实验步骤: Spark-local Spark的Local模式仅需要单个虚拟机节点即可,无需启…...

VS代码生成工具ReSharper v2025.1——支持.NET 10和C# 14预览功能
实质上,ReSharper特征可用于C#,VB.net,XML,Asp.net,XAML和构建脚本。 使用ReSharper,你可以进行深度代码分析,智能代码协助,实时错误代码高亮显示,解决方案范围内代码分析…...

【Godot】如何导出 Release 版本的安卓项目
在使用 Godot 引擎开发安卓游戏或应用时,发布到应用市场(如 Google Play、华为应用市场等)通常需要生成一个 Release 版本的 .apk 包,而非 Debug 版本。本文将详细介绍如何将 Godot 项目导出为 Release 版本的安卓项目,…...

VSCode 工作区配置文件通用模板(CMake + Ninja + MinGW/GCC 编译器 的 C++ 或 Qt 项目)
下面是一个通用模板,适用于大多数使用 VSCode CMake Ninja MinGW/GCC 编译器 的 C 或 Qt 项目。你可以将这个 .vscode 文件夹复制到你的项目根目录下,稍作路径调整即可使用。 📁 .vscode/ 目录结构(通用模板) .vs…...
js鼠标事件大全
一、鼠标相关事件(Mouse Events) 事件名描述支持浏览器(HTML 版本)onClick鼠标单击对象时触发IE3, N2, O3onDblClick鼠标双击对象时触发IE4, N4, OonMouseDown鼠标按键按下时触发IE4, N4, OonMouseUp鼠标按键释放时触发IE4, N4, …...

Java八股文——Redis篇
目录 1. 缓存穿透解决方案1. 缓存空值2. 布隆过滤器(Bloom Filter)3. 参数校验4. 接口限流与验证码 2. 缓存击穿解决方案1. 设置热点数据永不过期(或很长过期时间)2. 使用互斥锁(如分布式锁)3. 利用异步更新…...

爬虫接口类型判断与表单需求识别全解析
爬虫接口类型判断与表单需求识别全解析 在爬虫开发中,准确判断目标接口的类型以及是否需要表单提交,是实现高效、稳定爬取的关键一步。本文将通过实际案例,详细介绍如何通过浏览器开发者工具和代码验证来判断接口类型及表单需求。 一、接口…...