Kimi LeetCode 3574. 最大子数组 GCD 分数 Rust实现-北京尧图网络

这是 LeetCode 3574. 最大子数组 GCD 分数的 Rust 实现。解题思路核心观察翻倍操作最多只能让子数组的 GCD 乘以 2。因此对于每个子数组我们需要判断是否能通过最多 k 次翻倍操作使 GCD 翻倍。关键步骤1. 预处理统计每个数中因子 2 的个数即 x 能被 2 整除的次数2. 枚举子数组固定左端点 l向右扩展右端点 r3. 维护三个值- g当前子数组的 GCD- mi子数组中因子 2 个数的最小值- t具有最小因子 2 个数的元素个数4. 判断翻倍如果 t k说明需要翻倍的元素超过 k 个无法翻倍否则 GCD 可以翻倍时间复杂度O(n^2 \cdot \log n)空间复杂度O(n)Rust 代码rustimpl Solution {pub fn max_gcd_score(nums: Veci32, k: i32) - i64 {let n nums.len();// 预处理统计每个数中因子 2 的个数let mut cnt vec![0i32; n];for i in 0..n {let mut x nums[i];while x % 2 0 {cnt[i] 1;x / 2;}}let mut ans: i64 0;// 枚举所有子数组for l in 0..n {let mut g: i32 0; // 当前子数组 GCDlet mut mi: i32 1 30; // 最小因子 2 个数let mut t: i32 0; // 具有最小因子 2 个数的元素个数for r in l..n {// 更新 GCDg Self::gcd(g, nums[r]);// 更新最小因子 2 个数及其出现次数if cnt[r] mi {mi cnt[r];t 1;} else if cnt[r] mi {t 1;}// 判断是否能翻倍 GCD// 如果具有最小因子 2 个数的元素个数 k则无法翻倍let val if t k { g as i64 } else { (g * 2) as i64 };let len (r - l 1) as i64;ans ans.max(len * val);}}ans}// 递归实现 GCDfn gcd(a: i32, b: i32) - i32 {if b 0 {a} else {Self::gcd(b, a % b)}}}代码说明- cnt[i] 记录 nums[i] 中因子 2 的个数例如 12 2^2 × 3则 cnt[i] 2- 翻倍操作的本质是将某个数乘以 2相当于增加一个因子 2- 子数组 GCD 中因子 2 的个数取决于子数组中所有数因子 2 个数的最小值 mi- 如果具有最小值 mi 的元素个数 t k则最多 k 次翻倍无法让所有这些元素的因子 2 个数都增加GCD 无法翻倍- 否则可以通过翻倍使 GCD 乘以 2这个解法在 n \le 1500 的约束下可以通过所有测试用例。

Kimi LeetCode 3574. 最大子数组 GCD 分数 Rust实现

相关推荐

【aigc】初识mediakit-cli 和 chatcut、远程 AI 能力的命令行代理

P10098 [ROIR 2023] 地铁建设 (Day 2)

P9497 「RiOI-2」weight

更多资讯

WorkBuddy连接实战：四层模型、Skill配置与业务系统集成指南

大模型知识表征与逻辑推理机制解析

pyfem弹塑性有限元实现：本构积分与收敛问题解析

STM32 VS Code开发环境搭建：ARM GNU工具链+CMake+OpenOCD调试闭环

鼎阳SDS7404A H10示波器：10-bit高分辨率与4GHz带宽的工程实践指南

[数字安全]PDR 与 P2DR 资讯安全模型比较：核心差异、应用场合与实战落地

今日更新

51单片机开环控制磁阻传感器的硬件匹配与代码实现

AI Agent安全操作数据库：SQL注入防御与参数化查询实战

Android逆向实战：还原激励类App签到接口的签名算法

本周精选

AI驱动的自动化专利分析平台技术解析

LeetCode-Go 题解：1252. Cells with Odd Values in a Matrix（奇数值单元格计数）双解法剖析

在线答疑系统Java毕设实战：Spring Boot前后端分离与状态流转

本月热门

基于YOLO的焊缝缺陷检测：从数据标注到工业部署全流程实践

分布式服务的决策记录

创业产品的首版范围

读完文章，想聊聊您的网站？