Leetcode шешімінің тікбұрышын тұрғызыңыз


Күрделілік дәрежесі оңай
математика

Leetcode Solution тіктөртбұрышын құру мәселесі сіздің веб-дизайнер екеніңізді білдіреді. Сізге алдын-ала белгілі бір аймақпен веб-парақты жобалау тапсырмасы беріледі. Дизайнға қойылған кейбір шектеулер бар. Веб-парақтың ұзындығы веб-беттің еніне үлкен немесе тең болуы керек, жобаланған веб-беттің ауданы берілген аймаққа тең болуы керек. Ең соңында, бірақ ұзындығы мен ені арасындағы айырмашылық мүмкіндігінше аз болуы керек. Мәселен, мәселені шешуге терең сүңгуден бұрын бірнеше мысалға тоқталайық.

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 Solution тіктөртбұрышын құру мәселесі бізден алдын-ала анықталған аймақпен веб-парақтың қолайлы өлшемін білуді сұрайды. Веб-парақтың өлшемдері қойылған шектеулерді қанағаттандыруы керек. Үш шектеу мыналар: ұзындық веб-беттің еніне үлкен немесе тең болуы керек, жобаланған веб-беттің ауданы берілген аймаққа тең, ұзындық пен ен арасындағы айырмашылық минималды болуы керек. Берілген шектеулерді қанағаттандыратын өлшемдер жиынтығын берілген аймақтың квадрат түбіріне дейінгі 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), өйткені біз тек тұрақты айнымалыларды қолдандық. Ғарыштың күрделілігі де тұрақты.