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

假设我们有一个二进制字符串s。现在假设我们可以取s的某个前缀并将其移到后面，然后找到需要翻转的最小字符数，这样就不会出现相同值的连续字符。

因此，如果输入类似于s = "10010101111"，则输出将为2，因为我们可以取前缀"10"，然后将其移到后面，所以字符串变为"01010111110"，然后将从右数的第3位和第5位翻转为0 ("01010101010")。

为了解决这个问题，我们将遵循以下步骤：

  • ans := S的长度

  • N := S的长度

  • s := 0

  • 对于 i 从 0 到 2 * N，执行：

    • s := s + int(S[i mod N] XOR (i AND 1))

    • 如果 i >= N - 1，则：

      • ans := min(ans, s, N - s)

      • s := s - int(S[(i -(N - 1)) mod N] XOR ((i - (N - 1)) AND 1))

  • 返回 ans

示例

让我们看看下面的实现，以便更好地理解：

 在线演示

class Solution:
   def solve(self, S):
      ans = N = len(S)
      s = 0
      for i in range(2 * N):
         s += int(S[i % N]) ^ (i & 1)
         if i >= N - 1:
            ans = min(ans, s, N - s)
            s -= int(S[(i - (N - 1)) % N]) ^ ((i - (N - 1)) & 1)
      return ans
ob = Solution()
s = "10010101111"
print(ob.solve(s))

输入

"10010101111"

输出

2

更新于：2020年12月22日

浏览量：353

开启你的职业生涯

完成课程获得认证

开始学习
广告