https://leetcode.com/problems/minimum-number-of-k-consecutive-bit-flips/
https://leetcode.com/problems/minimum-number-of-k-consecutive-bit-flips/discuss/239284/C%2B%2B-greedy-stack-and-O(1)-memory
The time complexity of this solution is O(n * K), where n is the length of
https://leetcode.com/problems/minimum-number-of-k-consecutive-bit-flips/discuss/238557/Java-clean-O(n*k)-greedy-solution
https://leetcode.com/problems/minimum-number-of-k-consecutive-bit-flips/discuss/238609/JavaC%2B%2BPython-One-Pass-and-O(1)-Space
https://leetcode.com/articles/minimum-number-of-k-consecutive-bit-flips/
X. https://www.acwing.com/solution/LeetCode/content/1033/
(贪心，差分思想) O(n)O(n)
显然我们需要一个策略来翻转数组。
这里不加证明地给出最优的策略，考虑从数组开头开始检查，如果遇到了 0，则累计答案并翻转当前位置及当前位置之后的 K 个元素，使得当前位置变为 1，然后继续检查下一个位置。如果遇到了 1 则不进行任何操作。如果在最后不足 K 个位置的时候遇到了 0，则返回 -1。
但这样操作时间复杂度是 O(nK)O(nK) 的，需要进行优化。我们发现，每个位置的状态和操作次数的奇偶有关系，而每次我们又是操作连续的位置，则考虑差分的思想。
额外建立一个数组 B，初始值都为 0，额外维护一个当前的和 cur。如果 cur + A[i] + B[i] 为 0，则需要进行翻转，则累计答案的同时， cur = cur + 1 + B[i]，且 B[i + K] = -1；否则，只需要 cur = cur + B[i]。
时间复杂度
优化后的策略每个位置仅进行常数时间的操作，故时间复杂度为 O(n)O(n)。
空间复杂度
由于使用了额外数组，空间复杂度为 O(n)O(n)。
C++ 代码
class Solution {
public:
int minKBitFlips(vector<int>& A, int K) {
int n = A.size();
int cur = 0, ans = 0;
vector<int> B(n, 0);
for (int i = 0; i < n; i++)
if ((A[i] + B[i] + cur) % 2 == 0) {
ans++;
if (i + K < n)
B[i + K] = -1;
else if (i + K > n)
return -1;
cur += B[i] + 1;
}
else {
cur += B[i];
}
return ans;
}
X. Proof
https://leetcode.com/problems/minimum-number-of-k-consecutive-bit-flips/discuss/238683/Proof%3A-Why-greedy-works
https://buptwc.com/2019/02/25/Leetcode-995-Minimum-Number-of-K-Consecutive-Bit-Flips/
In an array
A containing only 0s and 1s, a K-bit flip consists of choosing a (contiguous) subarray of length K and simultaneously changing every 0 in the subarray to 1, and every 1 in the subarray to 0.
Return the minimum number of
K-bit flips required so that there is no 0 in the array. If it is not possible, return -1.
Example 1:
Input: A = [0,1,0], K = 1 Output: 2 Explanation: Flip A[0], then flip A[2].
Example 2:
Input: A = [1,1,0], K = 2 Output: -1 Explanation: No matter how we flip subarrays of size 2, we can't make the array become [1,1,1].
Example 3:
Input: A = [0,0,0,1,0,1,1,0], K = 3 Output: 3 Explanation: Flip A[0],A[1],A[2]: A becomes [1,1,1,1,0,1,1,0] Flip A[4],A[5],A[6]: A becomes [1,1,1,1,1,0,0,0] Flip A[5],A[6],A[7]: A becomes [1,1,1,1,1,1,1,1]
Note:
1 <= A.length <= 300001 <= K <= A.length
Formation and proof of greedy algorithm: Intuitively, we know if A[0] is 0, then we must flip from the left side since there is only this way to flip A[0]. So the following greedy algorithm may be the right algorithm here. But we must prove it is the correct algorithm.
Greedy Algorithm: from left to right, after considering the previous flips, if A[i] is 0, flip subarray A[i] to A[i + K - 1]. Otherwise don't flip. If A[i] needs to be flipped but the remaining subarray does not have K elements to operate flip on (A.length - i < K), return -1.
Proof of correctness: The above algorithm gives a solution S by greedily flipping 0s from left to right, considering previous flips. We claim to if A[i] is already 1, then we never flip it, else always flip subarray starting from A[i]. Now we'll prove the following solutions does not yield a solution that is better than S.
1. Without loss of generosity, let the i-th bit be the first 0. There is a solution S' that does a flip at A[j], j < i. Since A[j] == 1, a flip will set A[j] to 0. Eventually A[j] must be flipped back to 1, and this can only happen for flips whose start index is in [j - K + 1, j] range. Obviously we can eliminate start index j as that is doing the same flip starting from A[j] twice, essentially wasting 2 flips and achieving nothing. So we know in order to flip A[j] back to 1, a flip that starts at a smaller index j must occur. Because all the bits that come ahead index j are also 1s, we can induct the same reasoning: to flip back a bit that was originally 1, we can only resort to another flip that starts at an smaller index until we reach A[0]. At this point, we can only flip at A[0], wasting 2 flips and achieves nothing. So this proves that from left to right, skipping 1s is always better than flipping 1s.
2. Assume we don't start from left to right, but at some middle index i.
2a. A[i] == 1, based on the case 1 argument, we know skipping A[i] is better.
2b. A[i] == 0. There are two possible cases. 1. If there is no 0s to the left of A[i], then this is the greedy algorithm we formed. 2. If there are 0s to the left of A[i], let j be the index of the first 0 from A[0...i - 1]. Again by case 1 argument, we know that we simply flip A[j]. The same argument applies to rest of 0s in A[0.... i - 1]. As a result, we know starting in the middle does not yield a better result that starting from left.
public int minKBitFlips(int[] A, int K) { int count = 0; for(int i = 0; i < A.length; i++) { if(A[i] == 0 && i + K <= A.length) { for(int j = 0; j < K; j++) { A[i + j] = A[i + j] == 0 ? 1 : 0; } count++; } else if(A[i] == 0) { return -1; } } return count; }
Just want to share my thought process; I am sure that there is a formal proof somewhere.
- Since K is fixed, it does not make sense to do the flip for any given index more than once. It's a XOR operation, even flips will be equal to zero flips, odd flips will be equal to one flip. So, there could be up to
n - Kflips. - Since it's a XOR operation, we can do flips in any order.
- Say we start do flips left to right. That means that, when we encounter zero, we have no choice but flip.
At this point, this intuition is sound enough to try a greedy approach.
Naïve Greedy Solution
Go through the array and flip K elements when encounter zero. Return
-1 if you cannot do K flips.int minKBitFlips(vector<int>& A, int K, int res = 0) {
for (auto i = 0; i < A.size(); ++i) {
if (A[i] != 1) {
if (i + K - 1 >= A.size()) return -1;
for (auto j = i; j < i + K; ++j) A[j] = !A[j];
++res;
}
}
return res;
}
The time complexity of this solution is O(n * K), where n is the length of A. This solution is not accepted by the online judge.
https://leetcode.com/problems/minimum-number-of-k-consecutive-bit-flips/discuss/238557/Java-clean-O(n*k)-greedy-solution private void flip(int[]A,int K,int i){
for(int j=i;j<i+K;j++){
A[j]=1-A[j];
}
}
public int minKBitFlips(int[] A, int K) {
int cnt=0;
for(int i=0;i<A.length;i++){
if(A[i]==0){
if(i+K>A.length)return -1;
flip(A,K,i);
cnt++;
}
}
return cnt;
}
The bottleneck of the naive solution is that it does not use the previous flip information. For a given index i, whether there needs to be a flip starting from A[i] or not depends the original A[i] value and the impacts of possible flips starting from index [i - K + 1, i - 1]. Flips that occur at index smaller than i - K + 1 do not have any impact on A[i]'s flip decision. To save/update the previous K indices's flip events, we need a sliding window of size K.
1. Use an ArrayDeque of size K to keep the indices of bits that are flipped and a count variable currentEffectiveFlips to keep the flips that occur previously that are also still effective on the current bit A[i].
2. If the earliest flip event saved in the deque is no longer effective, remove it and decrement currentEffectiveFlips by 1.
3. At this point, we have A[i]'s value and the effective previous flip counts, we do the following:
3a. If A[i] has been flipped even number times and A[i] is originally 0, we know A[i] is still 0 so flip it.
3b. or if A[i] has been flipped odd number times and A[i] is originally 1, we know A[i] has been flipped to 0 so flip it.
public int minKBitFlips(int[] A, int K) { int totalFlips = 0, currentEffectiveFlips = 0; Deque<Integer> flipIndices = new ArrayDeque<>(); for(int i = 0; i < A.length; i++) { if(flipIndices.size() > 0 && flipIndices.peekFirst() + K == i) { flipIndices.remove(); currentEffectiveFlips--; } if(A[i] == 0 && currentEffectiveFlips % 2 == 0 || A[i] == 1 && currentEffectiveFlips % 2 != 0) { if(i + K > A.length) { return -1; } flipIndices.addLast(i); currentEffectiveFlips++; totalFlips++; } } return totalFlips; }
Since we are doing XOR operation, even flips will be equal to zero flips, odd flips will be equal to one flip. So, instead of modifying K bits every time we encounter zero, we can just track the current number of flips.
Linear Solution
Here, we are using a queue to track flips. When we 'flip', we put the end index of our flip (
i + K - 1) into our queue. The size of the queue will indicate number of flips; we also remove past 'flips' from our queue.int minKBitFlips(vector<int>& A, int K, int res = 0) {
queue<int> flips;
for (auto i = 0; i < A.size(); ++i) {
if (A[i] != (flips.size() % 2 ? 0 : 1)) {
++res;
flips.push(i + K - 1);
}
if (!flips.empty() && flips.front() <= i) flips.pop();
}
return flips.empty() ? res : -1;
}
Complexity Analysis
The time complexity of this solution is O(n), and the memory complexity is O(K).
Constant Memory Solution
Instead of using the queue, we can track the total number of flips, and use the source array to mark flips with negative values.
Note that we restore original values after the processing, so the source array is not changed.
int minKBitFlips(vector<int>& A, int K, int res = 0, int flips = 0) {
for (auto i = 0; i < A.size(); ++i) {
if (A[i] == flips % 2) {
if (i > A.size() - K) return -1;
++res, ++flips, A[i] -= 2;
}
if (i >= K - 1 && A[i - K + 1] < 0) --flips, A[i - K + 1] += 2;
}
return res;
}- 最naive的想法是暴力bfs，扫描所有的操作， 然后看是否走到最终状态或者重复状态， 结果当然是超时
- 然后试图用动态规划做， 试图对中间操作， 然后把数组分成两边， 然后对两边分别做， 最后求出最小值， 这个也只写了bug
中间也试图想能否先得到最右边都是1或者最右边都是0的状态， - 结果最后看别人的答案， 居然是直接一次遍历做贪心！！！ 又受到一万点暴击！
- 贪心代码非常简洁，就是从左向右遍历， 遇到0就做flip，然后一直到数组结尾就好了！！！
- 这里，重点是为什么贪心是对的？
我们有如下思路：
a. 对于任何一个位置，要么不flip, 要么flip一次， 因为flip两次是没有意义的
b. 从左向右遍历，如果左边第一个是1， 那么，因为我们要么不flip，要么flip一次， 所以，对于最左边的1， 一定是不需要flip的
c. 如果左边第一个是0， 那么，我们一定是需要在这个位置flip一次， 因为没有其他选择可以让这个数变成1
d. 现在我们已经对第一个元素做了最佳处理，然后我们考虑第二个元素，同样的推理过程也是适用的，如果是1就不处理，如果是0就flip，
e. 这里，正确性的关键在于， 每个步骤，一定是属于最佳答案的一部分， 并且，前面的处理完了以后，后面无论怎么样处理，
都不会影响到前面的处理结果和状态， 所以，这个过程一定是正确的。 - 还有一个问题是， 如何分析到贪心？ （比如我就没有分析出来）
这个题目除了暴力的思路， 尝试了尾部dp的思路（试图寻找dp[i]和dp[j]的关系)，尝试了中间的dp（中间处理，然后对两边单独做处理),
尝试了试图把尾部全部变成1或者0（这里其实有点接近了， 因为从左往右做的过程效果就是把0都放到最右边）， 也尝试了小规模数据，
都没有分析到贪心的思路。
https://leetcode.com/problems/minimum-number-of-k-consecutive-bit-flips/discuss/238609/JavaC%2B%2BPython-One-Pass-and-O(1)-Space
There is only one way to filp
and
So we start from the leftmost one by one using a greedy idea to solve this problem.
A[0],and
A[0] will tell us if we need to filp the range A[0] ~ A[K -1].So we start from the leftmost one by one using a greedy idea to solve this problem.
Solution 1
Explanation
Create a new array
Create a new array
isFlipped[n].isFlipped[i] = 1 iff we flip K consecutive bits starting at A[i].
We maintain a variable
flipped and flipped = 1 iff the current bit is flipped.
If
If
flipped = 0 and A[i] = 0, we need to flip at A[i].If
flipped = 1 and A[i] = 1, we need to flip at A[i].
Complexity
O(N) time for one passO(N) extra space for isFlipped[n]. public int minKBitFlips(int[] A, int K) {
int n = A.length, flipped = 0, res = 0;
int[] isFlipped = new int[n];
for (int i = 0; i < A.length; ++i) {
if (i >= K)
flipped ^= isFlipped[i - K];
if (flipped == A[i]) {
if (i + K > A.length)
return -1;
isFlipped[i] = 1;
flipped ^= 1;
res++;
}
}
return res;
}
Solution 2
ExplanationInstead an array isFlipped of size n,use a deque to maintain the state of a sliding window of size k.
Complexity
O(N) time for one pass
O(K) extra space for isFlipped[n].
Solution 3
Explanation:
One pass, count the cur filp numbers in a sliding window of size K.
If cur is even and A[i] is 0, we need to flip.
If cur is odd and A[i] is 1, we need to flip.
Complexity:
O(N) time for one pass
O(1) extra space.
public int minKBitFlips(int[] A, int K) {
int cur = 0, res = 0;
for (int i = 0; i < A.length; ++i) {
if (i >= K) cur -= A[i - K] / 2;
if ((cur & 1 ^ A[i]) == 0) {
if (i + K > A.length) return -1;
A[i] += 2;
cur++;
res++;
}
}
return res;
}https://leetcode.com/articles/minimum-number-of-k-consecutive-bit-flips/
If the leftmost element is a 0, we must flip the subarray starting at index 0. Similarly, if the leftmost element is a 1, we should not flip the subarray starting at index 0. This proves we can proceed in a greedy manner: after finding out whether we have to flip the first subarray (positions 0 to K-1) or not, we can consider the array with the first element (value 1) removed, and repeat this process.
We can do better. Every time we flip a subarray
A[i], A[i+1], ..., A[i+K-1], we can consider this as two "events", one 'opening event' at position i that marks the start of the subarray, and one 'closing event' at position i+K that marks the end of the subarray. Using these events, we always know how many overlapping flipped subarrays there are: its simply the number of opening events minus the number of closing events.
Algorithm
When we flip a subarray, let's call the set of indices we flipped an interval. We'll keep track of
flip, the number of overlapping intervals in our current position. We only care about the value of flip modulo 2.
When we flip an interval starting at
i, we create a hint for a closing event at i+K telling us to flip our writing state back.
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;
}
X. https://www.acwing.com/solution/LeetCode/content/1033/
(贪心，差分思想) O(n)O(n)
显然我们需要一个策略来翻转数组。
这里不加证明地给出最优的策略，考虑从数组开头开始检查，如果遇到了 0，则累计答案并翻转当前位置及当前位置之后的 K 个元素，使得当前位置变为 1，然后继续检查下一个位置。如果遇到了 1 则不进行任何操作。如果在最后不足 K 个位置的时候遇到了 0，则返回 -1。
但这样操作时间复杂度是 O(nK)O(nK) 的，需要进行优化。我们发现，每个位置的状态和操作次数的奇偶有关系，而每次我们又是操作连续的位置，则考虑差分的思想。
额外建立一个数组 B，初始值都为 0，额外维护一个当前的和 cur。如果 cur + A[i] + B[i] 为 0，则需要进行翻转，则累计答案的同时， cur = cur + 1 + B[i]，且 B[i + K] = -1；否则，只需要 cur = cur + B[i]。
时间复杂度
优化后的策略每个位置仅进行常数时间的操作，故时间复杂度为 O(n)O(n)。
空间复杂度
由于使用了额外数组，空间复杂度为 O(n)O(n)。
C++ 代码
class Solution {
public:
int minKBitFlips(vector<int>& A, int K) {
int n = A.size();
int cur = 0, ans = 0;
vector<int> B(n, 0);
for (int i = 0; i < n; i++)
if ((A[i] + B[i] + cur) % 2 == 0) {
ans++;
if (i + K < n)
B[i + K] = -1;
else if (i + K > n)
return -1;
cur += B[i] + 1;
}
else {
cur += B[i];
}
return ans;
}
X. Proof
https://leetcode.com/problems/minimum-number-of-k-consecutive-bit-flips/discuss/238683/Proof%3A-Why-greedy-works
- before and after any flip, any bit in the sequence of 1 starting from the left-most bit should not be flipped anymore.
Proof by contradiction:
The greedy claim gives a solution
-- So the greedy claim above is NOT false.
So, the greedy claim is true.
S. Without loss of generosity, let the i-th bit be the first 0 bit. Suppose the greedy claim above is false, then there must be a better (better means less flips) solution S' in which bits in range [J , J + K - 1] are flipped and J < i. There could be multiple J. Let j be the smallest possible J. Since A[j] now is 1 (why? because j<i), if we flip it, A[j] becomes 0. A[j] finally should be 1, so S' must flips A[j] again sometime later. As j is the smallest of J, S' can't flip anything left to A[j], which means only flipping the range [j , j + K - 1] can flip A[j] back to 1. See? we flipped [j , j + K - 1], then again [j , j + K - 1]. S' wasts flips. If S' exists, we can find a third solution S'' that is strictly even better than S'. And we can do this induction infinitely and find a solution needs only 0 or even negative number of flips. -- That is of course impossible. Actually, the induction of finding even better solutions will eventually give you S. S is strictly better than S? Of course not!-- So the greedy claim above is NOT false.
So, the greedy claim is true.
OK...I know I shouldn't flip the left-most 1s. What should I flip next?
So everything left to the i-th bit should not be flipped. But
A[i] now is 0. S will flip it to 1 sometime. Since from then on S can't flip anything left to A[i], it must flip A[i...i + K - 1] to flip A[i]https://buptwc.com/2019/02/25/Leetcode-995-Minimum-Number-of-K-Consecutive-Bit-Flips/
我们想一想，对于数组中最左边的0（不妨定义下标为i），我们如果想将其翻转为1的话，那么这k个翻转数该选哪个作为起点呢。如果以某个下标j(j < i)进行翻转，那么又会在更左边产生0，这样下去会一直到左边界，这显然是不合理的。我们应当就以i为起点来进行翻转。
这也就是贪心的思想！
这也就是贪心的思想！
从左至右进行遍历，每遍历到0就进行一次翻转，但是考虑到后面k个数也会进行翻转，我们如何对其进行记录呢
这里使用一个列表，将每次翻转所影响到的最右下标记录。对于当前判断的位置来说，使用二分法找到其到底被多少次翻转所影响，然后计算即可。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | def minKBitFlips(self, A, K): res = 0 s = [] for i in range(len(A)): index = bisect.bisect_right(s, i) # if influenced, flip it and then judge if (len(s) - index) % 2 == 1: A[i] = 1 - A[i] # only consider it when A[i] == 0 if A[i] == 1: continue if len(A)-i < K: return -1 res += 1 s.append(i + K) return res |
