2026-01-30: 使二进制字符串全为 1 的最少操作次数。用go语言, 给

2026-01-30：使二进制字符串全为 1 的最少操作次数。用go语言，给你一个只含 0 和 1 的字符串 s，以及一个整数 k。

一次操作中必须从不同的位置中选出恰好 k 个索引，并把这些位置上的字符取反（0 变为 1，1 变为 0）。要求通过若干次这样的操作，把字符串变为全部为 1。

输出使字符串全部变为 1 所需的最少操作次数；如果无论如何都办不到，则返回 -1。

1

s[i] 的值为 '0' 或 '1'。

1

输入： s = "0101", k = 3。

输出： 2。

解释：

每次操作选择 k = 3 个下标的一种最优操作方案是：

操作 1：翻转下标 [0, 1, 3]。s 从 "0101" 变为 "1000"。

操作 2：翻转下标 [1, 2, 3]。s 从 "1000" 变为 "1111"。

因此，最少操作次数为 2。

题目来自力扣3666。

步骤一：问题初始化与边界情况处理

1. 获取字符串长度与统计零的个数：

首先，代码获取字符串 s 的长度 n，并统计其中 '0' 的个数 z。例如，对于 s = "0101"，n = 4，z = 2。

2. 处理无需操作的情况：

如果 z == 0，说明字符串已经全为 '1'，无需任何操作，直接返回 0。

3. 处理必须一次性翻转所有字符的情况：

如果 k == n（即一次操作必须翻转所有字符）：

• 否则（字符串中既有 '0' 也有 '1'），一次翻转后 '0' 会变成 '1'，但原来的 '1' 会变成 '0'，无法达到全 '1'，因此返回 -1。

步骤二：核心计算过程

核心思想是，每次操作翻转 k 个位置，相当于改变了 z（'0' 的数量）的值。每次操作后，z 的变化量是 k - 2 * (被翻转位置中原本是 '0' 的数量)。为了最小化操作次数，需要找到一种操作序列，使得 z 最终变为 0。

代码通过分析操作次数的奇偶性与初始 z 和 k 的奇偶性关系，来推导最小操作次数 m。它考虑了两种情况：

1. 情况一：操作次数 m 为偶数

• 前提条件：初始 '0' 的个数 z 必须是偶数（z % 2 == 0）。

• 计算最小操作次数下界：

通过公式 m1 = max((z + k - 1) / k, (z + n - k - 1) / (n - k)) 计算一个理论上的最小操作次数下界。这个公式考虑了最有效的翻转方式。

• 调整奇偶性：

由于此情况要求 m 为偶数，因此将 m1 向上调整为最接近的偶数，作为该情况的候选答案。

2. 情况二：操作次数 m 为奇数

• 前提条件：初始 '0' 的个数 z 和每次翻转的个数 k 必须具有相同的奇偶性（z % 2 == k % 2）。

• 计算最小操作次数下界：

使用另一个公式 m2 = max((z + k - 1) / k, (n - z + n - k - 1) / (n - k)) 来计算下界。

• 调整奇偶性：

将 m2 向上调整为最接近的奇数，作为此情况的候选答案。

步骤三：结果确定

• 比较情况一和情况二得到的两个候选操作次数（如果它们都有效），取其中较小的那个作为最终答案。

• 如果两种情况都没有产生有效的候选值（即 ans 仍为初始的最大整数值），说明无法通过操作将字符串变为全 '1'，返回 -1。

⏱️ 复杂度分析

• 总的时间复杂度：O(n)。这主要来自于开始时使用 strings.Count 函数遍历字符串来统计 '0' 的个数 z。后续的计算步骤只涉及常数时间的数学运算。

• 总的额外空间复杂度：O(1)。算法只使用了固定数量的整数变量（如 n, z, k, ans, m 等），没有使用与输入规模 n 相关的额外空间。

总结

这个算法巧妙地利用了奇偶性这一数学性质，避免了复杂的模拟过程，将问题转化为在特定约束条件下寻找满足奇偶性的最小操作数，从而实现了高效的求解。

Go完整代码如下：

package main

import (

"fmt"

"math"

"strings"

)

func minOperations(s string, k int)int {

n := len(s)

z := strings.Count(s, "0")

if z == 0 {

return0

}

if k == n {

if z == n {

return1

}

return-1

}

ans := math.MaxInt

// 情况一：操作次数 m 是偶数

if z%2 == 0 { // z 必须是偶数

m := max((z+k-1)/k, (z+n-k-1)/(n-k)) // 下界

ans = m + m%2 // 把 m 往上调整为偶数

}

// 情况二：操作次数 m 是奇数

if z%2 == k%2 { // z 和 k 的奇偶性必须相同

m := max((z+k-1)/k, (n-z+n-k-1)/(n-k)) // 下界

ans = min(ans, m|1) // 把 m 往上调整为奇数

}

if ans

return ans

}

return-1

}

func main {

s := "0101"

k := 3

result := minOperations(s, k)

fmt.Println(result)

}

Python完整代码如下：

# -*-coding:utf-8-*-

import math

def minOperations(s: str, k: int) -> int:

n = len(s)

z = s.count('0')

if z == 0:

return0

if k == n:

if z == n:

return1

return-1

ans = math.inf

# 情况一：操作次数 m 是偶数

if z % 2 == 0: # z 必须是偶数

m = max((z + k - 1) // k, (z + n - k - 1) // (n - k)) # 下界

ans = m + (m % 2) # 把 m 往上调整为偶数

# 情况二：操作次数 m 是奇数

if z % 2 == k % 2: # z 和 k 的奇偶性必须相同

m = max((z + k - 1) // k, (n - z + n - k - 1) // (n - k)) # 下界

ans = min(ans, m if m % 2 == 1else m + 1) # 把 m 往上调整为奇数

return ans if ans

if __name__ == "__main__":

s = "0101"

k = 3

result = minOperations(s, k)

print(result)

C++完整代码如下：

#include

#include

#include

#include

using namespace std;

int minOperations(string s, int k) {

int n = s.length;

int z = count(s.begin, s.end, '0');

if (z == 0) {

return0;

}

if (k == n) {

if (z == n) {

return1;

}

return-1;

}

int ans = INT_MAX;

// 情况一：操作次数 m 是偶数

if (z % 2 == 0) { // z 必须是偶数

int m = max((z + k - 1) / k, (z + n - k - 1) / (n - k)); // 下界

ans = m + (m % 2); // 把 m 往上调整为偶数

}

// 情况二：操作次数 m 是奇数

if (z % 2 == k % 2) { // z 和 k 的奇偶性必须相同

int m = max((z + k - 1) / k, (n - z + n - k - 1) / (n - k)); // 下界

ans = min(ans, m | 1); // 把 m 往上调整为奇数

}

return ans

}

int main {

string s = "0101";

int k = 3;

int result = minOperations(s, k);

cout

return0;

}

我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。

欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。