本文主要是介绍Leetcode 391. Perfect Rectangle,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
解题思想
这道题是说给了一堆小矩形的坐标(左下角和右上角围成的),问其能否组合成一个完美的矩形(刚刚好,不多,不少,不交叉重复)。
核心思想就是:能够正好围成一个矩形的情况就是:
有且只有:
- 最左下/最左上/最右下/最右上的四个点只出现过一次,其他肯定是出现两次和四次(保证完全覆盖)
- 上面四个点围成的面积,正好等于所有子矩形的面积之和(保证不重复)
Leetcode代码收录,求粉求星星。
class Solution(object):def isRectangleCover(self, rectangles):""":type rectangles: List[List[int]]:rtype: bool"""def recordCorner(point):if point in corners:corners[point] += 1else:corners[point] = 1corners = {}area = 0left = min(x[0] for x in rectangles)bottom = min(x[1] for x in rectangles)right = max(x[2] for x in rectangles)top = max(x[3] for x in rectangles)for sub in rectangles:ax, ay, bx, by = sub[:]area += (bx-ax)*(by-ay)map(recordCorner, [(ax, ay), (bx, by), (ax, by), (bx, ay)])if area != (top-bottom)*(right-left): return Falsebig_four = [(left,bottom),(right,top),(left,top),(right,bottom)]for bf in big_four: # check corners of big rectangleif bf not in corners or corners[bf] != 1:return Falsefor key in corners: # check existing "inner" pointsif corners[key]%2 and key not in big_four:return Falsereturn True
这篇关于Leetcode 391. Perfect Rectangle的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!