得到目标数组的最少函数调用次数
难度:
标签:
题目描述
给你一个与 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
代码结果
运行时间: 36 ms, 内存: 23.5 MB
/*
* 题目思路：
* 1. 对于每个数字nums[i]，我们可以将其转换为二进制表示。二进制中1的个数表示加1操作的次数。
* 2. 最高位的1所在的位数表示乘以2操作的次数。
* 3. 我们需要对每个数字计算其加1操作和乘以2操作的总次数，并取最大的乘以2操作次数。
*/
import java.util.stream.IntStream;
public class Solution {
public int minOperations(int[] nums) {
int addOperations = IntStream.of(nums)
.map(num -> Integer.bitCount(num))
.sum();
int maxMultiplyOperations = IntStream.of(nums)
.map(num -> 31 - Integer.numberOfLeadingZeros(num))
.max()
.orElse(0);
return addOperations + maxMultiplyOperations;
}
}解释
方法:
此题解通过反向思维来求解：考虑如何从数组 `nums` 逆向得到全零数组。首先，计算每个数字需要多少次加法操作，即每个数字的二进制表示中 '1' 的个数，这些 '1' 都需要一次加法操作来实现。其次，考虑数组中的最大值，需要乘2的操作次数是最大数的二进制位长度减1（因为从1开始，乘2达到相应长度）。因此，总的操作次数为所有数字需要的加法次数之和加上最大数需要的乘法次数。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
为什么在计算乘2操作的次数时，使用的是最大数的二进制长度减1，而不是直接使用二进制长度？
▷🦆
算法中提到的`op1`是计算所有数字中二进制表示的1的总数，请问这种方法为什么能准确计算出需要的加法操作次数？
▷🦆
在代码中，`max(0, max(nums).bit_length() - 1)`使用了`max(0, ...)`，这是为了处理哪些特殊情况？
▷🦆
如果`nums`数组中包含零或负数，这个算法是否仍然有效？为什么？
▷