Rectangle Leetcode 솔루션 생성


난이도 쉽게
수학

Rectangle Leetcode 솔루션 구성 문제는 귀하가 웹 디자이너라고 말합니다. 그리고 미리 정의 된 영역이있는 웹 페이지를 디자인하는 작업이 주어집니다. 디자인에는 몇 가지 제약이 있습니다. 웹 페이지의 길이는 웹 페이지의 너비보다 크거나 같아야하며 디자인 된 웹 페이지의 영역은 주어진 영역과 같아야합니다. 마지막으로 길이와 너비의 차이는 가능한 한 작아야합니다. 따라서 문제 해결에 깊이 뛰어 들기 전에 몇 가지 예를 살펴 보겠습니다.

Rectangle Leetcode 솔루션 생성

area = 4
[2,2]

설명 : 영역이 4 인 웹 페이지의 길이와 너비는 1 × 4 또는 2 × 2가 될 수 있습니다. 그러나 우리는 길이와 너비가 최소한의 차이를 갖도록 찾을 필요가 있기 때문입니다. 2 × 2 치수를 선택하는 것이 좋습니다. 2 × 2 치수는 또한 길이가 페이지 너비보다 크거나 같음을 따릅니다.

area = 23
[23, 1]

설명 : 면적이 23 인 웹 페이지는 두 개만 가질 수 있습니다. 크기는 23x1 또는 1x23 일 수 있습니다. 크기가 1x23 인 웹 페이지가 첫 번째 조건을 위반하기 때문입니다. 23 × 1 크기의 웹 페이지 만 가질 수 있습니다.

Rectangle Leetcode 솔루션 생성 방법

Rectangle Leetcode 솔루션 구성 문제는 미리 정의 된 영역이있는 웹 페이지의 적절한 크기를 찾도록 요청합니다. 웹 페이지 크기는 부과 된 제약 조건을 충족해야합니다. 세 가지 제약은 다음과 같습니다. 길이는 웹 페이지의 너비보다 크거나 같아야하며, 디자인 된 웹 페이지의 영역은 주어진 영역과 같아야하며, 길이와 너비의 차이는 최소 여야합니다. 1에서 주어진 영역의 제곱근까지의 정수를 간단히 반복하여 주어진 제약 조건을 충족하는 차원 집합을 쉽게 찾을 수 있습니다. 현재 정수가 면적을 나누는 지 계속 확인합니다. 만약 그렇다면, 우리는 상대방 (주어진 면적을 현재 정수로 나누어받은 몫)의 차이가 현재 세트보다 차이가 적은지 확인합니다. 모든 조건이 충족되면 답변을 업데이트합니다.

처음에는 주어진 제약 조건을 항상 충족하므로 대답을 areax1로 설정합니다. 그리고 솔루션에서 우리는 그들 사이의 차이가 적은 더 나은 세트를 찾으려고 노력합니다. 결국, 우리는 차원을 정렬.

Rectangle 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

자바 코드

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), 상수 변수 만 사용했기 때문입니다. 공간 복잡성도 일정합니다.