今天带来使二进制字符串全为 1 的最少操作次数，这道题还是比较复杂的。我采用的是数学方法，但这题也可以使用BFS来做。那么先介绍一下数学方法，代码如下：

class Solution {
public:
    int minOperations(string s, int k) {
        int n = s.length();
        int zeros = 0;
        for (char c : s) {
            if (c == '0')
                zeros++;
        }
        if (zeros == 0)
            return 0;
        int ones = n - zeros;

        // 如果 k 是偶数且 zeros 是奇数，则不可能
        if (k % 2 == 0 && zeros % 2 == 1)
            return -1;

        int min_t = (zeros + k - 1) / k; // 理论下界
        // 尝试从下界到 n（操作次数不会超过 n）
        for (int t = min_t; t <= n; ++t) {
            // 当 k 为奇数时，t 必须与 zeros 同奇偶
            if (k % 2 == 1 && (t % 2 != zeros % 2))
                continue;

            long long U = (1LL * t * k - zeros) / 2; // 需要的总“额外”次数
            long long capacity =
                1LL * zeros * ((t - 1) / 2) + 1LL * ones * (t / 2);
            if (U <= capacity) {
                return t;
            }
        }
        return -1;
    }
};

我们知道求操作次数，那么对于0和1的操作是不一样的。因为最终的结果得到的都是1，那么一个原本是0的数就要翻转奇数次，一个原本是1的数就要翻转偶数次。我们先遍历一下字符串得到0的次数，那么1的次数也就随之得到了。我们首先可以排除一种肯定不可能全为1的情况，如果每次选择的下标数k是偶数，那么总共的翻转次数t*k就是偶数，我们知道翻转次数等于1的翻转数加上0的翻转数。那么因为每个1要翻转偶数次，那么1的翻转数肯定是偶数。对于0来说，当0的个数是奇数时，因为0要翻转奇数次，那么最终的翻转数是奇数。一个奇数加一个偶数是奇数，就不等于总翻转次数了，所以这种情况肯定是不存在的。那么对于其他情况，我们可以知道总翻转次数肯定是大于等于0的个数的，因为0肯定是需要至少每个0都翻转一次，那么因为k是已知值，0的个数也是已知值，所以k*t>=zeros，t>=zeros/k，t得向上取整。比如一个4位2进制字符串1010，zeros=2，当k=3时，zeros/k=0.66，得向上取整为1才对。而这个次数的最大值也是有的，那就是字符串的长度，因为根据鸽巢原理，如果是n+1，那么总n个数，肯定有一个数至少被操作了两次，那么翻转两次等于没有翻，所以这个位置需要的翻转次数还是小于n的，就是可以合并的，所以最多n次。那么就开始遍历了，当k是奇数时，总操作次数的奇偶就取决于t和zeros的奇偶相不相同，如果不相同的话，两边奇偶性不同，这个t就肯定不行，直接到下一个。如果奇偶相同就开始判断，我们知道总操作次数减去0所翻转那一次再除2就是所需要的额外次数，因为并不改变最终的奇偶。那么对于0和1的最大额外次数就是因为0已经动了一次还可以被操作t-1次,因为需要是偶数次，所以再除2。对于1来说没有操作过，所以额外次数最多可以被操作t次，因为需要是偶数次，所以也除2。这样子我们就得到了可以操作的最多次数，那么当总操作次数小于等于可以被操作的最多次数时，我们就找到了一个分配方案。如果找不到就说明不存在。

再来介绍一个BFS的方法，这道题参考了灵茶山艾府的题解。先贴一下代码:

class Solution {
public:
    int minOperations(string s, int k) {
        int n = s.size();
        set<int> not_vis[2];
        for (int m = 0; m < 2; m++) {
            for (int i = m; i <= n; i += 2) {
                not_vis[m].insert(i);
            }
            not_vis[m].insert(n + 1); // 哨兵，下面无需判断 it != st.end()
        }

        int start = ranges::count(s, '0'); // 起点
        not_vis[start % 2].erase(start);
        vector<int> q = {start};
        for (int ans = 0; !q.empty(); ans++) {
            vector<int> nxt;
            for (int z : q) {
                if (z == 0) { // 没有 0，翻转完毕
                    return ans;
                }
                // not_vis[mn % 2] 中的从 mn 到 mx 都可以从 z 翻转到
                int mn = z + k - 2 * min(k, z);
                int mx = z + k - 2 * max(0, k - n + z);
                auto& st = not_vis[mn % 2];
                for (auto it = st.lower_bound(mn); *it <= mx; it = st.erase(it)) {
                    nxt.push_back(*it);
                }
            }
            q = move(nxt);
        }
        return -1;
    }
};

对于这道题来说，因为我们不关心0和1的位置，只关注0和1的翻转，假如现在是z个0，n-z个1，那么经过k次翻转其中对x个0和k-x个1进行翻转，就变成，z-x+k-x个0，n-z+x-k+x个1，就可以求出新的0的个数。那么我们可以把这道题变成图论问题，每个0的个数都是1个城市，我们要从z开始到0，每次操作就是到下一个城市，一条最短路径就是最小的操作次数。这样就可以使用BFS求最短路径，先创建两个集合存储0和1的访问状态，初始把所有可能的0都加入到集合中，也就是所有城市。然后数一下初始字符串有多少个0，这就是起点，把它删掉，标记为访问。然后就开始进入遍历，首先是起点，起点经过翻转，能到的城市有一个范围，把这范围里的城市都加入到下一层，另外因为0和1之分，所以遍历时只遍历对应的集合，并且在访问后用迭代器删除，然后到下一层再用这些城市进行翻转，再去到能到的城市。ans表示了总共的操作次数，如果在q里遍历到0，那么就说明找到了。如果到最后都没有，那么就是不行。另外提一下，move可以直接把nxt数组里的东西移到q里，并丢弃q原本的东西，在本题用作当前层和下一层之间的连接。

这道题总体来说还是一道比较有趣的题，无论是数学上的思考，还是在运用BFS上的抽象思考。