Can Place Flowers

Suppose you have a long flowerbed in which some of the plots are planted and some are not. However, flowers cannot be planted in adjacent plots - they would compete for water and both would die.

Given a flowerbed (represented as an array containing 0 and 1, where 0 means empty and 1 means not empty), and a number n, return if n new flowers can be planted in it without violating the no-adjacent-flowers rule.

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
Note:
The input array won't violate no-adjacent-flowers rule.
The input array size is in the range of [1, 20000].
n is a non-negative integer which won't exceed the input array size.

描述：

假设你有一个花园,有些地是可以种花的,有些不可以。要求是你种的花不能够相邻,也就是说花与花之间是有间隙的,如果种的过于密集.他们可能会因为竞争水资源活不了。 给定过一个花园的数组，其中的元素包括0和1，0表示空地，1表示已经种了都花。给定一个花的数目，问，能否种的下这么都花，保证花不会死。 例： 输入： flowerbed = [1,0,0,0,1], n = 1 输出：True

输入: flowerbed = [1,0,0,0,1], n = 2 输出: False

注意： 1.输入的数组遵循种花的规则
2.输入的数组长度在1~20000之间
3.n是一个整数，不会超过输入数组的长度

分析：

可以种花的数组有以下特点 00x 这个地方 第一位0 可以种花
000 这个地方 中间的0 可以种花
x00 这个地方 最后的0 可以种花
然后遍历整个数组即可

• 解题思路：主要是找到能种花的场景，如果当前位置能够种花，那么这设置为1，将最大的值做-1操作。循环结束，判断最后n的值与0进行比较。(或者定义一个常量对其做+1操作，然后与n进行对比)关键判断在于 左右两边是否种花。(贪心算法：从左向右遍历数组，将满足条件的0设置为1，然后将值与n比较)

Java

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

C++:

class Solution {  
public:  
    bool canPlaceFlowers(vector<int>& flowerbed, int n) {

        int length = flowerbed.size();
        for (int i = 0; i < length && n > 0; i++) {
            if (flowerbed[i] == 0) {
                int left = i - 1 > 0 ? i - 1 : 0;
                int right = i + 1 < length - 1 ? i + 1 : length - 1;
                if (flowerbed[left] == 0 && flowerbed[right] == 0) {
                    flowerbed[i] = 1;
                    --n;
                }
            }
        }
        return n <= 0;
    }
};

Swift:

   func canPlaceFlowers(_ flowerbed: [Int], _ n: Int) -> Bool {

        var flowerbed = flowerbed
        var n = n
        if flowerbed.count == 0 {return false}
        let arrayLength = flowerbed.count
        for i in 0 ..< arrayLength {
            if n > 0 {
                if flowerbed[i] == 0 {
                    let left = i - 1 > 0 ? i - 1 : 0
                    let right = i + 1 < arrayLength - 1 ? i + 1 : arrayLength - 1
                    if flowerbed[left] == 0 && flowerbed[right] == 0 {
                        flowerbed[i] = 1
                        n -= 1
                    }
                }
            }
        }
        return n <= 0
    }

Python:

class Solution(object):  
    def canPlaceFlowers(self, flowerbed, n):
        """
        :type flowerbed: List[int]
        :type n: int
        :rtype: bool
        """
        for i, v in enumerate(flowerbed):
            if v: continue
            if i > 0 and flowerbed[i - 1]: continue
            if i < len(flowerbed) - 1 and flowerbed[i + 1]: continue
            n -= 1
            flowerbed[i] = 1
        return n<=0

什么是贪心算法？

词条来自维基百科

贪心法，又称贪心算法、贪婪算法、或称贪婪法，是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的算法。比如在旅行推销员问题中，如果旅行员每次都选择最近的城市，那这就是一种贪心算法。 贪心算法在有最优子结构的问题中尤为有效。最优子结构的意思是局部最优解能决定全局最优解。简单地说，问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解。 贪心算法与动态规划的不同在于它对每个子问题的解决方案都做出选择，不能回退。动态规划则会保存以前的运算结果，并根据以前的结果对当前进行选择，有回退功能。 贪心法可以解决一些最优化问题，如：求图中的最小生成树、求哈夫曼编码……对于其他问题，贪心法一般不能得到我们所要求的答案。一旦一个问题可以通过贪心法来解决，那么贪心法一般是解决这个问题的最好办法。由于贪心法的高效性以及其所求得的答案比较接近最优结果，贪心法也可以用作辅助算法或者直接解决一些要求结果不特别精确的问题。

什么是动态规划？

词条来自维基百科

动态规划（英语：Dynamic programming，简称DP）是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。 动态规划常常适用于有重叠子问题[1]和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。 动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再合并子问题的解以得出原问题的解。 通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量：一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。

本题来自:leetCode

https://leetcode.com/problems/can-place-flowers/description/