LeetCode 几何算法题解：223-矩形面积
大家好，我是前端西瓜哥。
一年多没做 LeetCode 算法题了，最近在 LeetCode 发现可以筛选出有 “几何” 标签的算法题，有个几十道题。
为了提高开发图形编辑器的需要的算法水平，我就打算出个新的系列，写点 LeetCode 算法题的题解。
当然是几何、矩阵相关，因为比较血压高。
平时开发图形编辑器其实也是类似的，一些需求最后还是会抽象成一道道算法题，然后开始做 LeetCode 一样去解题，不同的地方就是做着做着题目可能会调整，没有提供太多基础算法 API，以及没有太全的测试用例。
LeetCode 测试用例很完善，而且在这里你将看到各种花里胡哨的需求，拿来提升自己的算法解题能力还是不错的。
题目描述
平台：LeetCode（223题），难度中等。
给你 二维 平面上两个 由直线构成且边与坐标轴平行/垂直 的矩形，请你计算并返回两个矩形覆盖的总面积。
每个矩形由其 左下 顶点和 右上 顶点坐标表示：
- 第一个矩形由其左下顶点
(ax1, ay1)和右上顶点(ax2, ay2)定义。 - 第二个矩形由其左下顶点
(bx1, by1)和右上顶点(bx2, by2)定义。
示例 1：
输入：ax1 = -3, ay1 = 0, ax2 = 3, ay2 = 4, bx1 = 0, by1 = -1, bx2 = 9, by2 = 2
输出：45
示例 2：
输入：ax1 = -2, ay1 = -2, ax2 = 2, ay2 = 2, bx1 = -2, by1 = -2, bx2 = 2, by2 = 2
输出：16
提示：
-10^4 <= ax1, ay1, ax2, ay2, bx1, by1, bx2, by2 <= 10^4
函数签名为：
function computeArea(
// 矩形 1
ax1: number, // 左下点
ay1: number,
ax2: number, // 右上点
ay2: number,
// 矩形 2
bx1: number,
by1: number,
bx2: number,
by2: number
): number {
}
题解
简单来说，就是求两个矩形的布尔并集后的面积。
这里的矩形比较简单，用左下点和右上点表达，不带旋转。
看图其实很容易理解：所求面积 = 两个矩形的面积 - 重叠面积。
我的解法是：
- 求出两个矩形面积，得到它们的和；
- 判断两矩形是否重叠，如果没重叠，直接返回两个矩形面积之和；
- 如果重叠，计算重叠矩形面积，然后返回两矩形面积之和减去重叠矩形面积的值；
function computeArea(
// 矩形 1
ax1: number, // 左下点
ay1: number,
ax2: number, // 右上点
ay2: number,
// 矩形 2
bx1: number,
by1: number,
bx2: number,
by2: number
): number {
const rect1Area = (ax2 - ax1) * (ay2 - ay1);
const rect2Area = (bx2 - bx1) * (by2 - by1);
let area = rect1Area + rect2Area;
// 矩形 1 和 矩形 2 是否相交
if (bx1 < ax2 && bx2 > ax1 && by1 < ay2 && by2 > ay1) {
// 相交了，对所有点的 x 值排序，取中间两点的长度，该长度为重叠矩形的宽。
// y 同理
const xArr = [ax1, ax2, bx1, bx2].sort((a, b) => a - b);
const yArr = [ay1, ay2, by1, by2].sort((a, b) => a - b);
const overlap = (xArr[2] - xArr[1]) * (yArr[2] - yArr[1]);
area -= overlap;
}
// 不相交，没有重叠区域
return area;
}
刚好这里用到了广泛使用的 经典的矩形碰撞算法，我们可以回顾一下：
看了下 LeetCode 的官方题解，更简练些，看起来我的算法还能优化一下，不过整体思路差不多。
官方题解把是否相交和求重叠区域的宽高的逻辑写在一起了，实在是优雅。
const overlapWidth = Math.max(
Math.min(ax2, bx2) - Math.max(ax1, bx1),
0
)结尾
做这种几何题，一个特点是，变量通常很多，解题时容易眼花写错变量，这个要注意。
本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2024-07-13，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
