Pythonを使用してターゲット配列を作成するための関数呼び出しの最小数を見つけるプログラム

次の関数定義があるとします。

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

同じサイズの1つのゼロ配列から特定の配列番号を作成するために必要な関数呼び出しの最小数を見つける必要がありますか？

したがって、入力がnums =[1,5,3]のような場合、最初はすべての要素が0、[0,0,0]

• 最初のステップで2番目の要素を1増やし、配列は[0,1,0]

  になります。

• 2番目の要素を2倍にして[0,2,0]

• 3番目の要素を1増やして、配列が[0,2,1]

  になるようにします。

• インデックス1から2までの要素が2つあるため、配列は[0,4,2]

• すべての要素を1つ増やします[ここでは合計3つの操作]

したがって、合計3 + 4=7回の操作が必要です。

これを解決するには、次の手順に従います-

• ans：=2つの要素を持つ配列はすべて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