ກໍ່ສ້າງວິທີແກ້ໄຂ Leetcode


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຄະນິດສາດ

ບັນຫາການກໍ່ສ້າງ 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

ບັນຫາການກໍ່ສ້າງ Rectangle Leetcode Solution ຂໍໃຫ້ພວກເຮົາຊອກຫາຂະ ໜາດ ທີ່ ເໝາະ ສົມຂອງ ໜ້າ ເວບໄຊທ໌ດ້ວຍບາງພື້ນທີ່ທີ່ ກຳ ນົດໄວ້ກ່ອນ. ຂະ ໜາດ ໜ້າ ເວບໄຊທ໌ຄວນຕອບສະ ໜອງ ຂໍ້ ຈຳ ກັດທີ່ວາງໄວ້. ຂໍ້ ຈຳ ກັດສາມຢ່າງຄື: ຄວາມຍາວຕ້ອງສູງກວ່າຫຼືເທົ່າກັບຄວາມກວ້າງຂອງ ໜ້າ ເວບ, ພື້ນທີ່ຂອງ ໜ້າ ເວບໄຊທ໌ທີ່ອອກແບບຕ້ອງມີຄວາມເທົ່າທຽມກັນກັບພື້ນທີ່ທີ່ ກຳ ນົດໄວ້, ຄວາມແຕກຕ່າງລະຫວ່າງຄວາມຍາວແລະຄວາມກວ້າງຈະຕ້ອງມີ ຕຳ ່ສຸດ. ພວກເຮົາສາມາດຊອກຫາຊຸດຂອງຂະ ໜາດ ທີ່ສາມາດຕອບສະ ໜອງ ຂໍ້ ຈຳ ກັດຕ່າງໆໄດ້ຢ່າງງ່າຍດາຍໂດຍການພຽງແຕ່ລວບລວມເລກເຕັມຈາກ 1 ຫາຮາກສີ່ຫລ່ຽມຂອງພື້ນທີ່ດັ່ງກ່າວ. ພວກເຮົາສືບຕໍ່ກວດເບິ່ງວ່າຕົວເລກປະຈຸບັນແບ່ງເຂດບໍລິເວນ. ຖ້າມັນເຮັດ, ພວກເຮົາກວດເບິ່ງວ່າຄວາມແຕກຕ່າງລະຫວ່າງຄູ່ຮ່ວມງານຂອງມັນ (ຕົວເລກທີ່ໄດ້ຮັບໂດຍການແບ່ງພື້ນທີ່ໂດຍ ຈຳ ນວນປະຈຸບັນ) ມີຄວາມແຕກຕ່າງ ໜ້ອຍ ກ່ວາທີ່ ກຳ ນົດໄວ້ໃນປະຈຸບັນ. ຖ້າທຸກເງື່ອນໄຂຖືກຕອບສະ ໜອງ, ພວກເຮົາປັບປຸງ ຄຳ ຕອບ.

ໃນເບື້ອງຕົ້ນ, ພວກເຮົາຕັ້ງ ຄຳ ຕອບໃຫ້ເປັນ areax1, ເນື່ອງຈາກວ່າມັນພໍໃຈກັບຂໍ້ ຈຳ ກັດດັ່ງກ່າວ. ແລະໃນທາງແກ້ໄຂ, ພວກເຮົາພະຍາຍາມຊອກຫາຊຸດທີ່ດີກວ່າທີ່ມີຄວາມແຕກຕ່າງ ໜ້ອຍ ກວ່າລະຫວ່າງພວກມັນ. ໃນທີ່ສຸດ, ພວກເຮົາສົ່ງຄືນຂະ ໜາດ ເປັນ array.

ລະຫັດ ສຳ ລັບການກໍ່ສ້າງວິທີແກ້ໄຂຮູບສີ່ຫລ່ຽມ 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 Code

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), ເນື່ອງຈາກວ່າພວກເຮົາໄດ້ໃຊ້ພຽງແຕ່ຕົວແປທີ່ຄົງທີ່ເທົ່ານັ້ນ. ຄວາມສັບສົນຂອງພື້ນທີ່ແມ່ນຍັງຄົງທີ່.