题面

LeetCode 995. K 连续位的最小翻转次数

给定一个二进制数组 nums 和一个整数 k 。

k位翻转 就是从 nums 中选择一个长度为 k 的 子数组 ，同时把子数组中的每一个 0 都改成 1 ，把子数组中的每一个 1 都改成 0 。

返回数组中不存在 0 所需的最小 k位翻转 次数。如果不可能，则返回 -1 。

子数组 是数组的连续部分。

示例 1：

1
2
3

输入：nums = [0,1,0], K = 1
输出：2
解释：先翻转 A[0]，然后翻转 A[2]。

示例 2：

1
2
3

输入：nums = [1,1,0], K = 2
输出：-1
解释：无论我们怎样翻转大小为 2 的子数组，我们都不能使数组变为 [1,1,1]。

示例 3：

输入：nums = [0,0,0,1,0,1,1,0], K = 3
输出：3
解释：
翻转 A[0],A[1],A[2]: A变成 [1,1,1,1,0,1,1,0]
翻转 A[4],A[5],A[6]: A变成 [1,1,1,1,1,0,0,0]
翻转 A[5],A[6],A[7]: A变成 [1,1,1,1,1,1,1,1]

题解

差分数组

当我隐约感觉某道题或许可以用差分做的时候，那道题往往用不了差分；当我想破脑袋都想不到可以用差分做时，差分就来了。

策略就是当遇到0时进行翻转，否则不翻转。一开始根据这个策略做，暴力模拟，经典超时。后来看了题解才会做。我们可以用差分数组来维护某个位置被翻转的次数，结合这个位置的初始状态，就可以快速得到这个位置目前的状态。

代码：

class Solution {
public:
    int minKBitFlips(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> diff(n + 1, 0);
        int res = 0;
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            cnt += diff[i];
            if ((nums[i] + cnt) % 2 == 0) {
                if (i + k > n) return -1;
                res++;
                cnt++;
                diff[i + k]--;
            }
        }
        return res;
    }
};

滑动窗口

当然，差分数组也不是必要的，可以维护一个滑动窗口来将空间复杂度降为O(1)。

思路就是用一个队列维护对当前仍有影响的取了反的位置，这样队列的长度就反映了当前位置反转的次数了。

class Solution {
public:
    int minKBitFlips(vector<int>& nums, int k) {
        queue<int> q;
        int res = 0;
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            if (!q.empty() && q.front() + k == i) q.pop();
            if (q.size() % 2 == nums[i]) {
                if (i + k > n) return -1;
                q.push(i);
                res++;
            }
        }
        return res;
    }
};

有的没的

曙光

从十一开始就没有闲下来过。国庆过完紧跟着信息政策的pre，然后是毛概，还有计网的实验报告，还有信息检索。后面还要计网写Web Server，还（算是）接过了98勋章系统的活（虽然还啥都不会，得从零开始学）。不过还好都熬过来了，这个周末忙完大概就可以稍微闲一阵子了。微博好友圈里看到的同学们都好用功，怎么每天都能学到凌晨才回寝室的，为什么会有这么多事情要做，合着她们学校不把同学当人似的。或许只是单纯是她们比较有追求，不是我这种咸鱼能理解的。

gtmdzyh

章燕华查老师2.2分属于是给高了，嘴碎屁事多也就算了，饭点拖课是真的不能忍，等结课了一定要给她刷1分。这门课爷反正摆了，爱给几分给几分，还能把爷挂了不成。不过话说回来，刷低分也没啥用，专业必修课也没得选。晦气晦气。

日期	2022年10月13日
是否独立完成	否
涉及算法	差分数组、滑动窗口

环己三烯的冬眠舱

每日Hard - Day 11

Tags

题面