LeetCode 题解工作台
得到目标数组的最少函数调用次数
给你一个与 nums 大小相同且初始值全为 0 的数组 arr ，请你调用以上函数得到整数数组 nums 。 请你返回将 arr 变成 nums 的最少函数调用次数。 答案保证在 32 位有符号整数以内。 示例 1： 输入： nums = [1,5] 输出： 5 解释： 给第二个数加 1 ：[0, …
3
题型
4
代码语言
3
相关题
当前训练重点
中等 · 贪心·invariant
答案摘要
class Solution: def minOperations(self, nums: List[int]) -> int:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 贪心·invariant 题型思路
题目描述
给你一个与 nums 大小相同且初始值全为 0 的数组 arr ，请你调用以上函数得到整数数组 nums 。
请你返回将 arr 变成 nums 的最少函数调用次数。
答案保证在 32 位有符号整数以内。
示例 1：
输入：nums = [1,5] 输出：5 解释：给第二个数加 1 ：[0, 0] 变成 [0, 1] （1 次操作）。 将所有数字乘以 2 ：[0, 1] -> [0, 2] -> [0, 4] （2 次操作）。 给两个数字都加 1 ：[0, 4] -> [1, 4] -> [1, 5] （2 次操作）。 总操作次数为：1 + 2 + 2 = 5 。
示例 2：
输入：nums = [2,2] 输出：3 解释：给两个数字都加 1 ：[0, 0] -> [0, 1] -> [1, 1] （2 次操作）。 将所有数字乘以 2 ： [1, 1] -> [2, 2] （1 次操作）。 总操作次数为： 2 + 1 = 3 。
示例 3：
输入：nums = [4,2,5] 输出：6 解释：（初始）[0,0,0] -> [1,0,0] -> [1,0,1] -> [2,0,2] -> [2,1,2] -> [4,2,4] -> [4,2,5] （nums 数组）。
示例 4：
输入：nums = [3,2,2,4] 输出：7
示例 5：
输入：nums = [2,4,8,16] 输出：8
提示：
1 <= nums.length <= 10^50 <= nums[i] <= 10^9
解题思路
方法一
class Solution:
def minOperations(self, nums: List[int]) -> int:
return sum(v.bit_count() for v in nums) + max(0, max(nums).bit_length() - 1)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n * log(max(nums[i]))) because each element may be halved up to log(max value) times. Space complexity is O(1) beyond input storage since we only track counters and the maximum doubling depth. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Mentions working backwards or reverse operations from target array.
- question_mark
Hints at bit manipulation or handling even/odd numbers separately.
- question_mark
Focuses on greedy accumulation of increments and maximum doubling.
常见陷阱
外企场景- error
Incrementing forwards without considering doubling causes overcounting operations.
- error
Treating doubling per element rather than globally leads to suboptimal solutions.
- error
Ignoring edge cases where elements are zero or powers of two can miscount operations.
进阶变体
外企场景- arrow_right_alt
Allow decrement operations instead of increments and recalculate minimal steps.
- arrow_right_alt
Change the doubling operation to triple all elements, requiring updated greedy logic.
- arrow_right_alt
Target array contains negative numbers, requiring separate handling for subtractive steps.