使用 Python 查找最小函数调用次数以制作目标数组的程序

假设我们有以下函数定义：

def modify(arr, op, index):
   if op == 0:
      arr[index] += 1
   if op == 1:
      for i in range(len(arr)):
         arr[i] *=2

我们必须找到从一个相同大小的零数组创建给定数组 nums 所需的最少函数调用次数？

因此，如果输入类似于 nums = [1,5,3]，那么输出将是 7，因为最初所有元素都是 0, [0,0,0]

• 在第一步将第二个元素增加 1，所以数组是 [0,1,0]

• 将第二个元素加倍以使其成为 [0,2,0]

• 将第三个元素增加 1，因此数组为 [0,2,1]

• 从索引 1 到 2 的双精度元素，所以数组是 [0,4,2]

• 将所有元素增加 1 [这里总共三个操作]

所以总共需要 3+4 = 7 次操作。

为了解决这个问题，我们将按照以下步骤操作 -

• ans := 一个有两个元素的数组都是0

• 对于 nums 中的每个 n，做

• 如果 n 是奇数，那么

• 否则，

• n := n/2 的商

• 双 := 双 + 1

• n := n - 1

• ans[0] := ans[0] + 1

• 双:= 0

• 当 n 非零时，做

• ans[1] := ans[1] 和 double 的最大值

• 返回 ans 所有元素的总和

让我们看看以下实现以获得更好的理解 -

示例

def solve(nums):
   ans = [0, 0]
   for n in nums:
      double = 0
      while(n):
         if not n%2:
            n = n//2
            double+=1
         else:
            n-=1
            ans[0]+=1
            ans[1] = max(ans[1], double)
   return sum(ans)
nums = [1,5,3]
print(solve(nums))

输入

[1,5,3]

7