🔒Открыть пост
и посмотреть медиа
и посмотреть медиа
Задача: 976. Largest Perimeter Triangle
Сложность: easy
Дан целочисленный массив nums. Верните наибольший периметр треугольника с ненулевой площадью, образованный из трех этих длин. Если невозможно образовать треугольник с ненулевой площадью, верните 0.
Пример:
Input: nums = [1,2,1,10]
Output: 0
Explanation:
You cannot use the side lengths 1, 1, and 2 to form a triangle.
You cannot use the side lengths 1, 1, and 10 to form a triangle.
You cannot use the side lengths 1, 2, and 10 to form a triangle.
As we cannot use any three side lengths to form a triangle of non-zero area, we return 0.
👨💻 Алгоритм:
1⃣Отсортируйте массив nums в порядке возрастания.
2⃣Для каждого элемента c в массиве, начиная с конца: Выберите два наибольших возможных значения a и b, которые находятся перед c в отсортированном массиве (т.е. значения, смежные с c). Проверьте, образуют ли a, b и c треугольник (условие треугольника: a + b > c). Если образуют, верните их сумму как периметр треугольника.
3⃣Если не удалось найти такие значения, верните 0.
😎 Решение:
public class Solution {
public int LargestPerimeter(int[] A) {
Array.Sort(A);
for (int i = A.Length - 3; i >= 0; --i)
if (A[i] + A[i + 1] > A[i + 2])
return A[i] + A[i + 1] + A[i + 2];
return 0;
}
}
Ставь 👍 и забирай 📚 Базу знаний