მართკუთხედის Leetcode ამოხსნის აგება


Რთული ტური Easy
მათემატიკის

პრობლემა აშენების მართკუთხედი 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

ჯავის კოდი

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 (კვადრატი (N)), სადაც N არის მომხმარებლისთვის მიწოდებული ტერიტორია. მას შემდეგ, რაც ჩვენ შევეცადეთ მოვნახეთ მოცემული ფართობის ყველა გამყოფი მის კვადრატულ ფესვამდე, ამიტომ დროის სირთულე არის შეყვანის კვადრატული ფესვი.

სივრცის სირთულე

O (1)რადგან ჩვენ გამოვიყენეთ მხოლოდ მუდმივი ცვლადები. სივრცის სირთულე ასევე მუდმივია.