LeetCode/Java/995.java at master · strengthen/LeetCode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
__________________________________________________________________________________________________
sample 4 ms submission
class Solution {
    public int minKBitFlips(int[] A, int K){
        int N = A.length;
        int[] hint = new int[N];
        int ans = 0, flip = 0;

        for (int i = 0; i < N; i++){
            flip ^= hint[i];
            if (A[i] == flip){
                ans++;
                if (i + K > N) return -1;
                flip ^= 1;
                if (i + K < N) hint[i + K] ^= 1;
            }
        }
        return ans;
    }
}
__________________________________________________________________________________________________
sample 45472 kb submission
class Solution {
    public int minKBitFlips(int[] A, int K) {
        int N = A.length;
        int[] hint = new int[N];
        int ans = 0, flip = 0;

        // When we flip a subarray like A[i], A[i+1], ..., A[i+K-1]
        // we can instead flip our current writing state, and put a hint at
        // position i+K to flip back our writing state.
        for (int i = 0; i < N; ++i) {
            flip ^= hint[i];
            if (A[i] == flip) {  // If we must flip the subarray starting here...
                ans++;  // We're flipping the subarray from A[i] to A[i+K-1]
                if (i + K > N) return -1;  //If we can't flip the entire subarray, its impossible
                flip ^= 1;
                if (i + K < N) hint[i + K] ^= 1;
            }
        }

        return ans;
    }
}
__________________________________________________________________________________________________