这是 LeetCode 3495 的 Java 实现。注意这道题与搜索结果中第一个 GFG 题目数组减1操作完全不同3495 的操作是将两个数替换为 floor(a/4) 和 floor(b/4)。题目理解- 每个查询 [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)。Java 代码javaclass 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 次操作。
