列表

详情


NC414. 小红的最小三角形周长

描述

小红拿到了一个数组,她希望取其中的三个数,使得以这三个数为边长的三角形周长尽可能小。你能帮帮她吗?


数据范围 ,
注意:输入数据中保证至少能形成一个三角形

示例1

输入:

[2,8,4,11,9]

输出:

19

原站题解

上次编辑到这里,代码来自缓存 点击恢复默认模板

C++ 解法, 执行用时: 67ms, 内存消耗: 7788KB, 提交时间: 2022-08-06

class Solution {
  public:
    int hongstriangle(vector<int>& nums) {
        int a, b, h = nums.size(), y, z = 0;
        
        if (h >= 3) {
            sort(nums.begin(), nums.end());
            for (a = 1; (!z) && (a < h - 1); a++) {
                y = nums[a + 1] - nums[a];
                for (b = 0; (!z) && (b < a); b++) {
                    if (nums[b] > y)
                        z = nums[a] + nums[a + 1] + nums[b];
                }
            }
        }
        return z;
    }
};

C++ 解法, 执行用时: 68ms, 内存消耗: 7788KB, 提交时间: 2022-05-19

#include <algorithm>

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型
     */
    int hongstriangle(vector<int>& nums) {
        int i,j,sz=nums.size(),diff,res=0;
        if(sz>=3)
        {
            sort(nums.begin(),nums.end());
            for(i=1;(!res)&&(i<sz-1);i++)
            {
                diff=nums[i+1]-nums[i];
                for(j=0;(!res)&&(j<i);j++)
                {
                    if(nums[j]>diff)
                        res=nums[i]+nums[i+1]+nums[j];
                }
            }
        }
        return res;
    }
};

C++ 解法, 执行用时: 69ms, 内存消耗: 7796KB, 提交时间: 2022-07-15

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型
     */
    int hongstriangle(vector<int>& nums) {
        int res=0;
        if(nums.size()>2){
            sort(nums.begin(),nums.end());
            for(int i=1;(!res)&&(i<nums.size()-1);i++){
                for(int j=0;(!res)&&j<i;j++){
                    if(nums[j]>nums[i+1]-nums[i]){
                        res=nums[i]+nums[i+1]+nums[j];
                    }
                }
            }
        }
        return res;
    }
};

C++ 解法, 执行用时: 75ms, 内存消耗: 7824KB, 提交时间: 2022-06-30

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     *
     * @param nums int整型vector
     * @return int整型
     */
    int hongstriangle(vector<int>& nums) {
        // write code here
        sort(nums.begin(), nums.end());

        for (int i = 1; i < nums.size() - 2; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] > (nums[i + 1] - nums[i]))
                    return nums[j] + nums[i + 1] + nums[i];
            }
        }

        return -1;
    }
};

C 解法, 执行用时: 76ms, 内存消耗: 7812KB, 提交时间: 2022-06-17

/**
 * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
 *
 * 
 * @param nums int整型一维数组 
 * @param numsLen int nums数组长度
 * @return int整型
 *
 * C语言声明定义全局变量请加上static,防止重复定义
 */
int cmp(const void *a, const void *b) {
    return *((int *)a) - *((int *)b);
}

long min(long a, long b) {
    return a > b ? b : a;
}

int hongstriangle(int* nums, int numsLen) {
    qsort(nums, numsLen, sizeof(int), cmp);
    
    long minC = 3000000001;
    
    for (int i = 0; i < numsLen - 2; i++) {
        for (int j = i + 1; j < numsLen - 1; j++) {
            if (nums[i] + nums[j] > nums[j+1]) {
                minC = min(((long)nums[i]) + nums[j] + nums[j+1], minC);
                break;
            }
        }
    }
    
    return (int)minC;
}



上一题