[C#] Simple count and caculation, with explain


  • 0
    Z

    Simply count the continuous empty slots(segment), and calculate the flower count can be placed in the segment, sum all count of them, we can get the max count of the whole flowers can be planted on the flowerbed.

    Suppose that we count the segment has emptyCount empty slots, and the segment has 3 states:

    1. double end sealed, likes: 1, 0 .... 0, 1
      in this situation, the count of empty slot can only place (emptyCount - 1) /2 flower(s)
    2. single end sealed: 0,0....0, 1, or 1,0.....0,0
      in this situation, the segment can play emptyCount / 2 flowers
    3. double end opened: 0,0....0,0
      in this segment, we can place (emptyCount + 1) /2 flowers
        public bool CanPlaceFlowers(int[] flowerbed, int n) {
            int canPlaceCount = 0;
            
            // left-end sealed or not
            bool leftF = false;
            int emptyCount = 0;
            // scan the flowerbed from left to right
            foreach(var f in flowerbed)
            {
                if(f != 0) // planted slot, and implicit right sealed.
                {
                    if(leftF == false) leftF = true; // seal left-end for next segment, if it is open
                    else emptyCount --;
                    // how many flower can placed in this fragment 
                    canPlaceCount += emptyCount / 2;
                    
                    emptyCount = 0;
                } else { // empty slot
                    emptyCount ++;            
                }
            }
            if(emptyCount > 0) { // right-end opened
                if(leftF == false) emptyCount ++;
                canPlaceCount += emptyCount / 2;
            }
            return canPlaceCount >= n;
        }
    

Log in to reply
 

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