【算法】算法测试题2：组装三角形

charles_paul 发布于2019-08-23 11:36 / 2465人阅读

摘要：题目描述牛牛有根木棒，编号为，从中取根，使得这三根木棒可以构成一个三角形。解题思路先给木棒排序，最长的边减去最小的边大于第三边，最长的边小于其他两边和。注意排序函数会调用方法，导致排序错，需要传入自定义的才能正确排序。

题目描述

牛牛有n根木棒，编号为1-N，从中取3根，使得这三根木棒可以构成一个三角形。请问有几种取法？（编号不一样则为不同取法）

输入

第一行为正整数n，表示有n个木棒
接下来n行为每个木棒的长度
n<=50, length <= 10000.

输出

取法数

思路

三角形三边关系：任何两边相加大于第三边，任何两边相减小于第三边。
解题思路：先给木棒排序，最长的边减去最小的边大于第三边，最长的边小于其他两边和。
注意：Javascript排序sort函数会调用toString方法，导致排序错，需要传入自定义的compare才能正确排序。

JavaScript解法

let n = parseInt(readline());
let lines = readline().split(" ");
let arr = new Array(n);
for(let i = 0; i < n; i++){
    arr[i] = parseInt(lines[i]);
}
arr.sort(cmp);
let count = 0;
for(let i = 0; i < n; i++){
    for(let j = i+1; j < n; j++){
        for(let k = j+1; k < n; k++){
            if(arr[i]+arr[j]>arr[k] && arr[k]-arr[i]y?1:-1;
}

海外云主机服务器托管测试数据算法图像识别算法测试字符串转2进制算法服务器并发测试算法

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/97197.html

抽象类和模板方法模式

摘要：抽象类作为多个子类的通用模板，子类在抽象类的基础上进行扩展改造，但子类总体上会大致保留抽象类的行为方式。稍微专业一点的定义就是模板方法模式，在一个方法中定义一个算法的骨架，而将一些步骤延迟到子类中。抽象方法和抽象类抽象类：用abstract修饰符修饰的类，如： public abstract class GeneralService { } 抽象方法：用abstract修...

only_do 2019-08-16 16:48 评论0 收藏0
剖析虚幻渲染体系（12）- 移动端专题Part 3（渲染优化）

摘要：管线优化管线优化曲面细分期间消除子像素。然而，高级别的曲面细分可以产生子像素三角形，这导致光栅化利用率降低。另外，如果合并或批处理之后的物体包围盒过大，反而会造成性能下降，因为无法有效使用遮挡剔除等技术进行剔除。目录 12.6 移动端渲染优化 12.6.1 渲染管线优化 12.6.1.1 使用新特性 12.6.1.2 管线优化 ...

defcon 2021-11-19 11:38 评论0 收藏0
用Node.js实现机器学习中的K最近邻分类算法

摘要：简介源于数据挖掘的一个作业，这里用来实现一下这个机器学习中最简单的算法之一算法最近邻分类法。其实这些标签就对应于机器学习中的特征这一重要概念，而训练我们识别的过程就对应于泛化这一概念。 1. 简介源于数据挖掘的一个作业，这里用Node.js来实现一下这个机器学习中最简单的算法之一k-nearest-neighbor算法(k最近邻分类法)。 k-nearest-neighbor-cl...

Cc_2011 2019-08-20 12:30 评论0 收藏0