Problem: 3666. 使二进制字符串全为 1 的最少操作次数

[TOC]

思路

公式推导

先计数，假设有a个0，则b = n - a，假设选取ta个0进行反转，ta范围推导如下：
$$
0 \le ta \le a \
ta \le k \
k - ta \le b \
k-b \le ta \
\Downarrow \

\max(0,k - b) \le ta \le \min(a,k)
$$

又因为 tb = k - ta，即选取tb个1进行反转
因此a可以扩展为[mn_a,mx_a]:
$$
a + tb - ta = a + k - ta * 2 \
mn_a = a + k - mx_ta * 2 \
mx_a = a + k - mn_ta * 2
$$

        # 扩展区间
        def getExArea(a):
            b = n - a
            # max(0,k - b) <= ta <= min(a,k)
            mn_ta = max(0,k - b) 
            mx_ta = min(a,k)

            #  a + k - ta - ta
            mn_a = a + k - mx_ta * 2
            mx_a = a + k - mn_ta * 2
            
            return mn_a,mx_a

上面是第一次扩展，那下一次扩展 $a ∈ [mn_a,mx_a] $ 呢？遍历区间内的值肯定超时。
其实，对于每一个a值，就是一个滑动窗口的过程，得到的区间是具有单调性的，因此我们只需要关注区间的边界值即可，因此每一次都对区间边界值进行扩展，得到一个更大的区间即可

区间扩展出口

当满足以下两个条件即可终止扩展：

• $k ∈ [mn_a,mx_a] $
• $ k\ &\ 1 = mn_a\ &\ 1 $

第一个条件很容易理解，a可以满足等于k，那下一次操作直接把k个0转化成1就好了。

第二个条件就是奇偶性相等，为何要满足这个条件呢？其实模拟一下操作就知道了，假设
a = 9, b = 11, k = 5

虽然扩展后，k ∈ [4,14] ，但很明显这个区间范围内的值是公差为2的等差数列，得不到a = k = 5，因此要满足与k奇偶性相等才行。

那如何判断满足不了题意呢？扩展区间过程中，如果还没达到扩展出口条件，且出现扩展区间重复，那就满足不了题意了，return -1

        # 获取 0 的个数
        a = 0
        for w in s:
            if w == '0':
                a += 1

        res = 0
        la,ra = a,a
        dt = set()
        dt.add((la,ra))
        while la:
            if la <= k <= ra and la&1 == k&1:
                res += 1
                break
            mn_la,mx_la = getExArea(la)
            mn_ra,mx_ra = getExArea(ra)

            nla = min(mn_la,mn_ra)
            nra = max(mx_la,mx_ra)
            # 扩展过了
            if (nla,nra) in dt:
                return -1
            
            la,ra = nla,nra
            dt.add((la,ra))
            res += 1
        
        return res

贪心优化

• 如果 a >= 2 * k，可以贪心的a -= k，且操作结果+1
• 如果 b >= 2 * k，可以贪心的b -= k

        n = len(s)
        # 获取 0 的个数
        a = 0
        for w in s:
            if w == '0':
                a += 1
        b = n - a
        # 贪心优化
        res = 0
        while a >= 2 * k:
            res += 1
            a -= k
            b += k
        
        while b >= 2 * k:
            b -= k
        n = a + b

更多题目模板总结，请参考2024年度总结与题目分享

Code

###Python3

class Solution:
    def minOperations(self, s: str, k: int) -> int:
        '''
        计数：
        a,b 分别为 0,1的数目
        0 的数目区间扩展 区间扩展
        若 k 为偶数
        (a,b)

        左扩展
        ta <= a
        ta <= k
        k - ta <= b
        max(0,k - b) <= ta <= min(a,k)
        tb = k - ta

        a = a + tb - ta
        a = a + k - ta - ta
        b = n - a

        求出 a,b 对应最小值，最大值
        '''
        n = len(s)
        # 获取 0 的个数
        a = 0
        for w in s:
            if w == '0':
                a += 1
        b = n - a
        # 贪心优化
        res = 0
        while a >= 2 * k:
            res += 1
            a -= k
            b += k
        
        while b >= 2 * k:
            b -= k
        n = a + b
        
        # 扩展区间
        def getExArea(a):
            b = n - a
            # max(0,k - b) <= ta <= min(a,k)
            mn_ta = max(0,k - b) 
            mx_ta = min(a,k)

            #  a + k - ta - ta
            mn_a = a + k - mx_ta * 2
            mx_a = a + k - mn_ta * 2
            
            return mn_a,mx_a


        la,ra = a,a
        dt = set()
        dt.add((la,ra))
        while la:
            if la <= k <= ra and la&1 == k&1:
                res += 1
                break
            mn_la,mx_la = getExArea(la)
            mn_ra,mx_ra = getExArea(ra)

            nla = min(mn_la,mn_ra)
            nra = max(mx_la,mx_ra)
            # 扩展过了
            if (nla,nra) in dt:
                return -1
            
            la,ra = nla,nra
            dt.add((la,ra))
            res += 1
        
        return res