构造矩形Leetcode解决方案


难度级别 易得奖学金
数学

问题“构建矩形Leetcode解决方案”表明您是网页设计师。 您将获得一个任务,以设计一个具有一些预定义区域的网页。 在设计上有一些限制。 网页的长度必须大于或等于网页的宽度,设计的网页的面积必须等于给定的面积。 最后但并非最不重要的是,长度和宽度之间的差异应尽可能小。 因此,在深入研究解决问题之前,让我们看一些示例。

构造矩形Leetcode解决方案

area = 4
[2,2]

说明:面积等于4的网页的长度和宽度可以是1×4或2×2。 但是,由于我们需要找到长度和宽度,以使它们之间的差异最小。 最好选择2×2尺寸。 2×2尺寸也遵循这样的原则,即长度大于或等于页面的宽度。

area = 23
[23, 1]

说明:您只能有两个面积为23的网页。尺寸可以为23×1或1×23。 由于尺寸为1×23的网页违反了我们的第一个条件。 我们只能拥有大小为23×1的网页。

矩形Leetcode解决方案的构造方法

问题“构建矩形Leetcode解决方案”要求我们找出带有一些预定义区域的网页的合适大小。 网页尺寸应满足施加的约束。 这三个约束是:长度必须大于或等于网页的宽度,设计的网页的面积必须等于给定的面积,长度和宽度之间的差必须最小。 通过简单地从1到给定区域的平方根的整数循环,我们可以轻松找到满足给定约束的一组尺寸。 我们一直在检查当前整数是否将面积除。 如果是这样,我们将检查其对应对象之间的差(通过将给定面积除以当前整数而得到的商)的差是否小于当前集合的差。 如果满足所有条件,我们将更新答案。

最初,我们将答案设置为areax1,因为它始终满足给定的约束。 在解决方案中,我们试图找到一个更好的集合,它们之间的差异较小。 最后,我们将尺寸返回为 排列.

构造矩形Leetcode解决方案的代码

C ++代码

#include <bits/stdc++.h>
using namespace std;

vector<int> constructRectangle(int area) {
    vector<int> ans({area, 1});
    for(int i=1;i*i<=area;i++){
        if(area%i == 0 && (area/i - i)<(ans[0] - ans[1]))
            ans[0] = area/i, ans[1] = i;
    }
    return ans;
}

int main(){
    vector<int> ans = constructRectangle(4);
    cout<<ans[0]<<", "<<ans[1];
}
2, 2

Java代码

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
    public static int[] constructRectangle(int area) {
        int[] ans = {area, 1};
        for(int i=1;i*i<=area;i++){
            if(area%i == 0 && (area/i - i)<(ans[0] - ans[1])){
                ans[0] = area/i;
                ans[1] = i;
            }
        }
        return ans;
    }
    
  public static void main (String[] args) throws java.lang.Exception{
    int[] ans = constructRectangle(4);
    
    System.out.println(ans[0] + ", " + ans[1]);
  }
}
2, 2

复杂度分析

时间复杂度

O(sqrt(N)), 其中N是提供给用户的区域。 由于我们试图找到给定区域的所有除数直到其平方根,因此时间复杂度是输入的平方根。

空间复杂度

O(1),因为我们仅使用了常量变量。 空间复杂度也是恒定的。