605. Can Place Flowers

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

题解：

class Solution {
    public boolean canPlaceFlowers(int[] flowerbed, int n) {
        int sum = 0;
        LinkedList<Integer> list = new LinkedList<>();
        for (int i = 0; i < flowerbed.length; i++) {
            if (flowerbed[i] == 1) {
                int betweenCnt = 0;
                if (list.size() > 0) {
                    betweenCnt = (i - list.getLast() - 2) / 2;
                } else {
                    betweenCnt = (i > 1) ? (i - 2) / 2 + 1: 0;
                }
                sum += betweenCnt;
                list.add(i);
            }            
        }
        
        if (list.isEmpty()) {
            sum += (flowerbed.length + 1) / 2;
        } else {
            int betweenCnt = 0;
            if (list.getLast() < flowerbed.length - 2) {
                betweenCnt = (flowerbed.length - 1 - list.getLast() - 2) / 2 + 1;
            }
            sum += betweenCnt;
        }
        
        return sum >= n;
    }
}

发现直接 Greedy 种花更简单。

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