【Leetcode】605. Can Place Flowers

Description

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

Input: flowerbed = [1,0,0,0,1], n = 1
Output: True

Note

1.The input array won’t violate no-adjacent-flowers rule.
2.The input array size is in the range of [1, 20000].
3.n is a non-negative integer which won’t exceed the input array size.

Solution

First

public boolean canPlaceFlowers(int[] flowerbed, int n) {
        int count = 0;
        int len = flowerbed.length;
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < len; i++) {
            if (flowerbed[i] == 1) {
                count++;
                list.add(i);
            }
        }
        if (n == 0) {
            return true;
        }

        if (len == 1 && count == 0 && n == 1) {
            return true;
        }

        if (count == 0) {
            return (len + 1)/2 >= n ? true : false;
        }
        if (count == 1) {
            //list.get(0)/2 + (len - list.get(0) - 1)/2 = (len - 1)/2
            int first = list.get(0)/2;
            int second = (len - list.get(0) - 1)/2;
            return first + second >= n ? true : false;
        }
        if (len - count <= 2) {
            return false;
        }
        int begin = 0;
        int available = 0;
        if (list.get(begin) > 1) {
            available += list.get(begin)/2;
        }
        while (begin < list.size() - 1) {
            if (list.get(begin + 1) - list.get(begin) >= 4) {
                int interval = list.get(begin + 1) - list.get(begin) - 1;
                if (interval % 2 == 0) {
                    available += interval/2 - 1;
                } else {
                    available += interval/2;
                }
            }
            begin++;
        }
        if (list.get(list.size() - 1) != len - 1) {
            available += (len - list.get(list.size() - 1) - 1)/2;
        }
        return available >= n ? true : false;
    }

Result

AC

Analyse

复杂度没问题，但是耗时太长，测了好多边界条件，而且在判断count==1的条件下，开始把list.get(0)/2 + (len - list.get(0) - 1)/2 = (len - 1)/2 直接加一起算，其实得分成两半，结果是会有差的。这个解法过于愚蠢。

Optimization

Idea

public boolean canPlaceFlowers(int[] flowerbed, int n) {
        int count = 0;
        int i = 0;
        while (i < flowerbed.length && count < n) {
            if (flowerbed[i] == 0) {
                int prev = i == 0 ? 0 : flowerbed[i - 1];
                int next = i == flowerbed.length - 1 ? 0 : flowerbed[i + 1];
                if (prev == 0 && next == 0) {
                    flowerbed[i] = 1;
                    count++;
                }
            }
            i++;
        }
        return count == n;
    }

Analyse

思路很清晰，开始想得count超过n不知道怎么在count==n的情况下就break，还是代码太不熟练，这个思路很清晰，一眼可以看出来，好解法，O(n)，代码行数少。