Leetcode

Leetcode

Leetcode

class Solution:     def computeArea(self, ax1: int, ay1: int, ax2: int, ay2: int, bx1: int, by1: int, bx2: int, by2: int) -> int:         a = (ax1 - ax2) * (ay1 - ay2)         b = (bx2 - bx1) * (by2 - by1)          w = min(ax2, bx2) - max(ax1, bx1)         h = min(ay2, by2) - max(ay1, by1)         c = max(w, 0) * max(h, 0)                  return a   b - c 

Leetcode

class Solution:     def isRectangleCover(self, rectangles: List[List[int]]) -> bool:       
        minx, miny, maxx, maxy = rectangles[0]
        area, cnt = 0, defaultdict(int)
        for rec in rectangles:
            x, y, a, b = rec
            minx, miny, maxx, maxy = min(minx, x), min(miny, y), max(maxx, a), max(maxy, b)
            area += (a - x) * (b - y)
            cnt[(x, y)] += 1
            cnt[(x, b)] += 1
            cnt[(a, y)] += 1
            cnt[(a, b)] += 1
        
        if area != (maxx - minx) * (maxy - miny):
            return False

        for i in [(minx, miny), (minx, maxy), (maxx, miny), (maxx, maxy)]:
            if cnt[i] != 1: return False
            del cnt[i]
            
        for i in cnt:
            if cnt[i] not in [2,4]:
                return False
        
        return True

统计唯一顶点，如果只有 4 个，且围成的矩形面积正好等于累加的面积返回真。

class Solution:
    def isRectangleCover(self, rectangles: List[List[int]]) -> bool:  
        area, p = 0, set()
        for x, y, a, b in rectangles:
            area += (a - x) * (b - y)
            p ^= { 
        (x, y),(x, b),(a, y),(a, b)}
            # p.symmetric_difference_update()
            
        p = sorted(p)

        return len(p) == 4 and area == (p[-1][0] - p[0][0]) * (p[-1][1] - p[0][1]) 

Leetcode

∵ L * W = area 且 L >= W ∴ W * W <= area
贪心地求得 W 的最大值，L 和 W 之间的差距尽可能小，同时又等于 area。
w 最大是 int(sqrt(area))，找到第一个能够整除 area 的那个值即可。

class Solution:
    def constructRectangle(self, area: int) -> List[int]:
        ''' w = 1 for i in range(1, int(area**0.5)+1): if area % i == 0: w = i '''
        w = int(area ** 0.5)
        while area % w: w -= 1          
            
        return [area//w, w]

11、 497. 非重叠矩形中的随机点

12、 499. 迷宫 III

13、 505. 迷宫 II

14、 554. 砖墙

15、 750. 角矩形的数量

16、 807. 保持城市天际线

17、 836. 矩形重叠

18、 850. 矩形面积 II

19、 939. 最小面积矩形

20、 963. 最小面积矩形 II

21、 1001. 网格照明

22、 1274. 矩形内船只的数目

23、 1401. 圆和矩形是否有重叠

24、 1444. 切披萨的方案数

25、 1459. 矩形面积

26、 1465. 切割后面积最大的蛋糕

27、 1476. 子矩形查询

28、 1504. 统计全 1 子矩形

29、 1591. 奇怪的打印机 II

30、 1725. 可以形成最大正方形的矩形数目

31、 1727. 重新排列后的最大子矩阵

32、 1958. 检查操作是否合法

33、 1992. 找到所有的农场组

34、 2001. 可互换矩形的组数

35、 LCP 27. 黑盒光线反射

36、 LCP 37. 最小矩形面积

37、 LCP 49. 环形闯关游戏

38、 剑指 Offer 12. 矩阵中的路径

39、 剑指 Offer 29. 顺时针打印矩阵

40、 剑指 Offer II 013. 二维子矩阵的和

41、 剑指 Offer II 039. 直方图最大矩形面积

42、 剑指 Offer II 040. 矩阵中最大的矩形

43、 剑指 Offer II 090. 环形房屋偷盗

44、 剑指 Offer II 100. 三角形中最小路径之和

45、 剑指 Offer II 107. 矩阵中的距离

46、 面试题 16.22. 兰顿蚂蚁

47、 面试题 17.25. 单词矩阵