Python程序：查找将所有球移动到当前位置所需的总距离列表

假设我们有一个名为 nums 的二进制列表，其中只包含 0 和 1，其中 0 表示空单元格，1 表示单元格被球填充。我们必须找到一个新的列表，例如 L，其大小也与 nums 大小相同，其中 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
  • result := 一个新列表
  • 对于 nums 中的每个索引和值 num，执行以下操作：
    • 如果 num 非零，则
      • right_count := right_count + 1
      • right_sum := right_sum + index
  • 对于 nums 中的每个索引和值 num，执行以下操作：
    • 将 (left_sum + right_sum) 插入到 result 的末尾
    • 如果 num 非零，则
      • right_count := right_count - 1
      • left_count := left_count + 1
    • left_sum := left_sum + left_count
    • right_sum := right_sum - right_count
  • 返回 result

示例

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

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]

更新于： 2021年10月16日

95 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告