بناء الحل Leetcode المستطيل


مستوى الصعوبة سهل
الرياضيات

تنص المشكلة Construct the Rectangle 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 المستطيل

تطلب منا مشكلة Construct the Rectangle 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 (sqrt (N)) ، حيث N هي المنطقة المقدمة للمستخدم. نظرًا لأننا حاولنا إيجاد جميع قواسم المنطقة المحددة حتى الجذر التربيعي لها ، فإن التعقيد الزمني هو الجذر التربيعي للمدخل.

تعقيد الفضاء

يا (1)، لأننا استخدمنا المتغيرات الثابتة فقط. التعقيد المكاني ثابت أيضًا.