This article is participating in Python Theme Month. See the link for details

describe

You are given an array rectangles where rectangles[i] = [li, wi] represents the ith rectangle of length li and width wi.

You can cut the ith rectangle to form a square with a side length of k if both k <= li and k <= wi. For example, if you have a rectangle [4,6], you can cut it to get a square with a side length of at most 4.

Let maxLen be the side length of the largest square you can obtain from any of the given rectangles.

Return the number of rectangles that can make a square with a side length of maxLen.

Example 1:

Input: rectangles = [[5,8],[3,9],[5,12],[16,5]] Output: 3 Explanation: The largest squares you can get from each rectangle are of [5,3,5,5] 5, and you can get it out of 3 rectangles.Copy the code

Example 2:

Input: rectangles = [[2, 3], [3, 7], [4], [3, 7]] Output: 3Copy the code

Note:

1 <= rectangles.length <= 1000 rectangles[i].length == 2 1 <= li, wi <= 109 li ! = wiCopy the code

parsing

Given a list of rectangles, cut each rectangle to form a square and ask the number of squares with the largest side length that can be formed. The length of the sides of a square is by the smaller side of the rectangle, so find the smallest side of all the rectangles, and then calculate the dictionary of numbers to find the number of occurrences of the largest side. This is a bit of a cheat using Python’s built-in function collections.counter ().

answer

class Solution(object):
    def countGoodRectangles(self, rectangles):
        """
        :type rectangles: List[List[int]]
        :rtype: int
        """
        c = collections.Counter([min(r) for r in rectangles])
        k = c.keys()
        return c[max(k)]
        	      
		
Copy the code

The results

Runtime: 160 ms, faster than 18.45% of Python online submissions for Number Of Rectangles That Can Form The Largest Square.
Memory Usage: 14 MB, less than 58.67% of Python online submissions for Number Of Rectangles That Can Form The Largest Square.
Copy the code

parsing

If you don’t use built-in functions, use dictionary D to save the number of smaller edges in each rectangle, and finally find the number of the largest edges. The results here are quite satisfactory. Both of them are close to 100%. In fact, I think the leetcode test is related to the network environment.

answer

class Solution(object):
    def countGoodRectangles(self, rectangles):
        """
        :type rectangles: List[List[int]]
        :rtype: int
        """
        d = {}
        for r in rectangles:
            p = min(r)  
            if p in d:
                d[p] += 1 
            else:
                d[p] = 1 
        return d[max(d.keys())]  
Copy the code

The results

Runtime: 140 ms, faster than 97.60% of Python online submissions for Number Of Rectangles That Can Form The Largest Square.
Memory Usage: 13.9 MB, less than 99.04% of Python online submissions for Number Of Rectangles That Can Form The Largest Square.
Copy the code

Original link: leetcode.com/problems/nu…

Your support is my biggest motivation