使用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，执行以下操作：

    • double := 0

    • 当n不为零时，执行以下操作：

      • 如果n是奇数，则

        • n := n/2 的商

        • double := double + 1

      • 否则，

        • n := n - 1

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

    • 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

更新于：2021年5月29日

247 次浏览

开启你的职业生涯

通过完成课程获得认证

开始学习
广告