605. 种花问题
贪心算法
思路
从左向右遍历花坛,在可以种花的位置就种一朵,能种就种(因为在任一种花时候,不种都不会得到更优解),是一种贪心的思想。
代码实现
class Solution { public: bool canPlaceFlowers(vector<int> &flowerbed, int n) { int count = 0; for (int i = 0; i < flowerbed.size(); i++) { if (!flowerbed[i] && (i == flowerbed.size() - 1 || !flowerbed[i + 1]) && (i == 0 || !flowerbed[i - 1])) { count++; flowerbed[i] = 1; } } return count >= n ? true : false; } };
麻了,一开始写的比这还要复杂,参考了网上的解法,算是比较简洁的了。括号里的逻辑或是重点,由此可以判断是否为首尾元素导致堆溢出。还要注意题目问的是最多,所以在不打破种植规则的情况下种入n朵花只要小于等于你算出的最大花数即可。