Python程式：查詢使二進位制字串交替所需的最小更改次數

假設我們有一個二進位制字串s。我們考慮一個可以翻轉一位的操作。如果字串s中沒有兩個相鄰字元相同，則稱s為交替字串。我們必須找到使s變為交替字串所需的最小操作次數。

因此，如果輸入類似於s = "11100011"，則輸出將為3，因為如果我們翻轉位置1、4和7處的位，則它將變為"10101010"，然後所有位都是交替的。

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

  • change := 0

  • even_1 := 0, even_0 := 0

  • odd_1 := 0, odd_0 := 0

  • 對於範圍從0到s的大小-1的i，執行：

    • 如果i為偶數，則：

      • 如果s[i]與'1'相同，則：

        • even_1 := even_1 + 1

      • 否則：

        • even_0 := even_0 + 1

    • 否則：

      • 如果s[i]與'1'相同，則：

        • odd_1 := odd_1 + 1

      • 否則：

        • odd_0 := odd_0 + 1

  • 如果 (even_1+odd_0) > (even_0+odd_1)，則：

    • change := even_0 + odd_1

  • 否則：

    • change := even_1 + odd_0

  • 返回change

示例（Python）

讓我們看看下面的實現以更好地理解；

 線上演示

def solve(s):
   change = 0
   even_1 = 0
   even_0 = 0
   odd_1 = 0
   odd_0 = 0
   for i in range(len(s)):
      if(i%2 == 0):
         if(s[i]=='1'):
            even_1 +=1
         else:
            even_0 +=1
      else:
         if(s[i] == '1'):
            odd_1 +=1
         else:
            odd_0 +=1
   if((even_1+odd_0)>(even_0+odd_1)):
      change = even_0 + odd_1
   else:
      change = even_1 + odd_0
   return change

s = "11100011"
print(solve(s))

輸入

"11100011"

輸出

3

更新於：2021年5月18日

294 次瀏覽

開始您的職業生涯

完成課程獲得認證

開始學習
廣告