Kimi LeetCode 3953. 互质元素的最大得分 Java实现

发布时间：2026/8/18 20:27:21

Kimi LeetCode 3953. 互质元素的最大得分 Java实现
以下是 LeetCode 3953. 互质元素的最大得分 的完整 Java 实现javaimport java.util.*;class Solution {private static final int N 100001;// primeFactors[i] 存储 i 的所有不同质因数SuppressWarnings(unchecked)private static final ListInteger[] primeFactors new ArrayList[N];// 预处理每个数的不同质因数筛法static {for (int i 0; i N; i) {primeFactors[i] new ArrayList();}for (int i 2; i N; i) {if (primeFactors[i].isEmpty()) { // i 是质数for (int j i; j N; j i) {primeFactors[j].add(i);}}}}public int maxScore(int[] nums, int maxVal) {// cnt[d]原数组中能被 d 整除的数的个数d 是质因数子集的乘积int[] cnt new int[N];// present[x]x 在原数组中出现的次数int[] present new int[N];for (int x : nums) {if (x N) {present[x];}ListInteger pf primeFactors[x];int sz pf.size();// 枚举所有非空子集统计各乘积的倍数个数for (int mask 1; mask (1 sz); mask) {int prod 1;for (int i 0; i sz; i) {if ((mask i 1) 1) {prod * pf.get(i);}}if (prod N) {cnt[prod];}}}int res Integer.MIN_VALUE;// 1. 处理 selectedValue 1 的情况if (maxVal 1) {if (present[1] 0) {// 1 在原数组中无需修改且 1 与任何数互质res Math.max(res, 1);} else {// 需要把一个元素修改为 1代价为 1res Math.max(res, 0); // 1 - 1 0}}// 2. 枚举 selectedValue 从 2 到 maxValfor (int v 2; v maxVal; v) {int notCoprime getNotCoprimeCount(v, cnt);if (present[v] 0) {// v 在原数组中v 与自身不互质v 1需减去自身这一次int cost notCoprime - 1;res Math.max(res, v - cost);} else {// v 不在原数组中至少要花费 1 次修改来创建vint cost notCoprime 0 ? 1 : notCoprime;res Math.max(res, v - cost);}}// 3. 处理原数组中大于 maxVal 的元素作为 selectedValue不修改它boolean[] visited new boolean[N];for (int x : nums) {if (x maxVal || x N || visited[x]) continue;visited[x] true;if (x 1) continue; // 1 已处理int notCoprime getNotCoprimeCount(x, cnt);int cost notCoprime - 1; // x 与自身不互质减去自身res Math.max(res, x - cost);}return res;}// 使用容斥原理计算原数组中与 x 不互质的元素个数private int getNotCoprimeCount(int x, int[] cnt) {ListInteger pf primeFactors[x];int sz pf.size();int total 0;for (int mask 1; mask (1 sz); mask) {int prod 1;int bits 0;for (int i 0; i sz; i) {if ((mask i 1) 1) {prod * pf.get(i);bits;}}if (prod N) {// 容斥奇数个质因数相加偶数个质因数相减if ((bits 1) 1) {total cnt[prod];} else {total - cnt[prod];}}}return total;}}---核心思路步骤 说明质因数预处理 用筛法在 static 块中预处理 [1, 10^5] 每个数的不同质因数倍数统计 对数组中每个数枚举其质因数的所有非空子集统计各乘积的倍数个数到 cnt[]容斥原理 对候选值 v通过容斥计算数组中与 v 不互质的元素个数三种候选 分别枚举 selectedValue 为 1、 [2, maxVal] 中的值、以及原数组中大于 maxVal 且未修改的元素复杂度- 时间复杂度O(N × 2^ω)其中 ω 是数的不同质因数个数≤ 6因为 2×3×5×7×11×13 30030 10^5所以 2^ω ≤ 64- 空间复杂度O(N)

相关新闻

BaiduPCS-Web 下载提速实测：一份把网盘速度从 200KB/s 提到 8MB/s 的避坑手册

BaiduPCS-Web 下载提速实测：一份把网盘速度从 200KB/s 提到 8MB/s 的避坑手册

2026/8/18 20:27:21

BaiduPCS-Web 下载提速实测：一份把网盘速度从 200KB/s 提到 8MB/s 的避坑手册 【免费下载链接】baidupcs-web 项目地址: https://gitcode.com/gh_mirrors/ba/baidupcs-web 周五晚上十点，我急着取回一份 2.3GB 的设计素材包，官方客户端…

6G物理层智能体：意图感知与持续进化的无线通信新范式

6G物理层智能体：意图感知与持续进化的无线通信新范式

2026/8/18 20:27:21

1. 项目概述：从“连接”到“使能”的范式跃迁 “Agentic Wireless Communication for 6G: Intent-Aware and Continuously Evolving Physical-Layer Intelligence”，这个标题初看有些拗口，但它精准地指向了下一代无线通信技术演进的核心战场。…

Kimi LeetCode 3943. 递增后的数对数量 Python3实现

Kimi LeetCode 3943. 递增后的数对数量 Python3实现

2026/8/18 20:17:21

这是 LeetCode 3943 递增后的数对数量 的 Python3 实现。 解题思路 核心观察&#xff1a;nums1.length < 5&#xff08;极短&#xff09;&#xff0c;而 nums2 很长&#xff08;5 \times 10^4&#xff09;且需要支持区间加和单值频次查询。 对于类型 2 查询 [2, tot]&…

RAG系统构建实战：从文档切片到混合检索的工程化指南

RAG系统构建实战：从文档切片到混合检索的工程化指南

2026/8/18 22:17:26

如果你在2024年问一个开发者&#xff0c;大模型应用落地最靠谱的路径是什么&#xff1f;十有八九会告诉你&#xff1a;RAG。但如果你再追问&#xff0c;如何从零搭建一个真正可用、可扩展、能应对复杂业务场景的RAG系统&#xff1f;很多人可能就卡在了“文档切片怎么切”、“向…

基于OpenAI API构建智能对话记忆系统：从原理到实战

基于OpenAI API构建智能对话记忆系统：从原理到实战

2026/8/18 22:17:26

在 ChatGPT 的日常使用中&#xff0c;你是否曾有过这样的困扰&#xff1a;几天前和 AI 讨论过一个技术方案&#xff0c;当时它给出了一个非常精妙的代码片段&#xff0c;但现在却怎么也想不起具体的对话内容&#xff0c;只能在一页页的聊天记录里大海捞针&#xff1f;或者&…

Coze实战指南：从零构建AI智能体与自动化工作流

Coze实战指南：从零构建AI智能体与自动化工作流

2026/8/18 22:17:26

大家好&#xff0c;我是专注于AI应用开发实战的技术博主。最近在探索如何将大模型能力快速落地到实际业务场景时&#xff0c;Coze&#xff08;扣子&#xff09;这个一站式AI应用开发平台进入了我的视野。它极大地降低了构建智能体&#xff08;Agent&#xff09;和自动化工作流的…

CTF入门到精通：清华蓝莲花战队教程实战指南与学习路径规划

CTF入门到精通：清华蓝莲花战队教程实战指南与学习路径规划

2026/8/18 22:17:26

1. 先搞清楚这套教程能帮你解决什么问题如果你对CTF&#xff08;夺旗赛&#xff09;感兴趣&#xff0c;尤其是想系统性地从零开始学习&#xff0c;那么“清华大学蓝莲花战队内部培训教程”这个名头确实很有吸引力。蓝莲花战队是国内顶尖的CTF战队&#xff0c;他们的内部培训材料…

智能微服务治理，产品和研发怎样约定自动化边界

智能微服务治理，产品和研发怎样约定自动化边界

2026/8/18 22:17:26

智能微服务治理&#xff0c;产品和研发怎样约定自动化边界 当平台和业务团队对自动切流的预期不一致时&#xff0c;常见缺口是责任边界、触发条件和人工接管机制没有提前写清。这里以降级策略演练为例&#xff0c;说明这些信息应怎样落到配置和审计中。 平台侧关心调用链和集群…

别再给论文查重交智商税了！参考文献、改稿、答辩PPT一站式搞定

别再给论文查重交智商税了！参考文献、改稿、答辩PPT一站式搞定

2026/8/18 22:07:26

【文章复现】非线性值迭代自适应动态规划（ADP）：离散时间非线性系统的策略迭代自适应动态规划算法研究附Matlab代码

【文章复现】非线性值迭代自适应动态规划（ADP）：离散时间非线性系统的策略迭代自适应动态规划算法研究附Matlab代码

2026/8/17 1:28:42

✅作者简介&#xff1a;热爱科研的Matlab仿真开发者&#xff0c;擅长毕业设计辅导、数学建模、数据处理、建模仿真、程序设计、完整代码获取、论文复现及科研仿真。&#x1f34e; 往期回顾关注个人主页&#xff1a;Matlab科研工作室&#x1f447; 关注我领取海量matlab电子书和…

【双层规划,节点出清价,绿证交易,CVaR方法】两级电力市场环境下计及风险的省间交易商最优购电模型附Matlab代码

【双层规划,节点出清价,绿证交易,CVaR方法】两级电力市场环境下计及风险的省间交易商最优购电模型附Matlab代码

2026/8/18 1:03:22

✅作者简介&#xff1a;热爱科研的Matlab仿真开发者&#xff0c;擅长毕业设计辅导、数学建模、数据处理、建模仿真、程序设计、完整代码获取、论文复现及科研仿真。&#x1f34e; 往期回顾关注个人主页&#xff1a;Matlab科研工作室&#x1f447; 关注我领取海量matlab电子书和…

隐式mpc+自适应mpc+时变mpc，线性时变模型预测控制附Simulink仿真

隐式mpc+自适应mpc+时变mpc，线性时变模型预测控制附Simulink仿真

2026/8/17 8:40:51

✅作者简介&#xff1a;热爱科研的Matlab仿真开发者&#xff0c;擅长毕业设计辅导、数学建模、数据处理、建模仿真、程序设计、完整代码获取、论文复现及科研仿真。&#x1f34e; 往期回顾关注个人主页&#xff1a;Matlab科研工作室&#x1f447; 关注我领取海量matlab电子书和…

多智能体大模型辩论中的立场收敛：从伪共识到理性说服的评估方法

多智能体大模型辩论中的立场收敛：从伪共识到理性说服的评估方法

2026/8/18 0:06:29

1. 从一场“假辩论”说起&#xff1a;为什么大模型辩论会走向“伪共识”&#xff1f;最近在折腾多智能体大语言模型&#xff08;Multi-Agent LLM&#xff09;的辩论实验&#xff0c;发现一个挺有意思的现象。我让几个基于GPT-4的智能体就一个争议性话题&#xff08;比如“远程办…

Frida动态代码插桩框架：从原理到实战的移动安全与逆向工程指南

Frida动态代码插桩框架：从原理到实战的移动安全与逆向工程指南

2026/8/18 0:06:29

1. 从“黑盒”到“白盒”&#xff1a;为什么我们需要Frida在移动安全、逆向工程甚至是一些自动化测试的场景里&#xff0c;我们经常会遇到一个让人头疼的问题&#xff1a;面对一个编译好的、没有源代码的应用程序&#xff0c;我们如何知道它在运行时内部发生了什么&#xff1f;…

ECharts饼图中心文字配置指南：从label与title区别到动态交互实现

ECharts饼图中心文字配置指南：从label与title区别到动态交互实现

2026/8/18 0:06:29

1. 从“空心”到“有魂”&#xff1a;为什么要在饼图中间加文字&#xff1f;如果你用过ECharts画饼图&#xff0c;大概率会注意到一个现象&#xff1a;默认生成的饼图中间是空心的。这个设计本身没问题&#xff0c;它清晰地展示了各个扇区的占比关系。但在很多实际的业务场景里…

摆脱论文困扰!盘点2026年全网爆红的的AI论文写作工具

摆脱论文困扰!盘点2026年全网爆红的的AI论文写作工具

2026/8/17 12:00:53

一天写完毕业论文在2026年已不再是天方夜谭。2026年最炸裂、实测能大幅提速的AI论文写作工具&#xff0c;覆盖选题构思、文献整理、内容生成、格式排版等核心场景&#xff0c;真正帮你高效搞定论文难题。 一、全流程王者&#xff1a;一站式搞定论文全链路&#xff08;一天定稿首…

导师推荐！2026最新AI论文工具测评与实用推荐

导师推荐！2026最新AI论文工具测评与实用推荐

2026/8/15 10:10:27

2026年真正好用的AI论文工具&#xff0c;核心看生成的论文质量、低AI味、格式正确、学术适配四大指标。综合实测&#xff0c;千笔AI、ThouPen、豆包、DeepSeek、Grammarly 是当前最值得推荐的梯队&#xff0c;覆盖从免费到付费、从中文到英文、从文科到理工的全场景需求。 一、…

告别游戏崩溃：XCOM 2模组管理器的智能革命

告别游戏崩溃：XCOM 2模组管理器的智能革命

2026/8/18 12:20:24

告别游戏崩溃&#xff1a;XCOM 2模组管理器的智能革命 【免费下载链接】xcom2-launcher The Alternative Mod Launcher (AML) is a replacement for the default game launchers from XCOM 2 and XCOM Chimera Squad. 项目地址: https://gitcode.com/gh_mirrors/xc/xcom2-lau…