在 Python 中計算移除連續相同位所需要的運算元的程式

假設我們有一個二進位制字串 s，那麼讓我們考慮一個操作，其中我們選擇一個位並將其值從 0 翻轉到 1 或從 1 翻轉到 0。我們必須找到獲得不含連續三個相同位的字串所需的最小運算元。

因此，如果輸入類似於 s = "10011100"，則輸出將為 1，因為我們可以將索引 4 處的位 1 翻轉為 0 以使字串 "10010100" 不含連續三個相同位。

要解決這個問題，我們將按照以下步驟操作 −

• l := 0，計數 := 0
• 當 l < s 的大小時，執行
  • r := l
  • 當 r < s 的大小且 s[r] 與 s[l] 相同時，執行
    • r := r + 1
  • 計數 := 計數 + (（r - l）/ 3) 的下取整
  • l := r
• 返回計數

示例

讓我們看看以下實現以更好地理解 −

def solve(s):
   l = 0
   count = 0
   while l < len(s):
      r = l
      while r < len(s) and s[r] == s[l]:
         r += 1
      count += (r - l) // 3
      l = r
   return count

s = "10011100"
print(solve(s))

輸入

"10011100"

輸出

1

Arnab Chakraborty

更新於： 14-10-2021

192 次瀏覽

開啟您的 職業生涯

完成課程認證

開始