leetcode 2026-02-27 每日一练 - 使二进制字符串全为 1 的最少操作次数

Austoin2026-02-272026-02-27

题目描述

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

给你一个二进制字符串 s 和一个整数 k。

在一次操作中，你必须选择恰好 k 个不同的下标，并将每个 '0' 翻转为 '1'，每个 '1' 翻转为 '0'。

返回使字符串中所有字符都等于 '1' 所需的最少操作次数。如果不可能，则返回 -1。

解题思路

核心观察

目标是把 z 个 0 变成 1，同时让原本的 1 尽量不被翻成 0（最终要全是 1）。

关键结论：

一个位置被翻转奇数次，状态会改变
一个位置被翻转偶数次，状态不变

因此问题可以转化为：

对每个 0：需要被翻转奇数次（才能变 1）
对每个 1：需要被翻转偶数次（最好是 0 次，保持 1）
总共有 m 次操作，每次选 k 个位置，所有位置被翻转的次数总和 = m × k

数学推导

推导 1：奇偶性约束

约束 1：操作次数 `m` 为偶数时，`z` 必须是偶数

假设操作了 m 次（偶数），那么：

所有 z 个 0 都需要被翻转奇数次
这 z 个位置的总翻转次数 = 奇数 + 奇数 + ... + 奇数（z 个）
结果的奇偶性取决于 z：
- z 为偶数 → 总和为偶数
- z 为奇数 → 总和为奇数
而总操作次数是偶数（m 偶），每次选 k 个位置
所有位置的总翻转次数 = m × k（偶数）

结论：为了满足奇偶性匹配，z 必须是偶数。

示例：

z=2（偶数），m=2（偶数）→ 符合约束 ✓
z=3（奇数），m=2（偶数）→ 3 个奇数相加是奇数，而 m×k=2×3=6（偶数）→ 奇偶不匹配 ✗

约束 2：操作次数 `m` 为奇数时，`z` 和 `k` 必须同奇偶

同理，m 是奇数时：

总翻转次数 m × k = 奇数 × k → 奇偶性和 k 一致
z 个 0 的总翻转次数的奇偶性取决于 z
两者必须一致 → z % 2 == k % 2

示例：

z=3（奇）、k=3（奇）→ 同奇偶，符合 ✓
z=3（奇）、k=2（偶）→ 不同奇偶，不可能用奇数次操作完成 ✗

推导 2：下界计算

公式：`max((z+k-1)/k, ...)`

这个公式本质是向上取整，(z + k - 1) / k 是编程中求 ⌈z/k⌉ 的常用技巧（不用浮点运算）。

第一部分：`(z + k - 1) / k` → 覆盖所有 `0` 的最少操作次数

我们至少需要多少次操作，才能让每个 0 都被翻转到（奇数次）？

每次操作最多能翻 k 个 0
最少需要 ⌈z/k⌉ 次

示例：

z=2, k=3 → (2+3-1)/3 = 4/3 = 1 → 至少 1 次
z=5, k=2 → (5+2-1)/2 = 6/2 = 3 → 至少 3 次（2+2+1，3 次才能覆盖 5 个 0）

第二部分：限制 `1` 被翻转的次数

这部分是为了避免”翻转太多 1“导致无法恢复。

n-k 是每次操作中不翻转的位置数（总长度 n，每次翻 k 个，剩下 n-k 个不翻）
对于偶数次操作：要保证原本的 1 被翻转偶数次 → 下界是 (z + n - k - 1)/(n - k)
对于奇数次操作：要保证原本的 1 被翻转偶数次 → 下界是 (n-z + n - k - 1)/(n - k)（n-z 是 1 的个数）

大白话解释：如果每次操作都尽量少翻 1，那么”不翻的位置（n-k 个）”要优先留给 1，这样 1 被翻的次数才会少。

最终取两个下界的最大值，因为要同时满足”覆盖所有 0“和”不翻坏所有 1“。

推导 3：调整操作次数

我们算出的下界 m 可能是奇数或偶数，但我们当前讨论的是”偶数次操作”或”奇数次操作”的情况，所以需要把 m 调整为符合要求的最小数：

偶数调整：m + m%2
- m=1（奇）→ 1+1=2
- m=2（偶）→ 2+0=2
奇数调整：m|1（二进制技巧）
- m=2（10）|1 = 3（11）
- m=3（11）|1 = 3
- 本质是”向上取最近的奇数”

示例验证

示例：s="0101"（n=4, z=2, k=3）

偶数次操作

约束判断：z=2 是偶数 → 符合 ✓
计算下界：
- (z+k-1)/k = (2+3-1)/3 = 4/3 = 1
- (z+n-k-1)/(n-k) = (2+4-3-1)/(4-3) = 2/1 = 2
- 取最大值 → m=2
调整为偶数：2 是偶数 → ans=2

奇数次操作

约束判断：z%2=0, k%2=1 → 不匹配，跳过 ✗

最终答案：ans=2 ✓

总结

核心推导逻辑 3 点：

奇偶性约束：操作次数的奇偶性，决定了 z（0 的个数）必须满足的条件
- 偶次操作 → z 偶
- 奇次操作 → z 和 k 同奇偶
下界计算：用向上取整算出”覆盖所有 0“和”不翻坏 1“的最少操作次数，取最大值
调整次数：把下界调整为符合奇偶性要求的最小数，最终取所有有效情况的最小值

代码实现

func minOperations(s string, k int) int {
	n := len(s)
	z := strings.Count(s, "0")
	if z == 0 {
		return 0
	}
	if k == n {
		if z == n {
			return 1
		}
		return -1
	}

	ans := math.MaxInt
	if z%2 == 0 {
		m := max((z+k-1)/k, (z+n-k-1)/(n-k))
		ans = m + m%2                        
	}

	if z%2 == k%2 { 
		m := max((z+k-1)/k, (n-z+n-k-1)/(n-k)) 
		ans = min(ans, m|1)                   
	}

	if ans < math.MaxInt {
		return ans
	}
	return -1
}