Kimi LeetCode 3495. 使数组元素都变为零的最少操作次数 Java实现
这是 LeetCode 3495 的 Java 实现。注意这道题与搜索结果中第一个 GFG 题目（数组减1操作）完全不同，3495 的操作是将两个数替换为 `floor(a/4)` 和 `floor(b/4)`。
题目理解
- 每个查询 `[l, r]` 定义一个数组 `nums = [l, l+1, ..., 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)`。
Java 代码
```java
class Solution {
public long minOperations(int[][] queries) {
long ans = 0;
for (int[] q : queries) {
int l = q[0], r = q[1];
long s = f(r) - f(l - 1); // 区间总操作次数
long mx = f(r) - f(r - 1); // 最大元素的操作次数
ans += Math.max((s + 1) / 2, mx); // max(ceil(s/2), mx)
}
return ans;
}
// 计算 [1, x] 所有数的操作次数之和
private long f(long x) {
long res = 0;
long p = 1; // 4的幂次
int i = 1; // 当前区间需要的操作次数
while (p <= x) {
// 区间 [p, min(4p-1, x)] 内的数都需要 i 次操作
long cnt = Math.min(p * 4 - 1, x) - p + 1;
res += cnt * i;
i++;
p *= 4;
}
return 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` 次操作。