605. Can Place Flowers
On This Page
In this problem, we are given a flowerbed represented by an integer array
flowerbed, where 0 represents an empty plot and 1 represents a plot with a flower.
We need to determine if we can plant
n new flowers in the flowerbed without violating the rule that no two adjacent plots can have flowers.
To solve this problem, we can use a greedy approach. We iterate through the flowerbed and check each plot. If a plot is empty and its adjacent plots are also empty, we can plant a flower in that plot.
We repeat this process until we have planted all
n flowers or we have checked all plots in the flowerbed.
To solve this problem, we will define a helper function
check_neighbors that checks if a plot can be planted with a flower and updates the flowerbed and
- Initialize a variable
ito iterate through the flowerbed.
- For each plot in the flowerbed:
2.1. If the current plot is empty and its previous plot is also empty (i.e.,
flowerbed[i-1] == 0), call the
check_neighborsfunction. 2.2. Otherwise, if the current plot is empty and its next plot is also empty (i.e.,
flowerbed[i+1] == 0), call the
nis less than or equal to 0 (i.e., all flowers have been planted), otherwise return
def canPlaceFlowers(flowerbed, n): def check_neighbors(n): if i < len(flowerbed) - 1: if flowerbed[i+1] == 0: flowerbed[i] = 1 n -= 1 else: flowerbed[i] = 1 n -= 1 return n for i in range(len(flowerbed)): if flowerbed[i] == 0: if i > 0: if flowerbed[i-1] == 0: n = check_neighbors(n) else: n = check_neighbors(n) return n <= 0