Pythonですべてのボールを現在の位置に移動するために必要な合計距離を示すリストを見つけるためのプログラム

0と1のみを含むnumsというバイナリリストがあるとします。ここで、0は空のセルを示し、1はセルがボールで満たされていることを示します。サイズがnumssizeと同じである、たとえばLの新しいリストを見つける必要があります。ここで、L [i]は、すべてのボールをL[i]に移動するのに必要な合計距離に設定されます。ここで、ボールをインデックスjからインデックスiに移動する距離は| j--i|です。

したがって、入力がnums =[1、1、0、1]のような場合、出力は[4、3、4、5]になります。これは、

• L [0] =| 0-0 | + | 1-0 | + | 3-0 |
• L [1] =| 0-1 | + | 1 --1 | + | 3-1 |
• L [2] =| 0-2 | + | 1-2 | + | 3-2 |
• L [3] =| 0-3 | + | 1-3 | + | 3-3 |

したがって、すべてのボールをL [1]に移動するには、ボールをインデックス0から1に距離1で移動し、ボールをインデックス3から1に距離2で移動する必要があります。

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

• numsが空の場合、
  • 新しいリストを返す
• left_count：=0
• right_count：=0
• left_sum：=0
• right_sum：=0
• 結果：=新しいリスト
• nums単位のインデックスと値numごとに、
  を実行します。
  • numがゼロ以外の場合、
    • right_count：=right_count + 1
    • right_sum：=right_sum+インデックス
• nums単位のインデックスと値numごとに、
  を実行します。
  • 結果の最後に（left_sum + right_sum）を挿入します
  • numがゼロ以外の場合、
    • right_count：=right_count-1
    • left_count：=left_count + 1
  • left_sum：=left_sum + left_count
  • right_sum：=right_sum --right_count
• 結果を返す

例

理解を深めるために、次の実装を見てみましょう-

def solve(nums):
   if not nums:
      return []

   left_count = right_count = 0
   left_sum = right_sum = 0
   result = []

   for index, num in enumerate(nums):
      if num:
         right_count += 1
         right_sum += index

   for index, num in enumerate(nums):
      result.append(left_sum + right_sum)

      if num:
         right_count -= 1
         left_count += 1

      left_sum += left_count
      right_sum -= right_count

   return result

nums = [1, 1, 0, 1]
print(solve(nums))

入力

[1, 1, 0, 1]

出力

[4, 3, 4, 5]