This is the 28th day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021.

Title description:

605. Flower Problems – LeetCode (leetcode-cn.com)

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.

The sample a

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 * 10^4
  • Flowerbed [I] is 0 or 1
  • There are no two adjacent flowers in the Flowerbed
  • 0 <= n <= flowerbed.length

Thought analysis

traverse

I think the idea is similar to the solution of the elder brother’s problem. I think it is much simpler than the official proof of greed. Here is a brief description:

They say that adjacent cells can’t grow flowers together, which is kind of like jumping cells, and we just have to go through the array

If the index is 1, there are flowers in this position. If the index is 1, there are flowers in this position. If the index is 1, there are flowers in this position.

When we encounter this position is 0, because every time we encounter 1 in the previous step, we jump two squares, so the previous cell must be 0. At this point, we only need to determine whether the next cell is 1 to get the index cell can plant flowers. If it can plant flowers, we reduce n by one, and then this position will be treated as if we encounter 1, that is, jump two squares. If the last cell of index is 1, it means that flowers cannot grow in this position and flowers cannot grow in the next two cells (see step 1). Skip 3 cells directly.

When n is reduced to 0, it means that n flowers can be planted, then you can exit the traversal and return true. If n is not reduced to 0 at the end of the traversal, the maximum number of flowers is less than n, and false is returned.

AC code

class Solution {
    public boolean canPlaceFlowers(int[] flowerbed, int n) {
        for (int i = 0, len = flowerbed.length; i < len && n > 0;) {
		if (flowerbed[i] == 1) {
			i += 2;
		} else if (i == flowerbed.length - 1 || flowerbed[i + 1] = =0) {
			n--;
			i += 2;
		} else {
                Flowerbed [I +2+1]=1
			i += 3; }}return n <= 0; }}Copy the code

conclusion

Read the next several questions, are easier to understand the answer, relative to the official solution of greed.

reference

Flower Problems – Flower Problems – LeetCode (leetcode-cn.com)

Very easy to understand lattice hopping solution (100% of the time) – Flower problem – LeetCode (leetcode-cn.com)

605. Flower Problems – Flower Problems – LeetCode (leetcode-cn.com)