[leetcode daily question 2021/2/18] [detailed explanation] minimum number of turns of 995. K continuous bits

The title comes from leetcode, Solutions and ideas represent only personal views . Portal .
difficulty ： difficult
Time ：2h-

subject

In contains only 0 and 1 Array of A in , once K Bit flipping involves selecting a length of K Of （ continuity ） Subarray , At the same time, add each of the subarrays 0 Change to 1, And each 1 Change to 0.

Return to required K The minimum number of bit flipping , So that the array has no value of 0 The elements of . If not , return -1.

Example 1：

 Input ：A = [0,1,0], K = 1
 Output ：2
 explain ： Turn it over first  A[0], Then flip  A[2].

Example 2：

 Input ：A = [1,1,0], K = 2
 Output ：-1
 explain ： No matter how we flip it, the size is  2  Subarray , We can't make arrays become  [1,1,1].

Example 3：

 Input ：A = [0,0,0,1,0,1,1,0], K = 3
 Output ：3
 explain ：
 Flip  A[0],A[1],A[2]: A become  [1,1,1,1,0,1,1,0]
 Flip  A[4],A[5],A[6]: A become  [1,1,1,1,1,0,0,0]
 Flip  A[5],A[6],A[7]: A become  [1,1,1,1,1,1,1,1]

Tips ：

1 <= A.length <= 30000
1 <= K <= A.length

Ideas & Code

Greedy reversal

It's kind of greedy The smell of .

Think about this case

[1,1,1,0,x,x,x,...]
3

To minimize the number of flips , In fact, we only need It's enough to flip

[1,1,1,1,0,x,x,x,...]
         ↑   ↑
       left right

left Pointer to 0,left To the left of the pointer are all 1, It must be Flip left The section to the right of the pointer , To minimize the total number of flips .

Why? ？ Think of counter examples ,

[1,1,1,1,0,x,x,x,...]   =>   [1,1,0,0,1,x,x,x,...]  =>  [0,0,1,0,1,x,x,x,...] 
     ↑   ↑                    ↑   ↑
   right left              right  left

If you flip left The paragraph to the right of the pointer , It will make There is no need to flip , This flip causes Scramble the previously flipped array .

---

hypothesis A[0~left)=1, Then just consider A[left,n) Length array , It is equivalent to that the input scale has decreased .

So every time we Greedily choice The first one from left to right 0 Flip . Make sure left The elements to the left of the pointer are all 1, When left Pointer to n When , We have flipped all the elements .

Specially , because One flip , Need to flip [left,left+K) The element of length . If a flip left+K > n, Then this flip failed , The entire array cannot be flipped to 1,return -1.

class Solution {
    
public:
    void flip(vector<int>& A,int left,int right){
    
        for(int i=left;i<=right;i++){
    
            if(A[i] == 0){
    
                A[i] = 1;
            }else{
    
                A[i] = 0;
            }
        }
    }
    int minKBitFlips(vector<int>& A, int K) {
    
        int left = 0;
        int right = left + K -1;
        // The length of the array 
        int n = A.size();
        int ans = 0;
        /* *  Find the first one for 0 The location of , reverse k position , Sure enough, it's time-out  *  The time complexity is O(nk), The space complexity is O(1) */
        for(int i=0;i<n;i++){
    
            if(A[i] == 1){
    
                continue;
            }
            if(i+K-1 >= n){
    
                return -1;
            }
            flip(A,i,i+K-1);
            ans++;
        }
        return ans;
    }
};

Time complexity ： O(nK).n Is array length .K Is the length of one flip .
Spatial complexity ： O(1).

Submit , It's overtime . Obviously ,leetcode Difficult questions have never been given so easily .

---

Flip optimization

Optimization ideas

Optimize it .
There are two ways to optimize timeout .

1. Follow the train of thought just now , Look at Time complexity Continue to optimize .
2. Change your mind and do it again .

I think the one just now greedy It's a good idea , So I plan to continue to optimize .

---

Consideration of time complexity

First observe Time complexity ：O(nk), near n², In fact, it's not very slow , If If you continue, you will O(nlogn) and O(n), Because you must traverse all the elements in the array , The time complexity cannot be less than O(n).

consider O(nlogn), Familiar algorithms have two points , Sort, etc .
here Sorting is useless , Two points It doesn't work .

consider O(n), Then we You can only traverse the array once .

I think the probability here is O(n) The algorithm of , So go on thinking .

---

Space for time

Generally speaking , Want less time complexity , Then trade space for time . and , The algorithm that just timed out , The space complexity is O(1), It is very likely that the direction of space for time optimization .

Consider specifically

The above considerations , Only one General direction , Want to do it , Still need Specific analysis of specific problems .

Where is the slow Algorithm ？
We always find the first one 0, The element A[left] It's going to flip [left,left+K) Interval of length , But actually , Flipping an array does not require execution , We just need to flip the target we need to find that will do . namely , This time 0, Next time find 1, Next time find 0.

---

The following example It has been flipped twice . First flip [left,right], The second flip [next_left,next_right].

K=4, right = left+K-1
     next_left next_right        next_left next_right         next_left next_right
           ↓     ↓                     ↓     ↓                      ↓     ↓
[...,1,0,0,1,1,1,1,...]  => [...,1,1,1,0,0,1,1,...]  =   [...,1,1,1,1,1,0,0,...]
       ↑     ↑                     ↑     ↑                      ↑     ↑
      left  right                left  right                  left  right

In this example , How to find the target ？

1. Find the first 0, Flip
2. stay [left,right] Between looking for 1, stay (right,n) Between looking for 0, Flip
3. stay [next_left,right] Between looking for 0, stay (right,next_right] Between looking for 1, stay (next_right,n) Between looking for 0, Flip

After analyzing the above example , You can find , Every time the target we are looking for flips , It's all at the dividing line of the last turnover .

---

such , We can define an array of flipped boundaries flipFlag, Record every flip right Demarcation line . Every time the traversal pointer reaches the dividing line , We will flip the target we are looking for .

class Solution {
    
public:
    int minKBitFlips(vector<int>& A, int K) {
    
        int left = 0;
        int right = left + K -1;
        // The length of the array 
        int n = A.size();
        int ans = 0;
        /* *  Virtual inversion , Space for time  *  Use tag array , After the pointer touches the tag array , Find the number flag, Flip  *  The time complexity is O(n), The space complexity is O(n) */
        //0 Means not to flip ,1 It means flip 
        vector<int> flipFlags(n,0);
        // The next number to look for 
        int flag = 1;
        for(int i=0;i<n;i++){
    
            if(flipFlags[i] == 1){
    
                // Flip flag
                flag = flag==0?1:0;
            }
            // Skip useless 
            if(A[i]==flag){
    
                continue;
            }
            // Right border 
            right = i + K;
            // If the current section needs to be flipped   Greater than   Array   Explain that you must not complete the flip 
            if(right > n){
    
                return -1;
            }
            // Flip once 
            flag = flag==0?1:0;
            // Record the number of turns 
            ans++;
            // Use if To prevent cross-border , because right Yes, we can n Of 
            if(right < n){
    
                // Mark next flag Where you need to flip 
                flipFlags[right] = 1;
            }
        }
        return ans;
    }
};

Time complexity ： O(n),n Is the size of the array .
Spatial complexity ： O(n),n Is the size of the array .

---

Space optimization

In fact, the time complexity reaches O(n), It's almost there , I will not continue to optimize .
After reading the official explanation , The space complexity can also be optimized to O(1).

---

Because we A Number of stored , Only 0 and 1, We can modify it in place A Array , Express with other values 【 The dividing line of target turnover 】, Instead of flipFlag Use of arrays .

class Solution {
    
public:
    int minKBitFlips(vector<int>& A, int K) {
    
        int left = 0;
        int right = left + K -1;
        // The length of the array 
        int n = A.size();
        int ans = 0;
		/* *  Refer to the official answer , Optimize space to O(1) */
        for(int i=0;i<n;i++){
    
//---------------------------------------------
            if(A[i] == 2 || A[i] == 3){
    
                // Restore flag
                A[i] -= 2;
//----------------------------------------------
                // Flip flag
                flag ^= 1;
            }
            // Skip useless 
            if(A[i]==flag){
    
                continue;
            }
            // Right border 
            right = i + K;
            // If the current section needs to be flipped   Greater than   Array   Explain that you must not complete the flip 
            if(right > n){
    
                return -1;
            }
            // Flip once 
            flag ^= 1;
            // Record the number of turns 
            ans++;
            // Use if To prevent cross-border , because right Yes, we can n Of 
            if(right < n){
    
//-----------------------------------------------
                // Mark next flag Where you need to flip 
                A[right] +=2;
//-----------------------------------------------
            }
        }
        return ans;
    }
};

Time complexity ： O(n).n Is an array A Size .
Spatial complexity ： O(1).

PS:
Compare the Space O(n) and O(1) Submission of , It doesn't make any difference how you feel .