976.三角形的最大周长

LeetCode LeetCode 数组贪心排序

发布时间 : 2000-01-10 09:07

字数:1.4k 阅读 :

评论:

976.三角形的最大周长

976.三角形的最大周长

976.1 题目

给定由一些正数（代表长度）组成的数组 nums，返回由其中三个长度组成的、面积不为零的三角形的最大周长。如果不能形成任何面积不为零的三角形，返回 0。

示例 1：

输入：nums = [2,1,2]
输出：5
解释：你可以用三个边长组成一个三角形: 1, 2, 2。

示例 2：

输入：nums = [1,2,1,10]
输出：0
解释：你不能用边长 1, 1, 2 来组成三角形。
不能用边长 1, 1, 10 来构成三角形。
不能用边长 1、2 和 10 来构成三角形。
因为我们不能用任何三条边长来构成一个非零面积的三角形，所以我们返回 0。

提示：

3 <= nums.length <= 10^4
1 <= nums[i] <= 10^6

976.2 题解

排序 + 贪心

// 方法一：排序 + 贪心
// 对数组升序排序，从后往前遍历判断两小边之和是否大于第三边
static int LargestPerimeter1(int[] nums)
{
    // 对数组进行排序，以便于从大到小遍历
    Array.Sort(nums);

    // 从数组末尾开始遍历，因为要找到最大的周长，所以先找到最大的边长
    for (int i = nums.Length - 1; i >= 2; i--)
    {
        // 根据三角形性质判断是否能构成三角形
        if (nums[i - 2] + nums[i - 1] > nums[i])
        {
            // 如果可以构成三角形，返回周长
            return nums[i - 2] + nums[i - 1] + nums[i];
        }
    }

    // 如果无法构成三角形，返回0
    return 0;
}

三重循环暴力法，不推荐

// 方法二：三重循环暴力法，不推荐
static int LargestPerimeter2(int[] nums)
{
    // 用于存储最大周长
    int maxPerimeter = 0;

    // 遍历数组中的每个元素，作为第一条边
    for (int i = 0; i < nums.Length - 2; i++)
    {
        // 第二层循环遍历数组中剩余元素，作为第二条边
        for (int j = i + 1; j < nums.Length - 1; j++)
        {
            // 第三层循环遍历数组中剩余元素，作为第三条边
            for (int k = j + 1; k < nums.Length; k++)
            {
                // 判断是否能构成三角形
                if (IsValidTriangle(nums[i], nums[j], nums[k]))
                {
                    // 如果可以构成三角形，更新最大周长
                    maxPerimeter = Math.Max(maxPerimeter, nums[i] + nums[j] + nums[k]);
                }
            }
        }
    }

    // 返回最大周长
    return maxPerimeter;
}

// 判断是否构成三角形
static bool IsValidTriangle(int a, int b, int c)
{
    // 根据三角形性质判断是否能构成三角形
    return a + b > c && a + c > b && b + c > a;
}

976.3 代码

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main()
    {
        #region 题目

        // 给定由一些正数（代表长度）组成的数组 nums ，返回由其中三个长度组成的、面积不为零的三角形的最大周长。
        // 如果不能形成任何面积不为零的三角形，返回 0。

        // 示例 1：
        // 输入：nums = [2,1,2]
        // 输出：5
        // 解释：你可以用三个边长组成一个三角形:1 2 2。

        // 示例 2：
        // 输入：nums = [1,2,1,10]
        // 输出：0
        // 解释：
        // 你不能用边长 1,1,2 来组成三角形。
        // 不能用边长 1,1,10 来构成三角形。
        // 不能用边长 1、2 和 10 来构成三角形。
        // 因为我们不能用任何三条边长来构成一个非零面积的三角形，所以我们返回 0。

        // 提示：
        // 3 <= nums.length <= 104
        // 1 <= nums[i] <= 106

        #endregion

        #region 测试

        // 示例 1
        int[] nums1 = { 2, 1, 2 };
        int result1_1 = LargestPerimeter1(nums1);
        Console.WriteLine($"示例1 方法1 输出：{result1_1}");
        int result1_2 = LargestPerimeter2(nums1);
        Console.WriteLine($"示例1 方法2 输出：{result1_2}");

        // 示例 2
        int[] nums2 = { 1, 2, 1, 10 };
        int result2_1 = LargestPerimeter1(nums2);
        Console.WriteLine($"示例2 方法1 输出：{result2_1}");
        int result2_2 = LargestPerimeter2(nums2);
        Console.WriteLine($"示例2 方法2 输出：{result2_2}");

        #endregion
    }

    #region 答案

    // 方法一：排序 + 贪心
    // 对数组升序排序，从后往前遍历判断两小边之和是否大于第三边
    static int LargestPerimeter1(int[] nums)
    {
        // 对数组进行排序，以便于从大到小遍历
        Array.Sort(nums);

        // 从数组末尾开始遍历，因为要找到最大的周长，所以先找到最大的边长
        for (int i = nums.Length - 1; i >= 2; i--)
        {
            // 根据三角形性质判断是否能构成三角形
            if (nums[i - 2] + nums[i - 1] > nums[i])
            {
                // 如果可以构成三角形，返回周长
                return nums[i - 2] + nums[i - 1] + nums[i];
            }
        }

        // 如果无法构成三角形，返回0
        return 0;
    }

    // 方法二：三重循环暴力法，不推荐
    static int LargestPerimeter2(int[] nums)
    {
        // 用于存储最大周长
        int maxPerimeter = 0;

        // 遍历数组中的每个元素，作为第一条边
        for (int i = 0; i < nums.Length - 2; i++)
        {
            // 第二层循环遍历数组中剩余元素，作为第二条边
            for (int j = i + 1; j < nums.Length - 1; j++)
            {
                // 第三层循环遍历数组中剩余元素，作为第三条边
                for (int k = j + 1; k < nums.Length; k++)
                {
                    // 判断是否能构成三角形
                    if (IsValidTriangle(nums[i], nums[j], nums[k]))
                    {
                        // 如果可以构成三角形，更新最大周长
                        maxPerimeter = Math.Max(maxPerimeter, nums[i] + nums[j] + nums[k]);
                    }
                }
            }
        }

        // 返回最大周长
        return maxPerimeter;
    }

    // 判断是否构成三角形
    static bool IsValidTriangle(int a, int b, int c)
    {
        // 根据三角形性质判断是否能构成三角形
        return a + b > c && a + c > b && b + c > a;
    }

    #endregion
}

976.4 运行结果

示例1 方法1 输出：5
示例1 方法2 输出：5
示例2 方法1 输出：0
示例2 方法2 输出：0

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com