在Python中找到需要翻转的最小次数,使得值交替出现的程序

在Python中找到需要翻转的最小次数,使得值交替出现的程序

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

因此,如果输入如下:s = “10010101111”,那么输出将是2,因为我们可以取前缀”10″,然后将其移到后面,因此字符串为”01010111110″,然后将从右边翻转第3位和第5位为0(”01010101010″)。

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

  • ans := S的大小

  • N := S的大小

  • s := 0

  • 对于从0到2*N的范围内的i,执行以下操作

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

    • 如果i > = N – 1,则

      • ans := min(ans, s和N – s中的最小值)

      • s := s – (S[(i -(N – 1)) mod N]) XOR ((i – (N – 1)) AND 1)的整数

  • 返回ans

更多Python相关文章,请阅读:Python 教程

示例

让我们看下面的实现以得到更好的理解−

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

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程