【教3妹学编程-算法题】找到最大周长的多边形

2023-12-25 12:01:49

插: 前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。点击跳转到网站。
坚持不懈,越努力越幸运,大家一起学习鸭~~~

阳光明媚

3妹:“太阳当空照,花儿对我笑,小鸟说早早早,你为什么背上炸药包”
2哥 :3妹,什么事呀这么开森。
3妹:2哥你看今天的天气多好啊,经过了一周多的寒潮,天气总算暖和些了。
2哥:是啊,都说一九二九不出手,三九四九冰上走,这才一九就已经可以冰上走了。
3妹:上海这边虽然也挺冷了,但是还算好,想想北方都已经泼水成冰啦!
2哥:泼水成冰好玩是好玩,但是一定要注意防寒哦,看新闻都有人冻伤了。
3妹:是啊,还是待在室内比较好
2哥:给你出了一道题发你微信里了, 上班通勤的路上记得看一下,回来问你答案~
image.png
3妹:知道啦,难不倒我!

题目:

给你一个长度为 n 的 正 整数数组 nums 。

多边形 指的是一个至少有 3 条边的封闭二维图形。多边形的 最长边 一定 小于 所有其他边长度之和。

如果你有 k (k >= 3)个 正 数 a1,a2,a3, …,ak 满足 a1 <= a2 <= a3 <= … <= ak 且 a1 + a2 + a3 + … + ak-1 > ak ,那么 一定 存在一个 k 条边的多边形,每条边的长度分别为 a1 ,a2 ,a3 , …,ak 。

一个多边形的 周长 指的是它所有边之和。

请你返回从 nums 中可以构造的 多边形 的 最大周长 。如果不能构造出任何多边形,请你返回 -1 。

示例 1:

输入:nums = [5,5,5]
输出:15
解释:nums 中唯一可以构造的多边形为三角形,每条边的长度分别为 5 ,5 和 5 ,周长为 5 + 5 + 5 = 15 。
示例 2:

输入:nums = [1,12,1,2,5,50,3]
输出:12
解释:最大周长多边形为五边形,每条边的长度分别为 1 ,1 ,2 ,3 和 5 ,周长为 1 + 1 + 2 + 3 + 5 = 12 。
我们无法构造一个包含变长为 12 或者 50 的多边形,因为其他边之和没法大于两者中的任何一个。
所以最大周长为 12 。
示例 3:

输入:nums = [5,5,50]
输出:-1
解释:无法构造任何多边形,因为多边形至少要有 3 条边且 50 > 5 + 5 。

提示:

3 <= n <= 10^5
1 <= nums[i] <= 10^9

思路:

思考

排序+枚举,
把数组排序,枚举 nums[i]作为最长的那条边,那么 nums[i]左边的数之和越大越好,这样才能尽可能地组成多边形,并且周长尽量长。

所以周长就是 nums 的某个前缀和。从大到小枚举 nums[i],如果满足

nums[0]+nums[1]+?+nums[i?1]>nums[i]
那么答案就是
nums[0]+nums[1]+?+nums[i?1]+nums[i]

java代码:

class Solution {
    public long largestPerimeter(int[] nums) {
        Arrays.sort(nums);
        long s = 0;
        for (int x : nums) {
            s += x;
        }
        for (int i = nums.length - 1; i > 1; i--) {
            int x = nums[i];
            if (s > x * 2) { // s-x > x
                return s;
            }
            s -= x;
        }
        return -1;
    }
}

文章来源:https://blog.csdn.net/kangbin825/article/details/135191887
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。