Skip to content

Latest commit

 

History

History
 
 

1558.Minimum Numbers of Function Calls to Make Target Array

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 
 
 
 
 
 
 
 
 
 
 
 
 
comments difficulty edit_url rating source tags
true
中等
1637
第 33 场双周赛 Q3
贪心
位运算
数组

English Version

题目描述

给你一个与 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

解法

方法一

Python3

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)

Java

class Solution {
    public int minOperations(int[] nums) {
        int ans = 0;
        int mx = 0;
        for (int v : nums) {
            mx = Math.max(mx, v);
            ans += Integer.bitCount(v);
        }
        ans += Integer.toBinaryString(mx).length() - 1;
        return ans;
    }
}

C++

class Solution {
public:
    int minOperations(vector<int>& nums) {
        int ans = 0;
        int mx = 0;
        for (int v : nums) {
            mx = max(mx, v);
            ans += __builtin_popcount(v);
        }
        if (mx) ans += 31 - __builtin_clz(mx);
        return ans;
    }
};

Go

func minOperations(nums []int) int {
	ans, mx := 0, 0
	for _, v := range nums {
		mx = max(mx, v)
		for v > 0 {
			ans += v & 1
			v >>= 1
		}
	}
	if mx > 0 {
		for mx > 0 {
			ans++
			mx >>= 1
		}
		ans--
	}
	return ans
}