Python, Straightforward with Explanation


  • 10

    We need to justify a greedy solution.

    Call a plot ready if the very first flower is allowed to be planted there.
    Consider the left-most ready plot x (if it exists). If x+1 is not ready, then we increase our answer strictly by planting at x, since x does not disturb any ready plots. If x+1 is ready, then planting at x instead of x+1 is atleast as good, since x disturbs only {x, x+1}, whereas x+1 disturbs {x, x+1, x+2}.

    Now our implementation is trivial. For each plot from left to right, if we can plant a flower there, then do so. We can plant a flower if the left neighbor is 0 (or we are on the left edge), AND the right neighbor is 0 (or we are on the right edge).

    def canPlaceFlowers(self, A, N):
        for i, x in enumerate(A):
            if (not x and (i == 0 or A[i-1] == 0) 
                    and (i == len(A)-1 or A[i+1] == 0)):
                N -= 1
                A[i] = 1
        return N <= 0
    

  • 3
    L

    You can have a slight optimization if you include a return for when n<=0 in the if statement.

    class Solution(object):
        def canPlaceFlowers(self, flowerbed, n):
            """
            :type flowerbed: List[int]
            :type n: int
            :rtype: bool
            """
            for i,c in enumerate(flowerbed):
                if (not c and (i==0 or not flowerbed[i-1])) and (i==len(flowerbed)-1 or not flowerbed[i+1]):
                    n-=1
                    flowerbed[i]=1
                    if n<=0: return True
            return not n

  • 1
    A

    More optimized

    class Solution(object):
    def canPlaceFlowers(self, flowerbed, n):
    """
    :type flowerbed: List[int]
    :type n: int
    :rtype: bool
    """

        max_trees = 0
        l = len(flowerbed)
        i = 0
        while i < l:
            if (flowerbed[i] == 0) and ((i == 0) or (flowerbed[i-1] != 1)) and ((i+1 >= l) or (flowerbed[i+1] != 1) ):
                max_trees += 1
                if max_trees - n >= 0:
                    return True
                i +=2
            else:
                i += 1
                
        
        return max_trees >= n

  • 5
    P

    No improvement, but more straight-forward and easier to understand

    class Solution(object):
        def canPlaceFlowers(self, flowerbed, n):
            """
            :type flowerbed: List[int]
            :type n: int
            :rtype: bool
            """
            count = 0
            flowerbed = [0] + flowerbed + [0]
            for i in range(1, len(flowerbed)-1):
            	if flowerbed[i-1] == flowerbed[i] == flowerbed[i+1] == 0:
            		flowerbed[i] = 1
            		count += 1
            return count >= n
    

  • 1
    C

    Basic idea, if there are x continuous empty slots, you could plant (x-1)/2 flowers at most.

    class Solution(object):
        def canPlaceFlowers(self, flowerbed, n):
            """
            :type flowerbed: List[int]
            :type n: int
            :rtype: bool
            """
            cnt=1
            po=0
            for i in flowerbed:
                if i==1:
                    po+=(cnt-1)/2
                    cnt=0
                else:
                    cnt+=1
            if cnt>1:po+=cnt/2    
            return po>=n  
    

  • 0
    J

    @awice sorry i just have a question
    what is meant by
    if (NOT x and (i == 0 or A[i-1] == 0)
    what is the function of NOT x, here? thx


  • 0
    Z

    @JianQiang1029
    meaning x == 0


Log in to reply
 

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