Leetcode (605) -- flower planting

Leetcode（605）—— The problem of planting flowers

subject

Suppose there's a very long flower bed , Part of the plot is planted with flowers , The other part didn't . But , Flowers cannot be planted on adjacent plots , They compete for water , Both will die .

Give you an array of integers flowerbed Indicates a flower bed , By a number of 0 and 1 form , among 0 No flowers ,1 It means flowers are planted . There's another number n , Can it be planted without breaking the planting rules n A flower ？ Energy returns true , If not, return false.

Example 1：

Input ：flowerbed = [1,0,0,0,1], n = 1
Output ：true
Example 2：

Input ：flowerbed = [1,0,0,0,1], n = 2
Output ：false

Tips ：

1 <= flowerbed.length <= 2 * 104
flowerbed[i] by 0 or 1
flowerbed There are no two adjacent flowers
0 <= n <= flowerbed.length

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/can-place-flowers
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Answer key

Method 1 ： Greedy Algorithm

Ideas

​​   Judge whether you can plant in the flower bed without breaking the planting rules $n$ A flower , From the perspective of greed , You should plant as many flowers as possible without breaking the planting rules , Then judge whether the maximum number of flowers that can be planted is greater than or equal to $n$.

​​   Suppose the subscript of the flower bed $i$ And subscripts $j$ Flowers are planted everywhere , among $j-i\ge 2$, And subscript $[i+1,j-1]$ No flowers are planted in the range , Only when the $j-i\ge 4$ Can only be subscript $i$ And subscripts $j$ Plant more flowers between , And the subscript range of flowers that can be planted is $[i+2,j-2]$. The number of places where flowers can be planted is $p=j-i-3$, When $p$ If it is an odd number, it can be planted in this range at most $(p+1)/2$ A flower , When $p$ If the number is even, it can be planted in this range at most $p/2$ A flower . Because when $p$ When it's even , Under the rule of integer division $p/2$ and $(p+1)/2$ equal , So no matter $p$ Is it odd or even , Can be planted within this range at most $(p+1)/2$ A flower , That is, it can be planted within this range at most $(j-i-2)/2$ A flower .

​​   The above is the case of planting flowers between two existing flowers （ There is no other flower between the two flowers ）. Suppose the subscript of the flower bed $l$ At the left is the flower that has been planted , Subscript $r$ On the far right is the flower that has been planted （ That is, for any $k<l$ or $k>r$ There are $\text{flowerbed}[k]=0$）, How to calculate the subscript $l$ The maximum number of flowers that can be planted on the left and the subscript $r$ How many flowers can you plant on the right ？

​​   Subscript $l$ On the left $l$ A place , When $l<2$ Cannot subscript $l$ Plant flowers on the left , When $l\ge 2$ Can be in the subscript range $[0,l-2]$ Plant flowers within the range , The number of places where flowers can be planted is $l-1$, It can be planted at most $l/2$ A flower .

​​   Make $m$ Is an array $\text{flowerbed}$ The length of , Subscript $r$ On the right $m-r-1$ A place , The number of places where flowers can be planted is $m-r-2$, It can be planted at most $(m-r-1)/2$ A flower .

​​   If there are no flowers on the flower bed , Then there are $m$ There are four places to plant flowers , It can be planted at most $(m+1)/2$ A flower .

According to the above calculation method , Calculate the maximum number of flowers that can be planted in the flower bed , Judge whether it is greater than or equal to $n$ that will do . The specific methods are as follows .

• maintain $\text{prev}$ Indicates the subscript position of the last planted flower , At the beginning $\text{prev}=-1$, Indicates that you have not encountered any flowers that have been planted .
• Traverse the array from left to right $\text{flowerbed}$, When you meet $\text{flowerbed}[i]=1$ According to the $\text{prev}$ and $i$ Calculate the maximum number of flowers that can be planted in the previous interval , Then make $\text{prev}=i$, Continue traversing the array $\text{flowerbed}$ The remaining elements .
• Traversal array $\text{flowerbed}$ After the end , According to the array $\text{prev}$ And length $m$ Calculate the maximum number of flowers that can be planted in the last interval .
• Judge whether the maximum number of flowers that can be planted in the whole flower bed is greater than or equal to $n$.

​​   Because we only need to judge whether we can plant in the flower bed without breaking the planting rules $n$ A flower , There is no need to know exactly how many flowers can be planted in the flower bed , So it can be optimized in the loop , When the number of flowers that can be planted has reached $n$, You can go back to $\text{true}$, There is no need to continue calculating the rest of the array .

Code implementation

my ：

class Solution {
    
public:
    bool canPlaceFlowers(vector<int>& flowerbed, int n) {
    
        if(n == 0) return true;
        int size = flowerbed.size();
        int m = 0;
        int lastflower = -2;    //  In order to deal with  [0] 1  In special circumstances 
        for(int i = 0 ; i < size; i++){
    
            if(flowerbed[i] == 1){
    
                if(lastflower == -1) m += i/2;  // (i-0)/2
                else m += (i-lastflower-2) > 0? (i-lastflower-2)/2: 0;
                if(m >= n) return true;
                lastflower = i;
                i++;    //  Skip the next 0
            }else if(i == size-1){
    
                //  Special circumstances, i.e  [0,1,0,0,0]
                //  In order to deal with  [0] 1  In special circumstances , Make  lastflower = -2
                m += (i-lastflower)/2;
                if(m >= n) return true;
            }
        }
        return false;
    }
};

Netizens have a very clever idea ：
It's enough to judge whether there are flowers in the back . This use 1 The two adjacent sides must be followed by 0, And features at the end .
Because if flowerbed[i]==1 When , it i++ 了 , After one cycle, it will also i++, amount to i Two steps , So there is no need to judge the front .

class Solution {
    
public:
    bool canPlaceFlowers(vector<int>& flowerbed, int n) {
    
        int size = flowerbed.size();
        for(int i = 0; i < size; ++i){
    
            if(flowerbed[i] == 0 && (i+1 == size || flowerbed[i+1] == 0)){
    
                n--;
                i++;
            }else if(flowerbed[i] == 1) i++;
            if(n <= 0) return true; //  Less than 0 To avoid n For the initial 0 The situation of  
        }
        return false;
    }
};

//  I wrote the following 
class Solution {
    
public:
    bool canPlaceFlowers(vector<int>& flowerbed, int n) {
    
        int size = flowerbed.size();
        //  Suppose its left adjacency is 0, Then you only need to check whether it and the right are 0 that will do 
        //  Then take care of the special circumstances at the end 
        for(int i = 0; i < size; i++){
    
            if(flowerbed[i] == 1) i++;  //  Jump to adjacent 0 Next to , You can ensure that the left side of the next inspection position is 0
            else if(((i == size-1 && flowerbed[i] == 0)) || (flowerbed[i] == flowerbed[i+1])){
    
                i++;
                n--;
            }
            if(n <= 0) return true;
        }
        return false;
    }
};

Complexity analysis

Time complexity ：$O(m)$, among $m$ It's an array $\text{flowerbed}$ The length of . You need to traverse the array once .
Spatial complexity ：$O(1)$. The extra space used is constant .