សាងសង់ដំណោះស្រាយចតុកោណ Leetcode


កម្រិតលំបាក មានភាពងាយស្រួល
គណិតវិទ្យា

បញ្ហាបង្កើតដំណោះស្រាយចតុកោណ Leetcode បញ្ជាក់ថាអ្នកជាអ្នករចនាគេហទំព័រ។ ហើយអ្នកត្រូវបានផ្តល់ភារកិច្ចឱ្យរចនាគេហទំព័រជាមួយតំបន់ដែលបានកំណត់ជាមុន។ មានឧបសគ្គមួយចំនួនដែលត្រូវបានដាក់លើការរចនា។ ប្រវែងនៃទំព័រវែបសាយត្រូវការធំជាងឬស្មើនឹងទទឹងរបស់គេហទំព័រតំបន់នៃគេហទំព័រដែលត្រូវបានរចនាត្រូវតែស្មើនឹងតំបន់ដែលបានផ្តល់។ ចុងក្រោយភាពខុសគ្នារវាងប្រវែងនិងទទឹងគួរតែតូចបំផុតតាមដែលអាចធ្វើទៅបាន។ ដូច្នេះសូមក្រឡេកមើលឧទាហរណ៍មួយចំនួនមុនពេលមុជជ្រៅទៅក្នុងការដោះស្រាយបញ្ហា។

សាងសង់ដំណោះស្រាយចតុកោណ Leetcode

area = 4
[2,2]

ការពន្យល់ៈប្រវែងនិងទទឹងរបស់គេហទំព័រដែលមានផ្ទៃដីស្មើនឹង ៤ អាចជា ១ × ៤ ឬ ២ × ២ ។ ប៉ុន្តែដោយសារយើងត្រូវរកប្រវែងនិងទទឹងដូចជាវាមានភាពខុសគ្នាអប្បបរមារវាងពួកវា។ វាជាការល្អប្រសើរជាងមុនក្នុងការជ្រើសរើសទំហំ 4 × 1 ។ វិមាត្រ 4 × 2 ក៏ធ្វើតាមផងដែរថាប្រវែងធំជាងឬស្មើទទឹងទំព័រ។

area = 23
[23, 1]

ការពន្យល់ៈអ្នកអាចមានគេហទំព័រតែ ២ ប៉ុណ្ណោះដែលមានផ្ទៃដី = ២៣។ អ្នកអាចមានវិមាត្រ ២៣ × ១ ឬ ១ × ២៣ ។ ចាប់តាំងពីគេហទំព័រដែលមានវិមាត្រ 23 × 23 រំលោភលើលក្ខខណ្ឌដំបូងរបស់យើង។ យើងអាចមានគេហទំព័រដែលមានទំហំ ២៣ × ១ ប៉ុណ្ណោះ។

វិធីសាស្រ្តសម្រាប់សាងសង់ដំណោះស្រាយចតុកោណ Leetcode

បញ្ហាសាងសង់ដំណោះស្រាយចតុកោណ Leetcode ស្នើឱ្យយើងស្វែងរកទំហំសមស្របនៃគេហទំព័រជាមួយនឹងតំបន់ដែលបានកំណត់ជាមុន។ វិមាត្រទំព័រគេហទំព័រគួរតែពេញចិត្តចំពោះឧបសគ្គដែលបានដាក់។ ឧបសគ្គទាំងបីគឺៈប្រវែងត្រូវតែធំជាងឬស្មើនឹងទទឹងរបស់គេហទំព័រគេហទំព័រតំបន់នៃគេហទំព័រដែលត្រូវបានរចនាឡើងត្រូវតែស្មើនឹងតំបន់ដែលបានផ្តល់ឱ្យនោះភាពខុសគ្នារវាងប្រវែងនិងទទឹងត្រូវតែតិចបំផុត។ យើងអាចរកឃើញសំណុំវិមាត្រយ៉ាងងាយស្រួលដែលអាចបំពេញតាមឧបសគ្គដែលបានផ្តល់ឱ្យដោយគ្រាន់តែសង្កត់លើចំនួនគត់ពី ១ ដល់ឫសការេនៃផ្ទៃដែលបានផ្តល់។ យើងបន្តពិនិត្យមើលថាតើចំនួនគត់បច្ចុប្បន្នបែងចែកតំបន់។ ប្រសិនបើវាកើតឡើងយើងពិនិត្យមើលថាតើភាពខុសគ្នារវាងសមភាគីរបស់វា (កូតាដែលទទួលបានដោយបែងចែកតំបន់ដែលបានផ្តល់ឱ្យដោយចំនួនគត់បច្ចុប្បន្ន) មានភាពខុសគ្នាតិចជាងសំណុំបច្ចុប្បន្ន។ ប្រសិនបើលក្ខខណ្ឌទាំងអស់ត្រូវបានឆ្លើយតបយើងធ្វើបច្ចុប្បន្នភាពចម្លើយ។

ដំបូងយើងកំណត់ចម្លើយជា areax1 ព្រោះវាតែងតែពេញចិត្តនឹងឧបសគ្គដែលបានផ្តល់ឱ្យ។ ហើយនៅក្នុងដំណោះស្រាយយើងព្យាយាមរកសំណុំល្អប្រសើរជាងមុនដែលមានភាពខុសគ្នាតិចជាងរវាងពួកគេ។ នៅទីបញ្ចប់យើងត្រឡប់វិមាត្រជាក អារេ.

លេខកូដសំរាប់សាងសង់ដំណោះស្រាយចតុកោណឡេឡេតកូដ

លេខកូដ 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 ជាកន្លែងដែលត្រូវបានផ្តល់ជូនអ្នកប្រើប្រាស់។ ចាប់តាំងពីយើងបានព្យាយាមស្វែងរកអ្នកបែងចែកទាំងអស់នៃតំបន់ដែលបានផ្តល់ឱ្យរហូតដល់ឫសការ៉េរបស់វាដូច្នេះភាពស្មុគស្មាញពេលវេលាគឺជាឫសការ៉េនៃការបញ្ចូល។

ភាពស្មុគស្មាញនៃលំហ

ឱ (១)ចាប់តាំងពីយើងបានប្រើតែអថេរថេរ។ ភាពស្មុគស្មាញនៃលំហក៏មានថេរដែរ។