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

福大大架构师每日一题

发布于 2026-01-30 14:59:22

1030

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

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

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

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

1 <= s.length <= 100000。

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

1 <= k <= s.length。

输入： 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（即一次操作必须翻转所有字符）：
- • 若 z == n（字符串全为 '0'），则只需一次操作即可将其变为全 '1'，返回 1。
- • 否则（字符串中既有 '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 < math.MaxInt {
        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 < math.inf else-1

if __name__ == "__main__":
    s = "0101"
    k = 3
    result = minOperations(s, k)
    print(result)

C++完整代码如下：

#include <iostream>
#include <string>
#include <algorithm>
#include <climits>

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_MAX ? ans : -1;
}

int main() {
    string s = "0101";
    int k = 3;
    int result = minOperations(s, k);
    cout << result << endl;
    return0;
}