【LeetCode - 每日1题】使数组元素都变为零的最少操作次数

🌈 个人主页：（时光煮雨）
🔥 高质量专栏：vulnhub靶机渗透测试
👈 希望得到您的订阅和支持~
💡 创作高质量博文(平均质量分95+)，分享更多关于网络安全、Python领域的优质内容！（希望得到您的关注~）

---

---

难度 ⭐⭐⭐⭐⭐

本题要求高效处理多个查询，每个查询涉及一个连续整数数组，通过特定操作将所有元素变为零，求最少操作次数总和。核心在于数学推导和高效计算前缀和。

---

题目回顾

给你一个二维数组 queries，其中 queries[i] 形式为 [l r]。每个 queries[i] 表示了一个元素范围从l到 r
（包括 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

解释：

对于 queries[0]：

• 初始数组为 nums = [2, 3, 4, 5, 6]。
• 在第一次操作中，选择 nums[0] 和 nums[3]。数组变为 [0, 3, 4, 1, 6]。
• 在第二次操作中，选择 nums[2] 和 nums[4]。数组变为 [0, 3, 1, 1, 1]。
• 在第三次操作中，选择 nums[1] 和 nums[2]。数组变为 [0, 0, 0, 1, 1]。
• 在第四次操作中，选择 nums[3]> 和 nums[4]。数组变为 [0, 0, 0, 0, 0]。
• 所需的最小操作次数为 4。

输出为 4。

提示：

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

---

✅解题思路

💖概述

• 给定多个查询，每个查询为区间 [l, r]，表示数组包含从 l到 r的连续整数。
• 每次操作选择数组中的两个整数 a和 b，替换为 floor(a/4)和 floor(b/4)。
• 目标：计算每个查询的最少操作次数（使所有元素为零），并返回所有查询结果的总和。

💓核心思路

1. ​​独立计算每个数的操作次数​​

   • 定义 g(n)：将单个整数 n变为零所需的最少操作次数。
     • 递归关系：g(n) = 1 + g(n // 4)（n > 0），g(0) = 0。
     • 例如：
       • g(1) = 1（1 // 4 = 0）。
       • g(4) = 2（4 // 4 = 1，再操作一次得 0）。
   • 观察规律：g(n) = k当 n ∈ [4^{k-1}, 4^k - 1]。
     • k=1：[1, 3]
     • k=2：[4, 15]
     • k=3：[16, 63]