Python程序：查找使二进制字符串交替所需的最小更改次数

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"

输出

Arnab Chakraborty

更新于：2021年5月18日

294 次浏览

开始您的职业生涯

完成课程获得认证

开始学习