This is the 10th day of my participation in the August More Text Challenge. For details, see:August is more challenging

Topic link

605. The problem of planting flowers

Topic describes

Suppose you have a very long flower bed, and one part of the plot is planted with flowers, and another part is not. But flowers can’t be planted on adjacent plots. They will compete for water, and both will die.

I give you an integer array flowerbed for a flowerbed, consisting of 0s and 1s, where 0 means no flowers and 1 means flowers are planted. If I have another number n, can I plant n flowers without breaking the planting rules? Return true if it is, false if it is not.

The test case

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: falseCopy the code

Tip:

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

Subject analysis

In other words, given an array with a value of 0 or 1, the existing array is guaranteed to have no adjacent 1

All we need to do is go in and change the zero to one as much as possible, so that there are no adjacent ones, and return true if we can do this at least n times, false otherwise

As a simple idea, when s[I -1] + s[I] + s[I +1] = 0, you can plant flowers at the position I

If we operate directly on the original array, we need to determine the special case (found after being beaten by the test case) :

  1. s = [0]You can plant 1 flower
  2. s = [0, 0, ....]If the first two terms are 0, you can plant one flower at I = 0
  3. In the same way,s = [...., 0, 0]When the last two terms are 0, one flower can be planted at the position I = S.length-1

Since it takes I as the center point and takes the values before and after to judge, the traversal range is [1, s.length-1).

Tries to answer

Based on the above ideas, write the code:

var canPlaceFlowers = function(flowerbed, n) {
    if(n==0) return true;
	if (flowerbed.length == 0) return false;
	if (flowerbed.length == 1) {
		return flowerbed[0] = =0 ? true : false;
	}
	if (flowerbed[0] + flowerbed[1] = =0) {
		n--;
		flowerbed[0] = =1;
	}
	let len = flowerbed.length;
	if (flowerbed[len - 1] + flowerbed[len - 2] = =0) {
		n--;
		flowerbed[len - 1] = =1;
	}
	for (let i = 1; i < flowerbed.length - 1 && n > 0; i++) {
		if (flowerbed[i] + flowerbed[i - 1] + flowerbed[i + 1] = =0) {
			n--;
			flowerbed[i] = 1; }}return n > 0 ? false : true;
};

Copy the code

I’m sorry, but this code doesn’t work. I’ve already used if to process n==0, length==0, length==1, and the beginning and end may have two zeros in a row. Now the error test case is [0, 0], 2, and I don’t want to continue using if to process those strange test cases

If you want to take the time, you can use if to include those boundary test cases, but obviously it doesn’t make any sense, so we’re all trying to get the best solution, right

Optimize the summary

This code has a very intuitive problem, according to the condition of judgment, does not have generality

After looking at the problem, there is a great god to provide ideas, directly before and after the complement 0 processing, so directly can include the above special case

For example, [0] => [0, 0, 0], [0, 0,….] => [0, 0, 0,…., 0]

S [I -1] + s[I] + s[I +1] == 0

The topic answer

Post code

var canPlaceFlowers = function(flowerbed, n) {
	let fs = flowerbed;
	fs.push(0);
	fs.unshift(0);
	for (let i = 1; i < fs.length - 1 && n > 0; i++) {
		if (fs[i - 1] + fs[i] + fs[i + 1] = =0) {
			n--;
			fs[i] = 1; }}return n > 0 ? false : true;
};
Copy the code

This answer is much better than the last one, isn’t it?