Leetcode notes 605. can place flowers (easy) 605. planting flowers

Just started trying to write this thing , I hope you can point out the shortcomings after reading this article , thank you ！！

1. Problem description ：（ You must be familiar with the topic ！ But out of habit, I copied and pasted ）

         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.

2. Code ：（ I believe some people have ideas and everything , Just want to see the code , So put the code first ）

class Solution {
public:
    bool canPlaceFlowers(vector<int>& flowerbed, int n) {
        // Two special cases 
        if(n == 0){
            return true;
        }
        // When n > flowerbed.size()/2 + 1 when , It must be false.
        if(n > flowerbed.size() / 2 + 1){
            return false;
        }

        // Add 0, Avoid the trouble of classification discussion .
        flowerbed.emplace(flowerbed.begin(), 0);
        int count = 0;  // The amount that can be planted 
        int num = 1;    //  Count   whenever num == 3 when ,++count;

        // Every three adjacent 0 You can plant a flower , notes ： The next time num The count is from the third 0 At the beginning ！！！
        for(int i = 1; i < flowerbed.size(); ++i){
            if(flowerbed[i] != 0){
                num = 0;
            }else{
                ++num;
                if(num == 3){
                    ++count;
                    num = 1;
                }
            }
        }
        // At the end of the array is 00 You can plant a pot .       
        if(num == 2){
             ++count;
        }
        return {count >= n? true:false};
    }
};

3. Their thinking ：

         Since flowers cannot be planted on adjacent plots , Then every three adjacent open spaces can be planted with a pot of flowers , Turn the problem into traversing three adjacent 0, Each group can plant a pot , With num For the neighboring 0 Number of ,count For the number of pots of flowers that can be planted . When flowerbed[i]==0,++num, When num == 3 when ,++count, hold num Reset to 1; When flowerbed[i]== 1,num Zero clearing .

4. Details ：

        @. When the first value of the array is 1 Or is it 0 It seems that classification discussion is needed to accurately determine count Value , To avoid this trouble , I take to add one at the head of the array 0, In this way, there is no need to classify and discuss .

        @. whenever num == 3（ There are three consecutive 0） when ,count Add one to the value of , At this time num The value of is not zero , Instead, set it to 1（ This is what I think is the most important point ）, Because the third 0 Can participate in the following 0 In the count of , For example, the array is 010000010, After planting the most flowers, it becomes 010101010, That is to say 5 A continuous 0 It can be planted 2 basin , Without the need for 6 individual 0.（ The expression here seems not very good , If I think of something better, I'll come back and change it .）

        @. There are two situations in which the result can be directly judged ： The first is n == 0, It must be true; The second is n>(flowerbed.size()/2 + 1), namely n The value has been greater than what the array can theoretically hold 1 The number of , It must be false.

5. Code section

        @. adopt emplace() Function or insert() Functions can realize the function of adding elements .emplace() You can only add one element at a time , Faster ;insert() Function can add one or more elements or an array at a certain position , Slower . So I chose emplace() function .

        @. In fact, add one at the end of the array 0 There is no need for final judgment count == 2 了 , But the speed is much slower , So I made a compromise .