Rust面试宝典第8题：三角形的最大周长-Toy模板网

这篇具有很好参考价值的文章主要介绍了Rust面试宝典第8题：三角形的最大周长。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目

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

示例 1：

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

示例 2：

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

解析

这道题相对比较简单，主要考察应聘者对三角形基本性质的理解，特别是“任意两边之和大于第三边”的条件，这是判断能否构成三角形以及计算其周长的基础。虽然直接遍历所有三元组组合可以解决问题，但为了提高效率，可以考虑使用动态规划，或先对数组进行排序以减少不必要的检查。

本题的解题步骤如下。

首先，对输入数组nums进行排序。这样做的好处是：对于已排序的数组，我们可以确保在遍历过程中，当前元素不会小于之前检查过的元素，从而避免重复计算和无效检查。

然后，从排序后的数组中，遍历每个元素作为可能的三角形最长边。对于每个最长边，我们只需检查它之前（即更小的）两个元素是否满足三角形条件。若满足，记录当前周长；否则，继续遍历。

最后，遍历结束，返回最大周长。

这里有一些特殊情况，我们可以单独处理：如果数组长度小于3，或者数组中的所有元素都相同，此时无法构成面积不为零的三角形，则直接返回0。

fn get_largest_perimeter(nums: Vec<i32>) -> i32 {
    let mut nums = nums;
    nums.sort_unstable();

    if nums.len() < 3 || nums[0] == nums[nums.len() - 1] {
        return 0;
    }

    let mut max_perimeter = 0;
    for i in (2..nums.len()).rev() {
        let a = nums[i];
        let b = nums[i - 1];
        let c = nums[i - 2];
        if b + c > a && max_perimeter < a + b + c {
            max_perimeter = a + b + c;
        }
    }

    max_perimeter
}

fn main() {
    let numbers1 = vec![2, 1, 2];
    println!("{}", get_largest_perimeter(numbers1));

    let numbers2 = vec![1, 2, 1, 10];
    println!("{}", get_largest_perimeter(numbers2));
}

在上面的示例代码中，定义了一个名为get_largest_perimeter的函数，用于计算由给定数组nums中的三个正数所组成的、面积不为零的三角形的最大周长。此函数接受一个类型为Vec<i32>的参数nums，表示包含正数的数组。函数返回类型为i32，表示计算得到的最大三角形周长。函数主体分为：数据预处理、特殊情况处理、遍历与判断以及返回结果四个部分。下面，分别进行介绍。

数据预处理：首先创建一个可变变量nums，复制传入的参数值。接着对nums进行不稳定排序，这意味着可能会改变元素的原始相对顺序，但能提供更高的性能。排序后，数组中的元素按升序排列，便于后续遍历并快速判断能否构成三角形。

特殊情况处理：如果数组长度小于3，无法选取三个数构成三角形，因此直接返回0。如果数组的第一个元素（最小值）等于最后一个元素（最大值），说明所有元素都相等，无法构成面积不为零的三角形，也返回0。

遍历与判断：初始化变量max_perimeter为0，用于存储找到的最大三角形周长。使用for循环遍历数组，从倒数第三个元素开始到倒数第一个元素。逆序遍历是为了确保每次迭代时，a始终为当前最大的边长，b和c分别为较小的两个边长。在循环体内，计算当前三边长a、b、c，并检查它们是否满足三角形条件：b + c > a。如果满足条件且当前周长大于已记录的最大周长，则更新max_perimeter。

返回结果：循环结束后，返回计算得到的最大三角形周长max_perimeter。