2025-09-21：使数组元素都变为零的最少操作次数。用go语言，给定若干查询，每个查询由一对整数 l、r 指定，表示起始数组

2025-09-21：使数组元素都变为零的最少操作次数。用go语言，给定若干查询，每个查询由一对整数 l、r 指定，表示起始数组包含所有落在闭区间 [l, r] 内的整数。每次操作你可以从数组中选出两个元素，把它们各自替换为对 4 取整除（向下取整）的商。对于每个查询，求把该区间对应的数组全部变为 0 所需的最少操作次数，最后把所有查询的这些最少次数相加并返回该总和。

1 <= queries.length <= 100000。

queries[i].length == 2。

queries[i] == [l, r]。

1 <= l < r <= 1000000000。

输入： 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。

题目来自力扣3495。

分步骤描述过程

1. 问题理解

• • 每次操作：选择两个元素，分别用它们除以4（向下取整）的商替换（即 x = x // 4）。
• • 目标：将数组中的所有元素变为0，求最少操作次数。
• • 输入：多个查询，每个查询是一个区间 [l, r]，数组包含该区间内所有整数。
• • 输出：所有查询的最少操作次数之和。

2. 关键观察

• • 操作本质：每次操作将两个元素的值除以4（即右移2位），相当于每个元素不断进行除以4的操作直到变为0。
• • 一个元素变为0所需的操作次数：实际上，每个元素需要被“处理”多次（每次除以4），直到变为0。但注意，一次操作可以处理两个元素（但每个元素可能参与多次操作）。
• • 实际上，问题可以转化为：每个元素需要被“除以4”的次数（即其“深度”）之和，但操作一次可以处理两个元素，因此需要统筹安排。

经过分析（参考代码和典型解法）：

• • 实际上，最少操作次数与每个数变为0所需的“步数”有关，但操作允许同时处理两个数。
• • 典型解法：定义函数 f(n) 表示将区间 [1, n] 内所有数变为0所需的最少操作次数（或类似前缀和）。
• • 代码中 get(num) 函数计算的是区间 [1, num] 的某种代价（或操作次数相关量）。

3. 代码中的 get(num) 函数分析

• • 该函数遍历以2的幂为基数的区间（即 [base, base*2-1]，其中 base=1,2,4,8,...）。
• • 对于每个区间，计算一个权重 (i+1)/2（其中 i 是区间索引，从1开始），乘以区间长度（即 end-base+1），并累加到 cnt。
• • 例如：
  • • 对于 num=2：
    • • 第一段：base=1，区间 [1,1]（因为 end=min(1*2-1,2)=1），权重 (1+1)/2=1，贡献 1*1=1。
    • • 第二段：base=2，区间 [2,2]（end=min(3,2)=2），权重 (2+1)/2=1（整数除法），贡献 1*1=1。
    • • 总 cnt=2。
• • 但实际查询 [1,2] 的操作次数为1，所以代码中最后返回 (count1 - count2 + 1) / 2 进行调整。

实际上：

• • get(num) 返回的是区间 [1, num] 内所有数的“总深度”（每个数需要被除以4的次数之和）？但权重 (i+1)/2 可能表示该区间内每个数的“操作次数贡献”。
• • 注意：操作一次可以处理两个数，因此总操作次数大约是总深度的一半（但需要向上取整？）。

代码中对于查询 [l, r]：

• • 计算 count1 = get(r)
• • 计算 count2 = get(l-1)
• • 该查询的答案：(count1 - count2 + 1) / 2

例如查询 [1,2]：

• • count1 = get(2)=2（如上计算）
• • count2 = get(0)=0
• • 操作次数 (2-0+1)/2 = 3/2=1（整数除法，结果为1）。

查询 [2,4]：

• • 计算 get(4)：
  • • 第一段 [1,1]：权重1，长度1 → 1
  • • 第二段 [2,3]：权重 (2+1)/2=1，长度2 → 2
  • • 第三段 [4,4]：权重 (3+1)/2=2，长度1 → 2
  • • 总 get(4)=1+2+2=5
• • get(1)=1（第一段区间 [1,1] 贡献1）
• • 操作次数 (5-1+1)/2=5/2=2（整数除法）。

所以代码正确。

4. 整体流程

• • 对于每个查询 [l, r]：
  • • 计算 get(r)：得到区间 [1, r] 的累计值。
  • • 计算 get(l-1)：得到区间 [1, l-1] 的累计值。
  • • 该查询的操作次数 = (get(r) - get(l-1) + 1) / 2（整数除法）。
• • 将所有查询的操作次数相加，返回总和。

5. get(num) 函数的数学含义

• • 将数字按二进制位分组（按最高位位置分组，即 [2^k, 2^(k+1)-1]）。
• • 每组（区间）内的数，需要被除以4的次数（即“深度”）是相同的（或类似），权重 (i+1)/2 实际上表示该组每个数的“深度”（或操作中的贡献次数）。
• • 例如，区间 [1,1]（二进制1位）深度为1；区间 [2,3]（二进制2位）深度为1；区间 [4,7]（二进制3位）深度为2（因为4需要除以2次4才到0？）等等。

实际上，每个数 x 的操作次数深度为 ceil( (bit_length(x)) / 2 )？但代码中权重是 (i+1)/2，其中 i 是组索引（从1开始），即第 i 组的深度为 (i+1)/2（整数除法）。

• • 组1（i=1）：[1,1]，深度 (1+1)/2=1。
• • 组2（i=2）：[2,3]，深度 (2+1)/2=1。
• • 组3（i=3）：[4,7]，深度 (3+1)/2=2。
• • 组4（i=4）：[8,15]，深度 (4+1)/2=2。
• • 组5（i=5）：[16,31]，深度 (5+1)/2=3。

这符合预期：每个数的深度大约是二进制位数的一半（向上取整）。

所以 get(num) 计算的是区间 [1, num] 内所有数的深度之和。

6. 为什么查询操作次数为 (深度和之差 + 1) / 2？

• • 总深度和表示所有数需要被“处理”的总次数（每个数都要被除以4多次，直到0）。
• • 但一次操作可以处理两个数（即减少两个单位的深度），所以总操作次数至少为总深度和的一半（向上取整）。
• • 因此，对于区间 [l, r]，总深度和 = get(r) - get(l-1)，操作次数 = (总深度和 + 1) / 2（向上取整）。

例如查询 [1,2]：

• • 总深度和=2，操作次数=(2+1)/2=1（正确）。 查询 [2,4]：
• • 总深度和= get(4)-get(1)=5-1=4，操作次数=(4+1)/2=2（正确）。

复杂度分析

• • 时间复杂度：
  • • 函数 get(num) 中，循环次数为 num 的二进制位数，即 O(log(num))。
  • • 每个查询调用两次 get（分别计算 get(r) 和 get(l-1)），所以每个查询处理时间 O(log(r))。
  • • 总查询数 Q，最大 r 为 10^9（二进制位数约30），所以总时间复杂度为 O(Q * log(max_r)) = O(100000 * 30) = O(3e6)，可以接受。
• • 额外空间复杂度：
  • • 只使用了常数额外空间（循环变量和临时变量），所以为 O(1)。

总结

• • 通过分组计算深度和，利用前缀和思想求区间深度和，再通过向上取整的一半得到操作次数。
• • 总时间复杂度：O(Q * log(max_value))。
• • 总额外空间复杂度：O(1)。

Go完整代码如下：

.

package main

import (
    "fmt"
)

func get(num int)int64 {
    var cnt int64
    i := 1
    base := 1

    for base <= num {
        end := base*2 - 1
        if end > num {
            end = num
        }
        cnt += int64((i+1)/2) * int64(end-base+1)
        i++
        base *= 2
    }
    return cnt
}

func minOperations(queries [][]int)int64 {
    var res int64
    for _, q := range queries {
        count1 := get(q[1])
        count2 := get(q[0] - 1)
        res += (count1 - count2 + 1) / 2
    }
    return res
}

func main() {
    queries := [][]int{{1, 2}, {2, 4}}
    result := minOperations(queries)
    fmt.Println(result)
}

Python完整代码如下：

.

# -*-coding:utf-8-*-

def get(num: int) -> int:
    if num < 1:
        return0
    cnt = 0
    i = 1
    base = 1
    while base <= num:
        end = base * 2 - 1
        if end > num:
            end = num
        cnt += ((i + 1) // 2) * (end - base + 1)
        i += 1
        base *= 2
    return cnt

def min_operations(queries):
    res = 0
    for l, r in queries:
        count1 = get(r)
        count2 = get(l - 1)
        res += (count1 - count2 + 1) // 2
    return res

if __name__ == "__main__":
    queries = [[1, 2], [2, 4]]
    result = min_operations(queries)
    print(result)

我们相信Go语言和算法为普通开发者提供了困境的“面试利器”，并致力于分享全面的编程知识。在这里，您可以找到最新的Go语言教程、算法解析、提升面试竞争力的秘籍以及行业动态。 欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让 Go 语言和算法助力您的职业发展