LeetCode 492题 “Construct the Rectangle” 是一个数学问题，要求我们为一个给定的面积找到最接近的矩形尺寸（长和宽）。具体来说，我们需要找到一个矩形的长度 L 和宽度 W，使得 L * W = area，并且 L 和 W 的差值尽可能小。
题目描述
给定一个整数 area，找到三个整数 L 和 W，使得：
- L * W = area
- L >= W
- L 和 W 的差值尽可能小
示例
输入: area = 4
输出: [2, 2]
解释: 2 * 2 = 4 且 2 - 2 = 0，差值最小。
输入: area = 37 输出: [37, 1] 解释: 37 * 1 = 37 且 37 - 1 = 36，这是唯一可能的组合。
解题思路
- 从平方根开始：为了使 L 和 W 的差值尽可能小，我们可以从
sqrt(area)开始向下查找。因为平方根处的值是最接近的两个因数。 - 遍历因数：从
sqrt(area)开始向下遍历，找到第一个能整除area的数，这个数作为宽度 W，对应的商作为长度 L。 - 返回结果：返回
[L, W]。
代码实现
以下是 Python 的实现代码：
import math
def constructRectangle(area):
从平方根开始向下遍历
for w in range(int(math.sqrt(area)), 0, -1):
if area % w == 0:
return [area // w, w]示例
print(constructRectangle(4)) # 输出: [2, 2] print(constructRectangle(37)) # 输出: [37, 1]
详细解释
- 导入 math 库：用于计算平方根。
- 遍历范围：
range(int(math.sqrt(area)), 0, -1)从sqrt(area)向下遍历到 1。 - 判断整除：
if area % w == 0检查当前宽度w是否能整除area。 - 返回结果：如果找到符合条件的宽度
w，则返回[area // w, w]，其中area // w是长度 L。
复杂度分析
- 时间复杂度：O(sqrt(area))，因为我们最多遍历到
sqrt(area)。 - 空间复杂度：O(1)，只使用了常数级别的额外空间。
这种方法高效且直观，能够很好地解决题目要求。希望这个解释对你有帮助！如果有其他问题，欢迎继续提问。
发表回复