605. 种花问题
- 题号：力扣605
- 知识点：贪心，数组
- 目标完成度：43/150
- 总结
题干：
思路：
- 1.遍历数组，如果当前位置是0，并且它前一个位置和后一个位置也是0，则说明该位置可以种花。把该位置种上花，该位置的元素改为1，表示已经有花了。
- 2.难点在于边界的处理，第一个位置和最后一个位置如果是0时需要特殊处理。
class Solution:
def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
ans = 0
if len(flowerbed) < 3:
if flowerbed.count(1):
return not n
return True if n<=1 else False
if flowerbed[0] == 0 and flowerbed[1] == 0:
ans += 1
flowerbed[0] = 1
for i in range(1, len(flowerbed)-1):
if flowerbed[i] == 0:
if flowerbed[i-1] == 0 and flowerbed[i+1] == 0:
ans += 1
flowerbed[i] = 1
if ans >= n:
return True
if flowerbed[-2] == 0 and flowerbed[-1] == 0:
ans += 1
flowerbed[0] = 1
if ans >= n:
return True
return False
- 3.题解中看到的比较好的一个处理边界的方法：
/**
* 贪心
* 能种花的地方
* 当前位置没有花
* 前面要么没有花, 要么是边界
* 后面要么没有花, 要么是边界
*/
public boolean canPlaceFlowers(int[] flowerbed, int n) {
int length = flowerbed.length;
for (int i = 0; i < length; i++) {
if (flowerbed[i] == 0 && (i == 0 || flowerbed[i-1] == 0) && (i == length-1 || flowerbed[i+1] == 0)){
n--;
//把花种上
flowerbed[i] = 1;
}
if (n <= 0){
return true;
}
}
return false;
}
