Периметрийн хамгийн том гурвалжин Leetcode шийдэл


Хэцүү байдлын түвшин Easy
Байнга асуудаг C3 IoT
Математик Ангилах

Асуудлын мэдэгдэл

Асуудлын дотор ”Хамгийн том нь Периметр Гурвалжин ”гэж бидэнд n утга бүхий массивыг өгдөг. Бүх утга нь эерэг бүхэл тоонууд юм. Эдгээр утгуудаас бидний барьж чадах гурвалжны хамгийн дээд периметрийг олохыг хүсч байна. Хэрэв гурвалжинг бүтээх боломжгүй бол бид 0-ийг хэвлэх хэрэгтэй.

Жишээ нь

arr = [3,2,3,4]
10

Тайлбар: Эдгээр утгыг ашиглан үүсч болох гурвалжны хамгийн том периметр нь 10, гурвалжны талууд нь 4,3,3 байна.

Хамгийн том периметрийн гурвалжингийн Leetcode шийдлийн арга

Энэ бол математикийн үндсэн асуудал юм. Тиймээс үүнийг шийдэхийн тулд аль ч талын уртын гурвалжингийн нийлбэр нь гурав дахь талаасаа үргэлж их байдаг гэсэн теоремыг мэдэх ёстой. Үгүй бол тэд гурвалжин үүсгэхгүй. Гурвалжны талууд нь гэж хэлье a, b, c. Зураг дээр энэ теоремыг хангаагүй тохиолдолд гурвалжин байгуулах боломжгүй байгааг харуулж байна.

leetcode шийдэл нь хамгийн том периметрийн гурвалжин

Асуулт хамгийн том периметрийн гурвалжинг олохыг шаардаж байгаа тул a + b> c, b + c> a, a + c> b нөхцлийг хангасан бүх гурвалсан гурвалаас бид a + гэсэн гурвалсан гурвыг олох хэрэгтэй. b + c хамгийн их байна.

Тиймээс бид хамгийн том периметрийг авахын тулд a, b, c гэсэн утгыг аль болох их хүсч байна. Бид массивыг эрэмбэлж, хэрэв теоремд нийцсэн бол хамгийн том гурван утгыг эхлүүлнэ. Хэрэв тэгвэл тэдгээрийн нийлбэр нь шаардлагатай утга болно. өөр тохиолдолд бид дараагийн гурван хамгийн том утгыг шалгах болно.

хэрэв ийм гурвалсан гурвалжин байхгүй бол гурвалжны хамгийн том периметр нь 0 байна.

 Хэрэгжүүлэх

Хамгийн том периметрийн гурвалжингийн C ++ код

#include <bits/stdc++.h> 
using namespace std; 
    int largestPerimeter(vector<int>&  arr) {
        int n=arr.size();
        sort(arr.begin(),arr.end());
       for (int i =n - 1; i > 1; --i)
            if (arr[i] < arr[i - 1] + arr[i - 2])
                return arr[i] + arr[i - 1] + arr[i - 2];
        return 0;
    }
int main() 
{ 
 vector<int> arr = { 3,2,3,4 }; 
 cout<<largestPerimeter(arr)<<endl; 
 return 0;
}
10

Хамгийн том периметрийн гурвалжингийн Java код

import java.util.Arrays; 
public class Tutorialcup {
    public static int largestPerimeter(int[] arr) {
        Arrays.sort(arr);
        int n= arr.length;
        for (int i =n - 1; i > 1; --i)
            if (arr[i] < arr[i - 1] + arr[i - 2])
                return arr[i] + arr[i - 1] + arr[i - 2];
        return 0;
    }
  public static void main(String[] args) {
    int [] arr = {3,2,3,4}; 
    int ans= largestPerimeter(arr);
    System.out.println(ans);
  }
}

 

10

Хамгийн том периметрийн гурвалжингийн Leetcode шийдлийн нарийн төвөгтэй байдлын шинжилгээ

Цаг хугацааны нарийн төвөгтэй байдал

Дээрх кодын цаг хугацааны нарийн төвөгтэй байдал нь O (nlogn) Учир нь бид массивыг ангилж байна. Энд n нь массивын хэмжээ юм.

Сансрын нарийн төвөгтэй байдал

Дээрх кодын орон зайн нарийн төвөгтэй байдал нь O (1) Учир нь бид хариултыг хадгалахын тулд зөвхөн хувьсагч ашиглаж байна.

Ашигласан материал