Hard

题目描述

给你一个二维数组 queries，其中 queries[i] 的形式为 [l, r]。每个 queries[i] 定义了一个由 l 到 r（两端包含）范围内的整数组成的数组 nums。

在一次操作中，你可以：

  • 从数组中选择两个整数 a 和 b
  • 将它们分别替换为 floor(a / 4) 和 floor(b / 4)

你的任务是确定对于每个查询，将数组的所有元素减少为零所需的最少操作数。返回所有查询结果的总和。

示例 1：

输入：queries = [[1,2],[2,4]]
输出：3
解释：
对于 queries[0]：
- 初始数组为 nums = [1, 2]
- 第一次操作，选择 nums[0] 和 nums[1]，数组变为 [0, 0]
- 所需最少操作数为 1

对于 queries[1]：
- 初始数组为 nums = [2, 3, 4]  
- 第一次操作，选择 nums[0] 和 nums[2]，数组变为 [0, 3, 1]
- 第二次操作，选择 nums[1] 和 nums[2]，数组变为 [0, 0, 0]
- 所需最少操作数为 2

输出为 1 + 2 = 3

示例 2：

输入：queries = [[2,6]]
输出：4

约束条件：

  • 1 <= queries.length <= 10^5
  • queries[i].length == 2
  • queries[i] == [l, r]
  • 1 <= l < r <= 10^9

提示：

  • 对于数字 x，将其变为 0 所需的除 4 操作次数为 floor(log4(x)) + 1
  • 总是将需要最多除 4 操作的两个数字配对

解题思路

这道题的核心思想是理解每次操作可以同时处理两个数字，将它们都除以 4 向下取整。

分析过程：

  1. 单个数字的操作次数计算：对于任意数字 x，要将其变为 0，需要的操作次数是 ⌊log₄(x)⌋ + 1。这是因为每次除以 4，直到小于 1 为止。

  2. 最优配对策略：由于每次操作可以选择两个数字，最优策略是将需要操作次数最多的两个数字配对。这样可以最大化每次操作的效率。

  3. 贪心算法：

    • 计算范围 [l, r] 内每个数字需要的操作次数
    • 将这些操作次数按降序排序
    • 从最大的开始，每次取两个数字配对，操作次数为较大的那个
    • 如果数组长度为奇数，最后剩下的数字单独处理

  4. 优化思路：

    • 可以按操作次数分组，计算每组的数量
    • 从操作次数最多的组开始配对
    • 使用贪心策略确保最少的总操作数

时间复杂度优化：由于 log₄(10⁹) ≈ 15，操作次数的种类很有限，可以用计数的方式而不是排序来优化。

代码实现

class Solution {
public:
    long long minOperations(vector<vector<int>>& queries) {
        long long result = 0;
        
        for (auto& query : queries) {
            int l = query[0], r = query[1];
            map<int, int> count; // 操作次数 -> 数量
            
            // 计算每个数字需要的操作次数
            for (int num = l; num <= r; num++) {
                int ops = 0;
                int temp = num;
                while (temp > 0) {
                    temp /= 4;
                    ops++;
                }
                count[ops]++;
            }
            
            // 贪心配对，从操作次数最多的开始
            for (auto it = count.rbegin(); it != count.rend(); ++it) {
                int ops = it->first;
                int cnt = it->second;
                
                // 配对处理
                result += (long long)ops * (cnt + 1) / 2;
            }
        }
        
        return result;
    }
};

class Solution:
    def minOperations(self, queries: List[List[int]]) -> int:
        def get_operations(x):
            ops = 0
            while x > 0:
                x //= 4
                ops += 1
            return ops
        
        result = 0
        
        for l, r in queries:
            # 统计每种操作次数的数量
            count = {}
            for num in range(l, r + 1):
                ops = get_operations(num)
                count[ops] = count.get(ops, 0) + 1
            
            # 贪心配对，从操作次数最多的开始
            for ops in sorted(count.keys(), reverse=True):
                cnt = count[ops]
                # 配对处理，向上取整
                result += ops * (cnt + 1) // 2
        
        return result

public class Solution {
    public long MinOperations(int[][] queries) {
        long result = 0;
        
        foreach (var query in queries) {
            int l = query[0], r = query[1];
            var count = new Dictionary<int, int>(); // 操作次数 -> 数量
            
            // 计算每个数字需要的操作次数
            for (int num = l; num <= r; num++) {
                int ops = GetOperations(num);
                count[ops] = count.GetValueOrDefault(ops, 0) + 1;
            }
            
            // 贪心配对，从操作次数最多的开始
            var sortedOps = count.Keys.OrderByDescending(x => x);
            foreach (int ops in sortedOps) {
                int cnt = count[ops];
                // 配对处理
                result += (long)ops * (cnt + 1) / 2;
            }
        }
        
        return result;
    }
    
    private int GetOperations(int x) {
        int ops = 0;
        while (x > 0) {
            x /= 4;
            ops++;
        }
        return ops;
    }
}

/**
 * @param {number[][]} queries
 * @return {number}
 */
var minOperations = function(queries) {
    function getOperations(x) {
        let ops = 0;
        while (x > 0) {
            x = Math.floor(x / 4);
            ops++;
        }
        return ops;
    }
    
    let result = 0;
    
    for (let [l, r] of queries) {
        // 统计每种操作次数的数量
        const count = new Map();
        for (let num = l; num <= r; num++) {
            const ops = getOperations(num);
            count.set(ops, (count.get(ops) || 0) + 1);
        }
        
        // 贪心配对，从操作次数最多的开始
        const sortedOps = Array.from(count.keys()).sort((a, b) => b - a);
        for (let ops of sortedOps) {
            const cnt = count.get(ops);
            // 配对处理
            result += ops * Math.floor((cnt + 1) / 2);
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型数值
时间复杂度O(Q × R × log₄(max(r)))
空间复杂度O(log₄(max(r)))

其中 Q 是查询数量，R 是每个查询的范围大小 (r-l+1)，log₄(max(r)) ≈ 15 对于约束条件中的最大值。