使用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 次瀏覽

開啟你的職業生涯

透過完成課程獲得認證

開始學習
廣告