Периметрдің үшбұрышының ең үлкен шешімі


Күрделілік дәрежесі оңай
Жиі кіреді C3 IoT
математика Сұрыптау

Проблеманы шешу

Мәселеде »Ең үлкені Периметрі Үшбұрыш »n мәні бар жиым берілген. Барлық мәндер оң сандар болып табылады. Сұрақ үшбұрыштың осы шамалардан тұрғыза алатын максималды периметрін табуды сұрайды. Егер үшбұрыш салу мүмкін болмаса, онда 0 санын шығару керек.

мысал

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

Түсіндіру: Осы мәндерді пайдаланып құруға болатын үшбұрыштың ең үлкен периметрі - 10, ал үшбұрыштардың қабырғалары - 4,3,3.

Периметрдің ең үлкен үшбұрышының Leetcode шешіміне арналған тәсіл

Бұл негізгі математикалық проблема. Сондықтан оны шешу үшін үшбұрышта кез-келген екі жақтың ұзындығының қосындысы әрқашан үшінші жақтан үлкен болатыны туралы теореманы білуіміз керек. Әйтпесе, олар үшбұрыш құра алмайды. Үшбұрыштың қабырғалары деп айтайық а, б және с. Суреттер осы теореманы қанағаттандырмаса, үшбұрышты қалай құруға болмайтынын көрсетеді.

периметрдің ең үлкен үшбұрышына дейінгі 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

Ең үлкен периметр үшбұрышының кодтық шешімінің күрделілігін талдау

Уақыт күрделілігі

Жоғарыда келтірілген кодтың уақыт күрделілігі O (nlogn) өйткені біз массивті сұрыптап жатырмыз. Мұнда n - массивтің өлшемі.

Ғарыштың күрделілігі

Жоғарыда аталған кодтың кеңістігінің күрделілігі мынада O (1) өйткені біз жауапты сақтау үшін айнымалыны ғана қолданамыз.

Әдебиеттер тізімі