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
二、解题思路
-
首先计算两个矩形各自的面积。对于任何一个矩形，其面积可以通过计算长和宽的乘积得到，其中长为右上顶点的x坐标减去左下顶点的x坐标，宽为右上顶点的y坐标减去左下顶点的y坐标。
-
然后计算两个矩形的重叠面积。两个矩形重叠的部分也是矩形，其左下顶点的坐标为两个矩形左下顶点坐标的x和y坐标中的较大值，右上顶点的坐标为两个矩形右上顶点坐标的x和y坐标中的较小值。重叠矩形的面积可以通过计算长和宽的乘积得到，但需要确保长和宽都大于0，否则重叠面积为0。
-
最后，将两个矩形的面积相加，再减去重叠部分的面积，即可得到两个矩形覆盖的总面积。
三、具体代码
class Solution {
public int computeArea(int ax1, int ay1, int ax2, int ay2, int bx1, int by1, int bx2, int by2) {
// 计算第一个矩形的面积
int area1 = (ax2 - ax1) * (ay2 - ay1);
// 计算第二个矩形的面积
int area2 = (bx2 - bx1) * (by2 - by1);
// 计算两个矩形重叠部分的坐标
int overlapX1 = Math.max(ax1, bx1);
int overlapY1 = Math.max(ay1, by1);
int overlapX2 = Math.min(ax2, bx2);
int overlapY2 = Math.min(ay2, by2);
// 计算重叠部分的面积
int overlapArea = 0;
if (overlapX2 > overlapX1 && overlapY2 > overlapY1) {
overlapArea = (overlapX2 - overlapX1) * (overlapY2 - overlapY1);
}
// 计算总面积
return area1 + area2 - overlapArea;
}
}
这段代码首先计算了两个矩形各自的面积，然后确定了重叠矩形的坐标，并计算了重叠面积，最后返回了两个矩形覆盖的总面积。
四、时间复杂度和空间复杂度
1. 时间复杂度
- 计算第一个矩形的面积：O(1)（常数时间）
- 计算第二个矩形的面积：O(1)（常数时间）
- 计算重叠矩形的坐标：每个坐标计算使用了Math.max和Math.min，这两个操作都是O(1)（常数时间）
- 计算重叠矩形的面积：O(1)（常数时间，只有一行判断和计算）
- 计算总面积：O(1)（常数时间）
由于上述所有操作都是常数时间的操作，且没有循环或递归结构，因此整个函数的时间复杂度为O(1)，即常数时间复杂度。
2. 空间复杂度
- 整个函数只使用了固定数量的变量（ax1, ay1, ax2, ay2, bx1, by1, bx2, by2, area1, area2, overlapX1, overlapY1, overlapX2, overlapY2, overlapArea），这些变量占用的空间不会随着输入数据的大小而改变。
- 没有使用额外的数据结构，如数组、列表或哈希表。
因此，整个函数的空间复杂度为O(1)，即常数空间复杂度。
五、总结知识点
-
基本算术运算：
- 加法（+）、减法（-）、乘法（*）：用于计算矩形的面积和重叠部分的面积。
-
Java基本数据类型：
int：用于定义整数类型的变量，存储矩形坐标和面积。
-
Java Math类：
Math.max(int a, int b)：返回两个整数中的较大值。Math.min(int a, int b)：返回两个整数中的较小值。
-
条件语句：
if语句：用于检查重叠矩形是否存在（即重叠矩形的宽度和高度是否大于0）。
-
函数定义：
public关键字：定义访问权限，表示方法可以被任何其他类访问。int：指定函数返回类型，这里返回一个整数类型的面积。- 方法名
computeArea：遵循Java命名习惯，使用驼峰命名法。 - 参数列表：方法接受8个整数类型的参数，代表两个矩形的坐标。
-
逻辑思维：
- 分析问题并确定解决方案的逻辑步骤，例如先计算两个矩形的面积，再计算重叠面积，最后计算总面积。
-
空间坐标理解：
- 理解二维平面上的矩形坐标表示，包括左下角和右上角的坐标。
-
几何知识：
- 矩形的面积计算公式：长乘以宽。
以上就是解决这个问题的详细步骤，希望能够为各位提供启发和帮助。