LeetCode 605. Can Place Flowers

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.

Given an integer array flowerbed containing 0's and 1's, where 0 means empty and 1 means not empty, and an integer n, return if n new flowers can be planted in the flowerbed 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

Constraints:

• 1 <= flowerbed.length <= 2 * 104
• flowerbed[i] is 0 or 1.
• There are no two adjacent flowers in flowerbed.
• 0 <= n <= flowerbed.length

给了一个0和1构成的数组，要把其中的0变成1，使得最后形成的数组不能有相邻的1。这题刚开始的直观思路就是那就从最左开始放1，能尽量往左放就放，就是greedy的思想，但是并不会证明它的正确性。看了答案确实它是正确的……于是就写了代码，嗯，刚开始还被坑了一下，如果n为0的时候我这个会返回false，看了答案最后是返回count >= n，倒也合理。

Runtime: 1 ms, faster than 100.00% of Java online submissions for Can Place Flowers.

Memory Usage: 52 MB, less than 63.67% of Java online submissions for Can Place Flowers.

class Solution {
    public boolean canPlaceFlowers(int[] flowerbed, int n) {
        if (n == 0) {
            return true;
        }
        int count = 0;
        for (int i = 0; i < flowerbed.length; i++) {
            if (flowerbed[i] == 0) {
                boolean emptyLeft = (i == 0) || (flowerbed[i - 1] == 0);
                boolean emptyRight = (i == flowerbed.length - 1) || (flowerbed[i + 1]) == 0;
                if (emptyLeft && emptyRight) {
                    flowerbed[i] = 1;
                    count++;
                    if (count == n) {
                        return true;
                    }
                }
            }
        }
        return false;
    }
}

还看到有人提到说上面这个做法改变了input array, which is not a good idea，确实。如果需要保持原来的array，我们需要额外定义一个变量来存放前一个1的位置。以及如果这道题是求一共有多少种方法来实现，那么应该用dp，嗯，懒得想了，以后有空回来填坑好了。

还有一种思路是通过连续的0的个数来算，假如两个1之间有n个0，那么这些0之中可以有(n - 1) / 2个0变成1。比如(0, 0) -> 0，(0, 0, 0) - > 1，(0, 0, 0, 0) -> 1……前面这里没有考虑到第一个或者最后一个为0的情况，于是还需要额外在原数组前后加一个dummy 0，因此可以最开始的时候把0的个数初始化为1，最后return的时候因为return的要是最后一串0，又因为多一个dummy 0，所以最后result + n / 2就是最终可以放下的数量。代码就不写了，贴链接吧。

Loading...