b_lc_构成交替字符串需要的最小交换次数(思维+分类讨论两种方案)

将s转化为一个 交替字符串 。请你计算并返回转化所需的 最小 字符交换次数,如果无法完成转化,返回 -1 。

class Solution:
    def minSwaps(self, s: str) -> int:
        cnt1 = 0
        odd1 = 0
        cnt0 = 0
        n = len(s)

        for i in range(n):
            if s[i] == '1':
                cnt0 += 1
            else:
                cnt1 += 1
                if i % 2 == 0:
                    odd1 += 1
        
        if abs(cnt0 - cnt1) > 1:
            return -1
        
        ans = 0
        if n % 2 == 0: #偶数个,则看看第一位是0还是1,第一位决定了奇数位置上需要交换的个数
            ans = min(odd1, n // 2 - odd1)
        else: 
            if cnt0 > cnt1: # 如果0的个数>1的个数,则0一定要在奇数位置上,才能满足交替,所以此时的交换次数就是:在奇数位置上的1的个数
                ans = odd1
            else: #否则看看不在奇数位上的1的个数
                ans = cnt1 - odd1 
        return ans
上一篇:基于深度主动学习的命名实体识别的代码实现及实验


下一篇:b_lc_实现除法(倍增思想)