Python solution, count number of Zero between one


  • 0
    Y
        def canPlaceFlowers(self, A, n):
            """
            :type A: List[int]
            :type n: int
            :rtype: bool
            """                
            m=len(A)
            if n==0: return True
            cnt=0
            start=-1
            for i in xrange(m):
                if A[i]==1:
                    if start<0:
                        x=i-start-1
                    else:
                        x=i-start-1-1
                    cnt+=x//2
                    start=i
            if start<0:
                cnt+=(m-start)//2
            else:
                cnt+=(m-start-1)//2
            return cnt>=n
    

  • 0
    B

    Same idea different implementation.

    def canPlaceFlowers(flowerbed, flowers):
    
        # fast fail
        mx = (len(flowerbed) // 2) + 1
        if mx < sum(flowerbed)+flowers:
            return False
        
        # front two
        if flowers and sum(flowerbed[:2]) == 0:
            flowerbed[0] = 1
            flowers -= 1
            
        # back two
        if flowers and sum(flowerbed[-2:]) == 0:
            flowerbed[-1] = 1
            flowers -= 1
        
        # track adjacent zeros
        n, size = len(flowerbed), 0
        for i in xrange(n):
            if flowerbed[i]:
                size -= 3 
                if size >= 0:
                    flowers -= min((size // 2) + 1, flowers) 
                size = 0
            else:
                size += 1
                
        size -= 3
        if size >= 0:
            flowers -= min((size // 2) + 1, flowers)
        
        return flowers == 0
    

  • 0
    B

    Same idea, different way.

    def canPlaceFlowers(self, flowerbed, n):

    #list the indices of flowers in the flowerbed
    flower_position = [i for i, x in enumerate(flowerbed) if x == 1]
    
    #if the first position is vacant, prevent a flower two positions on the left
    if flowerbed[0] != 1:
        flower_position = [-2]+flower_position
    #if the last position is vacant, prevent a flower two positions on the right
    if flowerbed[-1] != 1:
        flower_position.append(len(flowerbed)+1)
    
    #first find the distance between two adjacent flowers, then use //2-1 to find the number of flowers allowed between
    flower_distance = [(j-i)//2-1 for i, j in zip(flower_position[:-1], flower_position[1:])]
    
    return n <= sum(flower_distance)

  • 0
    Y

    Can simplify by assuming there are plants in index of -2 and len+1 instead of checking by if and else

    if n==0: return True
            cnt, pre, l = 0, -2, len(flowerbed)
            for i in xrange(l):
                if flowerbed[i]==1:
                    cnt+=(i-2-pre)//2
                    pre=i
            cnt+=((l+1)-2-pre)//2
            return cnt>=n
    

Log in to reply
 

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