原文链接: https://leetcode-cn.com/problems/minimum-numbers-of-function-calls-to-make-target-array

英文原文

Your task is to form an integer array nums from an initial array of zeros arr that is the same size as nums.

Return the minimum number of function calls to make nums from arr.

The answer is guaranteed to fit in a 32-bit signed integer.

 

Example 1:

Input: nums = [1,5]
Output: 5
Explanation: Increment by 1 (second element): [0, 0] to get [0, 1] (1 operation).
Double all the elements: [0, 1] -> [0, 2] -> [0, 4] (2 operations).
Increment by 1 (both elements)  [0, 4] -> [1, 4] -> [1, 5] (2 operations).
Total of operations: 1 + 2 + 2 = 5.

Example 2:

Input: nums = [2,2]
Output: 3
Explanation: Increment by 1 (both elements) [0, 0] -> [0, 1] -> [1, 1] (2 operations).
Double all the elements: [1, 1] -> [2, 2] (1 operation).
Total of operations: 2 + 1 = 3.

Example 3:

Input: nums = [4,2,5]
Output: 6
Explanation: (initial)[0,0,0] -> [1,0,0] -> [1,0,1] -> [2,0,2] -> [2,1,2] -> [4,2,4] -> [4,2,5](nums).

Example 4:

Input: nums = [3,2,2,4]
Output: 7

Example 5:

Input: nums = [2,4,8,16]
Output: 8

 

Constraints:

• 1 <= nums.length <= 10^5
• 0 <= nums[i] <= 10^9

中文题目

给你一个与 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^5
• 0 <= nums[i] <= 10^9

通过代码

高赞题解

解题思路

这题可以理解为，在全体不断乘二的过程中，选择是否给某一个数单独加一。
所以就不难联想到二进制了，因为二进制的乘二是左移一位，加一正好是把末尾变成 1。

例如 5，二进制是 101，我们要怎么得到 5 呢？
0 -> 1(加一) -> 10(乘二) -> 100(乘二) -> 101(加一)

不难发现，每个数的二进制数的一是必须手动添加的，每个数都得把1给加上。
所以第一步，统计所有数的二进制数中 1 的个数。
我们又发现，它进行了两步乘二。但是我们看第一个例子，[1,5]
1 是直接加一，是不需要乘二的。
1 在变成 1 之前，必须一直为 0，直到 5 完毕了，它才可以加一，否则一旦全部乘二，它也会变化。

那么其实可以得出结论，具体移位（也就是乘二）的次数，是由最大的数来决定的，比它小的数，只要在合适的时机跟着最大的数变化就好了。
（由于只要统计次数，具体的时机我们不需要知道）

所以，我们只需要维护一个最大值，来计算它的移位次数，也就它的二进制有几位。
但是由于肯定最开始给它加了 1，才能移位（最高位不能为 0），所以移位次数是它位数 -1，最后返回时减了 1。

[]
class Solution {
public:
    int minOperations(vector<int>& nums) {
        int ans = 0;
        int max_num = 0;
        for (auto i : nums){
            if (i > max_num) max_num = i;
            while (i > 0){
                if (i & 1) ans++;
                i /= 2;
            }
        }
        while (max_num > 0){
            ans++;
            max_num /= 2;
        }
        return ans - 1;
    }
};

统计信息

通过次数	提交次数	AC比率
4642	7447	62.3%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言