Kimi LeetCode 3495. 使数组元素都变为零的最少操作次数 Python3实现

这是 LeetCode 3495 的 Python3 实现。题目理解- 每个查询 [l, r] 定义数组 nums [l, l1, ..., r]- 每次操作选两个数 a, b替换为 ⌊a/4⌋ 和 ⌊b/4⌋- 求将所有元素变为 0 的最少操作次数核心思路一个数 x 变为 0 需要的操作次数是满足 4^p x 的最小 p即 ⌊log₄x⌋ 1。对于区间 [l, r]- 设 s 为区间内所有元素各自所需操作次数之和- 设 mx 为区间内最大操作次数即 r 所需次数- 每次操作最多同时处理两个元素所以至少需要 ⌈s/2⌉ 次操作- 但某些元素如 r需要 mx 次操作才能归零所以答案为 max(⌈s/2⌉, mx)用前缀和优化定义 f(x) 为 [1, x] 所有元素操作次数之和则 s f(r) - f(l-1)mx f(r) - f(r-1)。Python3 代码pythonclass Solution:def minOperations(self, queries: list[list[int]]) - int:ans 0for l, r in queries:s self.f(r) - self.f(l - 1) # 区间总操作次数mx self.f(r) - self.f(r - 1) # 最大元素的操作次数ans max((s 1) // 2, mx) # max(ceil(s/2), mx)return ansdef f(self, x: int) - int:计算 [1, x] 所有数的操作次数之和res 0p 1 # 4的幂次i 1 # 当前区间需要的操作次数while p x:# 区间 [p, min(4p-1, x)] 内的数都需要 i 次操作cnt min(p * 4 - 1, x) - p 1res cnt * ii 1p * 4return res复杂度分析- 时间复杂度O(q · log₄M)其中 q 为查询数M ≤ 10⁹- 空间复杂度O(1)关键说明f(x) 将 [1, x] 按 4 的幂次分段- [1, 3]需要 1 次操作4¹ x- [4, 15]需要 2 次操作4² x- [16, 63]需要 3 次操作4³ x- 以此类推...每段长度为 3·4^(i-1)段内每个数贡献 i 次操作。