share a counting solution


  • 0
    C

    if there are n zeros between 2 ones (1 0 0 ... 0 0 1), we can insert (n - 1) / 2 ones.
    then add [1, 0] before flowerbed and [0, 1] after flowerbed, the array will be [1 0 flowerbed 0 1]. so all zeros surrounded by 2 ones.

    public class Solution {
        public boolean canPlaceFlowers(int[] flowerbed, int n) {
            int count = 1;                 // insert  [1, 0] in front the array
            for (int f : flowerbed) {
                if (f == 0) {
                    count ++;
                } else {
                    n -= (count - 1) / 2;
                    count = 0;
                }
            }
            n -= count / 2;           // ((1 + count) - 1) / 2, append [0, 1] to the end of the array
            if (n > 0) return false;
            else return true;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.