核心逻辑在于从高位到低位逐位试填。因为要使最终的 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 的总和还要大,感兴趣吗?