1、 84. 柱状图中最大的矩形
2、 85. 最大矩形
3、 223. 矩形面积
4、 302. 包含全部黑色像素的最小矩形
5、 304. 二维区域和检索 - 矩阵不可变
6、 308. 二维区域和检索 - 可变
7、 363. 矩形区域不超过 K 的最大数值和
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])
9、 391. 完美矩形
10、 492. 构造矩形
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. 单词矩阵
