[leetcode] 1558. Minimum Numbers of Function Calls to Make Target Array

[leetcode] 1558. Minimum Numbers of Function Calls to Make Target Array

Description

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: 5Explanation: 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: 3Explanation: 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: 6Explanation: (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^50 <= nums[i] <= 10^9

分析

题目的意思是：题目给定了一个函数，这个函数的功能为：如果是op是1，则当前的数加1；如果op是2，则当前的数组乘以2. 求从0开始得到给定的nums的最小操作步数。

我一开始想到的方法是从结果反推回去，如果全是偶数，则整个数组的数除以2，否则，把其中的奇数减1，可以证明，能够达到最小次数哈。如果知道这个，则只需要在做上述两个操作的时候维护res就能得到结果了

代码

class Solution: def isAllEven(self,nums): for num in nums: if(num%2==1): return False return True def minOperations(self, nums: List[int]) -> int: res=0 nums.sort() n=len(nums) while(nums[-1]!=0): while(self.isAllEven(nums)): nums=[item//2 for item in nums] res+=1 for i in range(n): if(nums[i]%2==1): nums[i]-=1 res+=1 return res

参考文献

​​得到目标数组的最少函数调用次数​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。