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 次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始學習
廣告