Python程序：检查从栈中弹出一些元素后所有栈的最大总和

假设我们有一组栈，我们可以选择任意一个或多个栈，并从中弹出任意数量的元素。我们必须找到可以达到的最大总和，使得所有栈具有相同的和值。

因此，如果输入类似于 stacks = [[3, 4, 5, 6], [5, 6, 1, 4, 4], [10, 2, 2, 2] ]，则输出将为 12，因为我们可以执行以下操作：

  • 从第一个栈弹出 [6]，得到 [3, 4, 5]，总和为 12。

  • 从第二个栈弹出 [4, 4]，得到 [5, 6, 1]，总和为 12。

  • 从第三个栈弹出 [2, 2]，得到 [10, 2]，总和为 12。

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

  • sums := 一个空映射

  • 对于 stacks 中的每个 stk：

    • s := 0

    • 对于 stk 中的每个 n：

      • s := s + n

      • sums[s] := sums[s] + 1

  • ans := 0

  • 对于 sums 的每个键值对 (s, f)：

    • 如果 f >= 栈的数量 且 s > ans，则

      • ans := s

  • 返回 ans

让我们看看下面的实现来更好地理解：

示例

 在线演示

from collections import defaultdict
class Solution:
   def solve(self, stacks):
      sums = defaultdict(int)
      for stk in stacks:
         s = 0
         for n in stk:
            s += n
            sums[s] += 1
         ans = 0
         for s, f in sums.items():
            if f >= len(stacks) and s > ans:
               ans = s
         return ans
ob1 = Solution()
stacks = [
   [3, 4, 5, 6],
   [5, 6, 1, 4, 4],
   [10, 2, 2, 2]
]
print(ob1.solve(stacks))

输入

stacks = [ [3, 4, 5, 6], [5, 6, 1, 4, 4], [10, 2, 2, 2] ]

输出

12

更新于：2020年10月21日

229 次浏览

开启你的职业生涯

完成课程获得认证

开始学习
广告