Topic describes

Suppose you have a very long flower bed, and one part of the plot is planted with flowers, but the other part is not. However, flowers cannot grow in adjacent plots. They compete for water and both die. Flowerbed gives you an array of integers representing a flowerbed, consisting of zeros and ones, where 0 indicates no flowers and 1 indicates flowers. Another number, n, can I plant n flowers without breaking the planting rules? Returns true if yes, false if no.

Source: LeetCode

Example 1:

Input: flowerbed = [1,0,0,0,1], n = 1 Output: trueCopy the code

Example 2:

Input: flowerbed = [1,0,0,0,1], n = 2 output: falseCopy the code

Tip:

  • 1 <= flowerbed.length <= 2 * 104
  • Flowerbed [I] is 0 or 1
  • There are no two adjacent flowers in the Flowerbed
  • 0 <= n <= flowerbed.length

Subject analysis

Num is the number of elements that can be modified, and n is the number of elements that are planned to be modified. Return true if num > n, false otherwise. The following conditions must be met: The value of the element flowerbed[I] and its neighboring elements are all 0, that is, Flowerbed [I-1] = 0, Flowerbed [I] = 0, and flower[I +1] = 0.

In this case, I use the idea of greedy algorithms. If the condition of planting flowers is met, modify it, and record the number of modified num until the end, judge the size relationship between num and n.

var canPlaceFlowers = function(flowerbed, n) {
    // To judge whether to plant or not, only there are no flowers on both sides
    let left=0,right=0;
    for(let i=0; i<flowerbed.length; i++) {if(i==flowerbed.length-1)
        {
            if(flowerbed[i]==0&&left==0&&right==0)
                n--;
        }
        else
        {
            if(flowerbed[i]==0&&left==0&&flowerbed[i+1] = =0)
            {    
                n--;
                flowerbed[i]=1;
                left = 1;
            }
            elseleft = flowerbed[i]; }}return n<=0;
};
Copy the code

In fact, the number of record changes num can be converted to n– whenever the record changes, and finally judge the case when n<=0. Let and rigth are for boundary issues, JS is not needed, it is very friendly for other languages.

In JS, the above boundary problem can be optimized by inserting a 0 at the beginning and end of the array, and the whole code will be clean.

var canPlaceFlowers = function(flowerbed, n) {
    flowerbed=[0. flowerbed,0];
    for(let i=1; i<flowerbed.length-1; i++) {if(flowerbed[i-1]+flowerbed[i]+flowerbed[i+1] = =0) { n--; flowerbed[i]++; }}return n<=0;
};
Copy the code

In fact, this approach can still be optimized, we do not need to judge all elements. A modified element flowerbed[I] cannot modify any of its neighbors, so there is no need to judge flowerbed[I +1]. We can skip more elements if we have a 1 on the right. Flowerbed [I +1] == 1 flowerbed[I +1] = 1 flowerbed[I +1] = 1

var canPlaceFlowers = function(flowerbed, n) {
    flowerbed=[0. flowerbed,0];
    for(let i=1; i<flowerbed.length-1; i+=2)
    {
        if(flowerbed[i]==0)
        {    
            if(flowerbed[i+1] = =0)
            {    
                n--;
                flowerbed[i]=1;
            }
            elsei++; }}return n<=0;
};
Copy the code

  1. I + = 2? After 0 -> 1 and flowerbed[I] = 1, the next judgment element is flowerbed[I +2], and the next judgment element is flowerbed[I +1] == 1.

  2. If (flowerbed [I + 1) = = 0)? Since we are always jumping to the next bit of Flowerbed [I] = 0 during the jump, we do not need to determine the value of the left element.

The optimization of the idea is not accomplished overnight, after repeated deliberation, in order to further! If you have any other ideas, please feel free to discuss them in the comments section 😄

The last

This is the No.2 of my LeetCode flash card, and the following chapters are waiting to be updated. If you like this LeetCode post, please like 😄

This article is participating in the “Gold Digging march Campaign”, click to see the details of the campaign.