LeetCode 605 - Can Place Flowers

https://leetcode.com/problems/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:

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.

https://leetcode.com/articles/can-place-flowers/

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

Approach #2 Optimized [Accepted]

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

https://discuss.leetcode.com/topic/91303/java-greedy-solution-o-flowerbed-beats-100

DP will always work for any problem that can be solved by greedy which deals with making local choices while DP considers all global choices. There are many problems where greedy isn't sufficient to get an optimal solution.

However, this problem isn't one. Here each local choice is enough to get the optimal solution. You can prove it by induction. No matter what other choices you consider, for any given row of plants, you will find that the greedy solution will always yield the optimal solution. The other choices that you traverse here would simply be a waste.

    public boolean canPlaceFlowers(int[] flowerbed, int n) {
        int count = 0;
        for(int i = 0; i < flowerbed.length && count < n; i++) {
            if(flowerbed[i] == 0) {
      //get next and prev flower bed slot values. If i lies at the ends the next and prev are considered as 0. 
               int next = (i == flowerbed.length - 1) ? 0 : flowerbed[i + 1]; 
               int prev = (i == 0) ? 0 : flowerbed[i - 1];
               if(next == 0 && prev == 0) {
                   flowerbed[i] = 1;
                   count++;
               }
            }
        }
        
        return count == n;
    }

Buttercola: LinkedIn: Can Place Flowers

    public boolean canPlaceFlowers(List<Boolean> flowerbed, int numberToPlace) {

        this.hashCode();

        if(flowerbed == null || flowerbed.isEmpty()){

            throw new IllegalArgumentException("bed is empty");

        }

        if(numberToPlace==0)

            return true;

        if(flowerbed.size()==1){

            return !flowerbed.get(0) && numberToPlace<=1;

        }

        int counter = 0;

        for(int i=0; i< flowerbed.size(); i++){

            if(!flowerbed.get(i)){

                if((i==0 && !flowerbed.get(i+1))

                || (i==flowerbed.size()-1 && !flowerbed.get(i-1))

                || (!flowerbed.get(i+1) && !flowerbed.get(i-1)) ){

                    //place the flower

                    flowerbed.set(i, true);

                    counter++;

                    if(counter==numberToPlace)

                        return true;

                }

            }

        }   

        return false;

    }

https://www.cnblogs.com/grandyang/p/6983982.html

这道题给了我们一个01数组，其中1表示已经放了花，0表示可以放花的位置，但是有个限制条件是不能有相邻的花。那么我们来看如果是一些简单的例子，如果有3个连续的零，000，能放几盆花呢，其实是要取决约左右的位置的，如果是10001，那么只能放1盆，如果左右是边界的花，那么就能放两盆，101，所以如果我们想通过计算连续0的个数，然后直接算出能放花的个数，就必须要对边界进行处理，处理方法是如果首位置是0，那么前面再加上个0，如果末位置是0，就在最后面再加上个0。这样处理之后我们就默认连续0的左右两边都是1了，这样如果有k个连续0，那么就可以通过(k-1)/2来快速计算出能放的花的数量

Read full article from Buttercola: LinkedIn: Can Place Flowers