大家好,我是前端西瓜哥。
一年多没做 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
)
做这种几何题,一个特点是,变量通常很多,解题时容易眼花写错变量,这个要注意。