题解 | #小红的最小三角形周长#

小红的最小三角形周长

https://www.nowcoder.com/practice/959c3b1ff4794ecea41a2569892ab4d4

从数组中寻找周长最小的三角形,常规的思路是先排序,再从小到大依次搜索,再添加一些小优化就OK了。

假设最短三角形的三条边依次是a、b、c(a<b<c),通过分析我们可以知道,b、c在排序后的数组中一定是相邻的,因为如果b、c中间还有数据(设为x),那么a、b、x会形成一个更短的三角形,与假设矛盾。

如此,我们仅需将c设为遍历变量,便可以直接确定b,接下来只需要找到a就可以了,根据三角形性质,我们有a>c-b,借助二分查找法我们可以查找到0~b范围内比c-b大的最小值,这个值就是我们要的a。

需要注意的是,从左到右按以上逻辑遍历数组查找到的第一组数据,不一定是最终结果(最优解),因为以上算法实际上仅能保证b+c是最小的,而不能保证b+c+a也是最小的,考虑一个实际例子:2,88,90,100,101,我们查找到的第一组数据是88,90,100,周长为278,但实际上答案是2,100,101,周长为203,因此我们还要继续遍历,看看后面有没有更短的三角形。

后续遍历的终止条件是已有周长<2c+1,因为当我们确定c时,由它所构成的三角形的最短周长为:c+b+(c-b+1)=2c+1,这个值越往后遍历越大,因此当2c+1比已知的答案更大时,便没有继续遍历的必要了。

参考代码如下,由于题目已经保证了数据的合法性,因此这里忽略了很多合法性检查:

class Solution {
  public:
    //使用二分法寻找三条边中最小的边,第21行的条件保证了该边一定存在
    int find_shortest_edge(vector<int>& nums, int endIdx, int minLimit) {
        int leftIdx = 0, rightIdx = endIdx, mid = 0;
        while (leftIdx < rightIdx) {
            mid = (leftIdx + rightIdx) / 2;
            if (nums[mid] < minLimit) leftIdx = mid + 1;
            else if (nums[mid] >= minLimit) rightIdx = mid;
        }
        return nums[leftIdx];
    }
  
    int hongstriangle(vector<int>& nums) {
        sort(nums.begin(), nums.end());

        unsigned int shortestPerimeter = UINT32_MAX;
        unsigned int currPerimeter = 0;
        for (int i = 2; shortestPerimeter == UINT32_MAX || (i < nums.size() &&
                shortestPerimeter > 2 * nums[i]); i++) {
            if (nums[i - 2] + nums[i - 1] > nums[i]) {
                currPerimeter = nums[i] + nums[i - 1] + find_shortest_edge(nums, i - 2,
                                nums[i] - nums[i - 1] + 1);
                if (currPerimeter < shortestPerimeter) {
                    shortestPerimeter = currPerimeter;
                }
            }
        }
        return shortestPerimeter;
    }
};

全部评论

相关推荐

仁者伍敌:难怪小公司那么挑剔,让你们这些大佬把位置拿了
点赞 评论 收藏
分享
Twilight_m...:表格简历有点难绷。说说个人看法: 1.个人基本情况里好多无意义信息,什么婚姻状况、健康状况、兴趣爱好、户口所在地、身份证号码、邮政编码,不知道的以为你填什么申请表呢。 2.校内实践个人认为对找工作几乎没帮助,建议换成和测开有关的项目,实在没得写留着也行。 3.工作经历完全看不出来是干什么的,起码看着和计算机没啥关系,建议加强描述,写点你在工作期间的实际产出、解决了什么问题。 4.个人简述大而空,看着像AI生成,感觉问题最大。“Python,C,C++成为我打造高效稳定服务的得力工具”、“我渴望凭借自身技术知识与创新能力,推动人工智能技术的应用发展,助力社会实现智能化转型”有种小学作文的美感。而且你确定你个人简述里写的你都会嘛?你AI这块写的什么“深入研究”,发几篇顶会的硕博生都不一定敢这么写。而且你AI这块的能力和软测也完全无关啊。个人简述建议写你对哪些技术栈、哪些语言、哪些生产工具的掌握,写的有条理些,而且最好是和测开强相关的。
点赞 评论 收藏
分享
评论
3
1
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务