力扣995.K連續位的最小翻轉次數 —— 滑動平均

1、暴力逾時，從左到右一個一個看

class Solution {
public:
    int minKBitFlips(vector<int>& A, int K) {
        int n = A.size();
        int ans = 0;
        for(int i = 0; i < n; i++)//直接暴力從左到右周遊
        {
            if(A[i] != 1 && i < n)
            {
                ans++;
                for(int j = i; j < i+K; j++)
                {
                    if(j >= n)return -1;
                    A[j] = !A[j];
                }
                //i = i+K;
            }else{
                continue;
            }
        }
    return ans;
    }
};
           

2、滑動視窗的計算方法是：我一開始統計一個總的反轉次數resum，每當我視窗往前滑動的時候我就要把我前面的翻轉次數減掉

class Solution {
public:
    int minKBitFlips(vector<int>& A, int K) {
        int count = 0;
        int resum = 0;
        for(int i = 0; i < A.size(); i++)
        {
            if(i - K >= 0 && A[i - K] < 0)
            {
                resum--;
            }
            if(((resum&1)^A[i]) == 0)//判斷目前位置是不是0，翻轉奇數次還是偶數次，偶數0 A[i]=0就需要翻轉
            {
                if(i + K > A.size())return -1;
                A[i] = ~A[i];
                resum++;
                count++;
            }
        }
        return count;
    }
};