使用Python找出二进制字符串中删除10或01后我们可以获得的最高分数的程序

使用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

    • 对于i在A大小范围内的循环,执行:

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

  • stack:=一个新栈

  • 对于A中的每个x,执行:

    • 如果堆栈不为空且堆栈顶元素<x,则
      • 从堆栈中弹出

      • ans:=ans + zero_one

    • 否则:

      • 将x推入堆栈
  • ans:= ans + one_zero * 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

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程