Python 中的细胞融合

假设我们有一个名为 cells 的数字列表；此列表表示不同细胞的大小。现在，在每次迭代中，两个最大的细胞 a 和 b 根据以下规则进行交互：因此，如果 a = b，则它们都会死亡。否则，这两个细胞合并，它们的大小变为 ((a + b) / 3) 的向下取整。我们必须找到最后一个细胞的大小，或者如果剩余的细胞不存在，则返回 -1。

因此，如果输入类似于 [20,40,40,30]，则输出将为 16，在第一次迭代中，40 和 40 将死亡，然后 20 和 30 变为 ((20+30) / 3) 的向下取整 = 50/3 的向下取整 = 16

为了解决这个问题，我们将遵循以下步骤：

  • cells := 将 cells 数组的每个值转换为负数

  • 使用 cells 创建一个堆

  • 当 cells 不为空时，执行以下操作：

    • 从 cells 中删除两个元素，并将它们再次转换为负数，并依次将它们赋值为 first 和 second

  • 如果 first 不等于 second，则：

    • 将 (first+second)/3 的负数向下取整插入堆中

  • 如果 cells 有一些元素，则返回 cells[0] 的负数，否则返回 -1

让我们看看以下实现，以便更好地理解：

示例

 实时演示

from heapq import heapify, heappop, heappush
class Solution:
   def solve(self, cells):
      cells=[-x for x in cells]
      heapify(cells)
      while len(cells)>1:
         first,second = -heappop(cells), -heappop(cells)
         if first!=second:
            heappush(cells, -((first+second)//3))
      return -cells[0] if cells else -1
ob = Solution()
cells = [20,40,40,30]
print(ob.solve(cells))

输入

[20,40,40,30]

输出

16

更新于：2020 年 9 月 2 日

166 次查看

开启您的 职业生涯

通过完成课程获得认证

开始学习
广告