在 Python 中计算移除连续相同位所需要的操作数的程序

假设我们有一个二进制字符串 s，那么让我们考虑一个操作，其中我们选择一个位并将其值从 0 翻转到 1 或从 1 翻转到 0。我们必须找到获得不含连续三个相同位的字符串所需的最小操作数。

因此，如果输入类似于 s = "10011100"，则输出将为 1，因为我们可以将索引 4 处的位 1 翻转为 0 以使字符串 "10010100" 不含连续三个相同位。

要解决这个问题，我们将按照以下步骤操作 −

  • l := 0，计数 := 0
  • 当 l < s 的大小时，执行
    • r := l
    • 当 r < s 的大小且 s[r] 与 s[l] 相同时，执行
      • r := r + 1
    • 计数 := 计数 + (（r - l）/ 3) 的下取整
    • l := r
  • 返回计数

示例

让我们看看以下实现以更好地理解 −

def solve(s):
   l = 0
   count = 0
   while l < len(s):
      r = l
      while r < len(s) and s[r] == s[l]:
         r += 1
      count += (r - l) // 3
      l = r
   return count

s = "10011100"
print(solve(s))

输入

"10011100"

输出

1

更新于： 14-10-2021

192 次浏览

开启您的 职业生涯

完成课程认证

开始
广告