Python程式：查詢二進位制字串中最多翻轉一個0後最長連續1子字串的長度

假設我們有一個二進位制字串 s。我們最多允許將一個“0”翻轉為“1”，我們需要找到最長連續1子字串的長度。

因此，如果輸入類似於 s = "1010110001"，則輸出將為 4，因為如果我們將索引 3 處的零翻轉，則得到字串 "1011110001"，這裡最長連續1子字串的長度為 4。

為了解決這個問題，我們將遵循以下步驟：

  • n := s 的大小
  • ans := 0，ones := 0，left := 0，right := 0
  • 當 right < n 時，執行以下操作：
    • 如果 s[right] 等於 "1"，則：
      • ones := ones + 1
    • 當 right - left + 1 - ones > 1 時，執行以下操作：
      • remove := s[left]
      • 如果 remove 等於 "1"，則：
        • ones := ones - 1
      • left := left + 1
    • ans := ans 和 (right - left + 1) 中的最大值
    • right := right + 1
  • 返回 ans

示例

讓我們看看以下實現以獲得更好的理解：

def solve(s):
   n = len(s)
   ans = ones = left = right = 0
   while right < n:
      if s[right] == "1":
         ones += 1
      while right - left + 1 - ones > 1:
         remove = s[left]
         if remove == "1":
            ones -= 1
         left += 1
      ans = max(ans, right - left + 1)
      right += 1
   return ans

s = "1010110001"
print(solve(s))

輸入

"1010110001"

輸出

4

更新於： 2021年10月19日

597 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

立即開始
廣告