news 2026/6/6 13:54:34

文心 LeetCode 3022. 给定操作次数内使剩余元素的或值最小 Python3实现

作者头像

张小明

前端开发工程师

1.2k 24
文章封面图
文心 LeetCode 3022. 给定操作次数内使剩余元素的或值最小 Python3实现

核心逻辑在于从高位到低位逐位试填。因为要使最终的 OR 结果最小,必须尽可能让高位为 0。
实现思路
2. 贪心试填:从第 29 位遍历到第 0 位。对于每一位,假设我们可以让它变为 0,并结合之前已经确定可以为 0 的高位掩码(mask),检查在 kkk 次操作内是否可行。
3. 掩码校验:构造一个 target 掩码,表示我们希望哪些位在最终结果中为 0。遍历数组,利用相邻合并(AND 操作)的特性,计算将数组划分为若干个其 AND 结果能填满 target 掩码的块所需的最小操作次数。
4. 操作计数:每合并两个元素计为 1 次操作。如果一段连续元素的 AND 结果与 target 取与后仍不为 0,说明这一段必须继续与下一个元素合并。
代码实现
【python】
class Solution:
def minOrAfterOperations(self, nums: list[int], k: int) -> int:
ans = 0
mask = 0
# 从最高位开始试探
for i in range(29, -1, -1):
# 假设第 i 位可以为 0,与之前确定的高位 mask 结合
test_mask = mask | (1 << i)
cnt = 0
# 初始化为全 1,用于连续 AND 运算
and_res = (1 << 30) - 1

for x in nums: # 仅保留我们关心的(试图变为 0 的)位 and_res &= (x & test_mask) if and_res != 0: cnt += 1 # 还没达到 0,需要继续合并,操作数加 1 else: and_res = (1 << 30) - 1 # 达到 0,开启新的一段 if cnt <= k: # 如果操作数达标,说明这些位可以都变为 0 mask = test_mask else: # 否则,第 i 位必须是 1 ans |= (1 << i) return ans

关键点
这个解法巧妙在于,它并没有真的去"模拟"合并过程,而是利用了 mmm 个元素合并成 1 个元素需要 m−1m-1m−1 次操作 的原理。如果整个数组被分成了 SSS 段,且每段的 AND 结果都能让目标位清零,那么总操作次数就是 n−Sn - Sn−S。

其实还有一个逻辑上的小陷阱:为什么从高位到低位贪心一定是对的?这背后其实是因为二进制的权值特点,任何一个高位的 1 都比后面所有低位全是 1 的总和还要大,感兴趣吗?

版权声明: 本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若内容造成侵权/违法违规/事实不符,请联系邮箱:809451989@qq.com进行投诉反馈,一经查实,立即删除!
网站建设 2026/6/6 13:52:25

计算机小程序毕设实战-基于Android的医院健康管理平台的设计与实现小程序健康管理微信小程序【完整源码+LW+部署说明+演示视频,全bao一条龙等】

博主介绍&#xff1a;✌️码农一枚 &#xff0c;专注于大学生项目实战开发、讲解和毕业&#x1f6a2;文撰写修改等。全栈领域优质创作者&#xff0c;博客之星、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java、小程序技术领域和毕业项目实战 ✌️技术范围&#xff1a;&am…

作者头像 李华
网站建设 2026/6/6 13:50:15

英雄联盟玩家的智能助手:5分钟掌握LeagueAkari本地化工具

英雄联盟玩家的智能助手&#xff1a;5分钟掌握LeagueAkari本地化工具 【免费下载链接】League-Toolkit An all-in-one toolkit for LeagueClient. Gathering power &#x1f680;. 项目地址: https://gitcode.com/gh_mirrors/le/League-Toolkit 你是否曾在紧张的排位赛B…

作者头像 李华
网站建设 2026/6/6 13:50:08

LinkSwift网盘直链助手:突破下载限制的技术解析与实用指南

LinkSwift网盘直链助手&#xff1a;突破下载限制的技术解析与实用指南 【免费下载链接】Online-disk-direct-link-download-assistant 一个基于 JavaScript 的网盘文件下载地址获取工具。基于【网盘直链下载助手】修改 &#xff0c;支持 百度网盘 / 阿里云盘 / 中国移动云盘 / …

作者头像 李华