01串修改

[编程题]01串修改

热度指数：1207 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个只包含'0'和'1'两种字符的字符串，每次操作可以选择相邻的两个字符，将它们同时变成'0'或者同时变成'1'。

请问最少多少次操作后，所有的字符都相同？

字符串长度不超过1000。

示例1

输入

"1001101"

输出

算法知识视频讲解

Python

pein531

分别求一下改为全零串和全一串的代价，返回两者中的较小值即可。由于是对称的，以改为全一串为例：分割字符串得到所有连续零的子串，然后挨个将每个零串改成全一串即可。对于一个长度为 $n$ 的全零串，要将它改为全一串，需要进行的操作次数为 $\frac{n+1}{2}$ ，所有次数累加起来就得到了总的操作次数。

落单的零是没有关系的，如果剩下一个0，它必然和一个1是相邻的，我们只要进行一次操作将01改成11即可。

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param str string字符串 
# @return int整型
#
class Solution:
    def minOperations(self , s: str) -> int:
        # write code here
        return min(self.getop(s, '1'), self.getop(s, '0'))

    def getop(self, s: str, delimter: str):
        terms = [term for term in s.split(delimter) if term]
        cnt = 0
        for term in terms:
            cnt += (len(term) + 1) >> 1
        return cnt

发表于 2023-02-01 17:58:04 回复(0)