構造矩形Leetcode解決方案


難度級別 容易獎學金
數學

問題“構建矩形Leetcode解決方案”表明您是Web設計人員。 您將獲得一個任務,以設計一個具有一些預定義區域的網頁。 在設計上有一些限制。 網頁的長度必須大於或等於網頁的寬度,設計的網頁的面積必須等於給定的面積。 最後但並非最不重要的是,長度和寬度之間的差異應盡可能小。 因此,在深入研究解決問題之前,讓我們看一些示例。

構造矩形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),因為我們僅使用了常量變量。 空間複雜度也是恆定的。