Python程序：求解从二进制字符串中移除“10”或“01”后可获得的最大分数

假设我们有一个二进制字符串s和两个值zero_one和one_zero。现在让我们考虑一个操作，我们可以删除任何子字符串“01”并获得zero_one分。或者我们可以删除任何子字符串“10”并获得one_zero分。我们必须找到在任何数量的操作后可以获得的最大分数。

因此，如果输入类似于s = "10100101" zero_one = 3 one_zero = 2，则输出将为11，因为我们可以删除三次“01”以获得3*3 = 9分。然后剩余的字符串是10。通过删除它，我们可以获得另外2分，所以总分是11。

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

  • A := 一个作为输入字符串给出的位列表

  • 如果zero_one < one_zero，则

    • 交换zero_one和one_zero

    • 对于范围为0到A大小的i，执行：

      • A[i] := A[i] XOR 1

  • ans := 0

  • stack := 一个新的栈

  • 对于A中的每个x，执行：

    • 如果栈非空且栈顶元素 < x，则

      • 从栈中弹出

      • ans := ans + zero_one

    • 否则，

      • 将x压入栈

  • ans := ans + one_zero * min(栈中0的出现次数, 栈中1的出现次数)

  • 返回ans

示例（Python）

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

 在线演示

class Solution:
   def solve(self, S, zero_one, one_zero):
      A = list(map(int, S))
      if zero_one < one_zero:
         zero_one, one_zero = one_zero, zero_one
         for i in range(len(A)):
            A[i] ^= 1
         ans = 0
         stack = []
         for x in A:
            if stack and stack[-1] < x:
               stack.pop()
               ans += zero_one
            else:
               stack.append(x)
         ans += one_zero * min(stack.count(0), stack.count(1))
         return ans
ob = Solution()
s = "10100101"
zero_one = 3
one_zero = 2
print(ob.solve(s, zero_one, one_zero))

输入

"10100101", 3, 2

输出

11

更新于：2020年12月22日

290 次浏览

开启你的职业生涯

完成课程获得认证

开始学习
广告