当前位置：网站首页>leetcode 605. Can place flowers planting problem (simple)

leetcode 605. Can place flowers planting problem (simple)

2022-07-18 03:40:00 【InfoQ】

One 、 The main idea of the topic

label : greedy

https://leetcode.cn/problems/can-place-flowers

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

Two 、 Their thinking

Ideas ： There are three consecutive 0 Words , Plant a flower in the middle .

Realization ： Traversal array , Judge the current element 、 Both left and right are 0 You can plant flowers , The number of flowers can be planted plus 1, And set the current element to 2, Prevent affecting the judgment of the next element . When the number of planting value flowers is greater than n return true.

3、 ... and 、 How to solve the problem

3.1 Java Realization

public class Solution {
 public boolean canPlaceFlowers(int[] flowerbed, int n) {
 if (n == 0) {
 return true;
 }
 int count = 0;
 int len = flowerbed.length;
 for (int i = 0; i < len; i++) {
 boolean left = i == 0 ? true : flowerbed[i - 1] == 0;
 boolean right = i == len - 1 ? true : flowerbed[i + 1] == 0;
 if (flowerbed[i] == 0 && left && right) {
 count++;
 flowerbed[i] = 2;
 if (count >= n) {
 return true;
 }
 }
 }
 return false;
 }
}