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

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

• 因为翻转顺序改变不影响最终结果

  • 因此从头找每个位置翻转后的结果
  • 如果为0 将从它开始的K长的数组翻转

•   class Solution {
    public:
        int minKBitFlips(vector<int>& nums, int k) {
            int n = nums.size();
            vector<int> s(n+1);
            int res=0,cnt=0;
            for(int i=0;i<n;i++)
            {
                cnt += s[i];  // 差分记录每个位置的翻转次数
                if((nums[i] + cnt) % 2 == 0)  //需要翻转
                {
                    if(i + k > n) return -1;  //i + k - 1 == n时不足k位
                    res ++;
                    cnt ++;  //相当于s[i] ++;
                    s[i+k] --;  //s[i+k-1+1] --;
                }
            }
            return res;
        }
    };