Hard

题目描述

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

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

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

示例 1：

输入：s = "110", k = 1
输出：1
解释：
s 中有一个 '0'。
由于 k = 1，我们可以直接在一次操作中翻转它。

示例 2：

输入：s = "0101", k = 3
输出：2
解释：
每次操作选择 k = 3 个索引的一组最优操作是：
操作 1：翻转索引 [0, 1, 3]。s 从 "0101" 变为 "1000"。
操作 2：翻转索引 [1, 2, 3]。s 从 "1000" 变为 "1111"。
因此，最少操作数是 2。

示例 3：

输入：s = "101", k = 2
输出：-1
解释：
由于 k = 2 且 s 只有一个 '0'，无法恰好翻转 k 个索引来使所有字符都变为 '1'。因此答案是 -1。

约束条件：

  • 1 <= s.length <= 10^5
  • s[i] 是 '0' 或 '1'
  • 1 <= k <= s.length

解题思路

这道题的核心思路是将问题抽象为状态转移，使用BFS寻找最短路径。

状态定义：用字符串中 0 的个数 z 来表示当前状态，目标是从初始的 0 个数到达状态 0（所有字符都是 1）。

状态转移分析：在一次操作中，我们选择恰好 k 个位置进行翻转。假设选择了 i 个 0 和 (k-i) 个 1：

  • 翻转后，i 个 0 变成 1，(k-i) 个 1 变成 0
  • 因此 0 的个数从 z 变为 z - i + (k-i) = z + k - 2*i
  • i 的取值范围：max(0, k-(n-z)) ≤ i ≤ min(k, z)

关键观察：

  1. 从状态 z 能到达的所有状态 z' 都满足 z' ≡ z + k (mod 2)，即奇偶性相同
  2. 可达状态在一个连续区间内

算法流程：

  1. 用BFS从初始状态（0 的个数）开始搜索
  2. 对每个状态，计算所有可达的下一状态
  3. 使用有序集合按奇偶性分组管理未访问状态，提高效率
  4. 当到达状态 0 时返回步数

这是一个图论问题，时间复杂度近似 O(n log n)。

代码实现

class Solution {
public:
    int minOperations(string s, int k) {
        int n = s.length();
        int zeros = count(s.begin(), s.end(), '0');
        
        if (zeros == 0) return 0;
        
        vector<set<int>> unvisited(2);
        for (int i = 0; i <= n; i++) {
            unvisited[i % 2].insert(i);
        }
        
        queue<pair<int, int>> q;
        q.push({zeros, 0});
        unvisited[zeros % 2].erase(zeros);
        
        while (!q.empty()) {
            auto [z, steps] = q.front();
            q.pop();
            
            if (z == 0) return steps;
            
            int min_flip_zeros = max(0, k - (n - z));
            int max_flip_zeros = min(k, z);
            
            int min_next = z + k - 2 * max_flip_zeros;
            int max_next = z + k - 2 * min_flip_zeros;
            
            int parity = (z + k) % 2;
            auto& parity_set = unvisited[parity];
            
            auto it_start = parity_set.lower_bound(min_next);
            auto it_end = parity_set.upper_bound(max_next);
            
            vector<int> to_remove;
            for (auto it = it_start; it != it_end; ++it) {
                q.push({*it, steps + 1});
                to_remove.push_back(*it);
            }
            
            for (int val : to_remove) {
                parity_set.erase(val);
            }
        }
        
        return -1;
    }
};

class Solution:
    def minOperations(self, s: str, k: int) -> int:
        from collections import deque
        import bisect
        
        n = len(s)
        zeros = s.count('0')
        
        if zeros == 0:
            return 0
        
        unvisited = [set(), set()]
        for i in range(n + 1):
            unvisited[i % 2].add(i)
        
        q = deque([(zeros, 0)])
        unvisited[zeros % 2].remove(zeros)
        
        while q:
            z, steps = q.popleft()
            
            if z == 0:
                return steps
            
            min_flip_zeros = max(0, k - (n - z))
            max_flip_zeros = min(k, z)
            
            min_next = z + k - 2 * max_flip_zeros
            max_next = z + k - 2 * min_flip_zeros
            
            parity = (z + k) % 2
            parity_set = unvisited[parity]
            
            to_remove = []
            for val in parity_set:
                if min_next <= val <= max_next:
                    q.append((val, steps + 1))
                    to_remove.append(val)
            
            for val in to_remove:
                parity_set.remove(val)
        
        return -1

public class Solution {
    public int MinOperations(string s, int k) {
        int n = s.Length;
        int zeros = 0;
        foreach (char c in s) {
            if (c == '0') zeros++;
        }
        
        if (zeros == 0) return 0;
        
        var unvisited = new SortedSet<int>[2];
        unvisited[0] = new SortedSet<int>();
        unvisited[1] = new SortedSet<int>();
        
        for (int i = 0; i <= n; i++) {
            unvisited[i % 2].Add(i);
        }
        
        var q = new Queue<(int z, int steps)>();
        q.Enqueue((zeros, 0));
        unvisited[zeros % 2].Remove(zeros);
        
        while (q.Count > 0) {
            var (z, steps) = q.Dequeue();
            
            if (z == 0) return steps;
            
            int minFlipZeros = Math.Max(0, k - (n - z));
            int maxFlipZeros = Math.Min(k, z);
            
            int minNext = z + k - 2 * maxFlipZeros;
            int maxNext = z + k - 2 * minFlipZeros;
            
            int parity = (z + k) % 2;
            var paritySet = unvisited[parity];
            
            var toRemove = new List<int>();
            foreach (int val in paritySet) {
                if (val >= minNext && val <= maxNext) {
                    q.Enqueue((val, steps + 1));
                    toRemove.Add(val);
                }
            }
            
            foreach (int val in toRemove) {
                paritySet.Remove(val);
            }
        }
        
        return -1;
    }
}

var minOperations = function(s, k) {
    const n = s.length;
    let zeros = 0;
    
    for (let i = 0; i < n; i++) {
        if (s[i] === '0') zeros++;
    }
    
    if (zeros === 0) return 0;
    if (k > n) return -1;
    
    let operations = 0;
    let arr = s.split('').map(c => c === '1' ? 1 : 0);
    
    while (true) {
        let zeroCount = 0;
        for (let i = 0; i < n; i++) {
            if (arr[i] === 0) zeroCount++;
        }
        
        if (zeroCount === 0) return operations;
        if (zeroCount < k) return -1;
        
        let indices = [];
        for (let i = 0; i < n && indices.length < k; i++) {
            if (arr[i] === 0) {
                indices.push(i);
            }
        }
        
        while (indices.length < k) {
            for (let i = 0; i < n && indices.length < k; i++) {
                if (arr[i] === 1 && !indices.includes(i)) {
                    indices.push(i);
                }
            }
        }
        
        for (let idx of indices) {
            arr[idx] = 1 - arr[idx];
        }
        
        operations++;
    }
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度大小
时间复杂度O(n log n)
空间复杂度O(n)

其中 n 是字符串的长度。时间复杂度主要来自于BFS遍历状态和有序集合的操作，空间复杂度主要用于存储状态和队列。