通过k次翻转连续0为1操作求二进制串最大1的数量

问题描述 #

给定仅由0和1组成的二进制字符串，以及操作次数k——每次操作可以把任意一段连续的0全部翻成1，求k次操作后字符串里1的最大数量。

示例 #

• 示例1：输入"00010"，k=1
  输出：4
  解释：把前3个连续0翻成1，得到"11110"，数一下1的数量是4。
• 示例2：输入"1100101001"，k=2
  输出：8
  解释：原字符串里的连续0块是[2,1,2]，选最大的两个块（各2个0）翻转，得到"1111101111"，1的数量是8（原示例的解释结果有误）。

正确解法思路 #

核心思路其实很简单：最终的1的总数 = 原字符串里已有的1的数量 + 我们能翻转的0的数量。要最大化结果，就用k次操作去翻总长度最大的k个连续0块——毕竟翻一个长的0块比翻几个短的能得到更多1。

具体步骤走一遍：

1. 先数出原字符串里1的总数total_ones，这是基础值。
2. 把字符串里所有连续0的长度提取出来，存到zero_blocks数组里：
   • 遍历字符串，遇到0就累加计数，遇到1时如果当前有累计的0长度，就把它放进数组，然后重置计数；遍历结束后别忘了处理末尾可能剩下的连续0。
3. 边界情况处理：如果k比0块的总数还多，那所有0都能被翻成1，直接返回字符串的总长度就行。
4. 计算最多能翻多少个0：把zero_blocks从大到小排序，取前k个加起来，就是能翻转的最大0数量。
5. 最终结果就是total_ones加上这个最大翻转数。

代码实现（Python） #

def max_ones_after_k_flips(s: str, k: int) -> int:
    total_ones = s.count('1')
    zero_blocks = []
    current_zero = 0
    for c in s:
        if c == '0':
            current_zero += 1
        else:
            if current_zero > 0:
                zero_blocks.append(current_zero)
                current_zero = 0
    # 处理字符串末尾的连续0
    if current_zero > 0:
        zero_blocks.append(current_zero)
    
    # 如果k足够翻所有0块，直接返回总长度
    if k >= len(zero_blocks):
        return len(s)
    
    # 取最大的k个0块求和
    zero_blocks.sort(reverse=True)
    max_flip = sum(zero_blocks[:k])
    return total_ones + max_flip

# 测试示例1
print(max_ones_after_k_flips("00010", 1))  # 输出4
# 测试示例2
print(max_ones_after_k_flips("1100101001", 2))  # 输出8

关于滑动窗口的误区 #

你尝试用滑动窗口没成功，是因为滑动窗口适合的是另一种场景——比如每次操作只能翻转固定数量的0，或者求最长的包含最多k个0的子串这类问题。而当前问题的操作是每次可以翻任意长度的连续0块（算一次操作），最优策略就是挑最大的k个0块来翻，根本用不上滑动窗口。要是你之前误解了操作规则（比如以为每次只能翻一个0），那滑动窗口才可能有用，但按问题描述和示例来看，上面的解法才是正确的。

内容的提问来源于stack exchange，提问作者bugdebug