③ 我们可以在一开始创建队列的时候就可以把队列里面的数据类型设置为一个对象，利用对象可以封装对应的属性的特点，往对象中增加时间这个属性这样我们就可以在一创建这个对象的时候就把入队的时间进行记录下来，这里可以使用设置一个全局变量来进行时间的记录，然后再创建对象的时候这个全局变量的值加一然后赋值给这个对象中的时间属性，注意这里的类是私有的内部类，而且必须声明成static
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 = 1Output: 2Explanation: Flip A[0], then flip A[2].
Example 2:
Input: A = [1,1,0], K = 2Output: -1Explanation: 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 = 3Output: 3Explanation:
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]
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.
publicint 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++;
}
elseif(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 - K flips.
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 isO(n * K), wherenis the length ofA. This solution is not accepted by the online judge.
privatevoid flip(int[]A,int K,int i){
for(int j=i;j<i+K;j++){
A[j]=1-A[j];
}
}
publicint 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;
}
X.
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.
publicint 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;
}
这里，重点是为什么贪心是对的？ 我们有如下思路： a. 对于任何一个位置，要么不flip, 要么flip一次， 因为flip两次是没有意义的 b. 从左向右遍历，如果左边第一个是1， 那么，因为我们要么不flip，要么flip一次， 所以，对于最左边的1， 一定是不需要flip的 c. 如果左边第一个是0， 那么，我们一定是需要在这个位置flip一次， 因为没有其他选择可以让这个数变成1 d. 现在我们已经对第一个元素做了最佳处理，然后我们考虑第二个元素，同样的推理过程也是适用的，如果是1就不处理，如果是0就flip， e. 这里，正确性的关键在于， 每个步骤，一定是属于最佳答案的一部分， 并且，前面的处理完了以后，后面无论怎么样处理， 都不会影响到前面的处理结果和状态， 所以，这个过程一定是正确的。
There is only one way to filp 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 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 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 pass O(N) extra space for isFlipped[n].
publicint 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
Explanation Instead 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.
publicint 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;
}
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.
publicint minKBitFlips(int[] A, intK) {
intN = A.length;
int[] hint = newint[N];
intans = 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 (inti = 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;
}
}
returnans;
}
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;
}
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 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]
defminKBitFlips(self, A, K): res = 0 s = []for i in range(len(A)): index = bisect.bisect_right(s, i)# if influenced, flip it and then judgeif (len(s) - index) % 2 == 1: A[i] = 1 - A[i]# only consider it when A[i] == 0if A[i] == 1: continueif len(A)-i < K: return-1 res += 1 s.append(i + K)return res
