华为OD机试真题 JavaScript 实现【最多几个直角三角形】【2023Q1 100分】

一、题目描述

有 N 条线段，长度分别为 a[1]-a[n]。

现要求你计算这 N 条线段最多可以组合成几个直角三角形，每条线段只能使用一次，每个三角形包含三条线段。

二、输入描述

第一行输入一个正整数 T (1< =T< = 100) ，表示有组测试数据对于每组测试数据，接下来有 T 行，每行第一个正整数 N，表示线段个数 (3<= N< = 20)，接着是 N 个正整数，表示每条线段长度，(0<a[i]<100)。

三、输出描述

对于每组测试数据输出一行，每行包括一个整数，表示最多能组合的直角三角形个数。

四、解题思路

1. 首先读取输入的测试数据组数 T；
2. 创建一个二维数组 cases，用于存储每组测试数据；
3. 针对每组测试数据，依次进行以下操作：
   • 读取线段个数 N；
   • 读取 N 个线段的长度，存储到一个数组 arr 中；
   • 将 arr 存储到 cases 数组中；
4. 调用 getResult 方法，处理每组测试数据；
5. 对于每组测试数据，依次进行以下操作：
   • 对线段数组 arr 进行升序排序，以便后续组合计算；
   • 创建一个动态数组 res，用于存储组合后的三条线段；
   • 调用 dfs 方法，通过全组合的方式找出所有可能的三条线段组合，并将符合直角三角形条件的组合存储到 res 中；
   • 创建一个长度为 100 的整型数组 count，用于记录每个线段长度出现的次数；
   • 遍历线段数组 arr，统计每个线段长度出现的次数，并存储到 count 数组中；
   • 创建一个动态数组 ans，用于存储不超过线段数的最多组合数；
   • 调用 canCombine 方法，递归计算每个直角三角形中不超过线段数的最多组合数，并将结果存储到 ans 中；
   • 输出 ans 中的最大值，即最多能组合的直角三角形个数；

五、JavaScript算法源码

function findMaxRightTriangles(T, input) {const results = [];const testCases = input.split(" ");for (let i = 0; i < T; i++) {const arr = testCases[i];arr.sort((a, b) => a - b);const res = [];dfs(arr, 0, [], res);const count = new Array(100).fill(0);for (let j = 0; j < arr.length; j++) {count[arr[j]]++;}const ans = [];canCombine(res, 0, count, 0, ans);results.push(Math.max(...ans));}return results;
}// 全组合求解，即 n 个数中选 3 个
function dfs(arr, index, path, res) {if (path.length === 3) {if (isRightTriangle(path)) {res.push([...path]);}return;}for (let i = index; i < arr.length; i++) {path.push(arr[i]);dfs(arr, i + 1, path, res);path.pop();}
}// 判断三条边是否可以组成直角三角形
function isRightTriangle(path) {const x = path[0];const y = path[1];const z = path[2];return x * x + y * y === z * z;
}// 求解当前直角三角形中不超用线段的最多组合数
function canCombine(ts, index, count, num, ans) {if (index >= ts.length) {ans.push(num);return;}for (let i = index; i < ts.length; i++) {const tri = ts[i];const a = tri[0];const b = tri[1];const c = tri[2];if (count[a] > 0 && count[b] > 0 && count[c] > 0) {count[a]--;count[b]--;count[c]--;num++;canCombine(ts, i + 1, count, num, ans);num--;count[a]++;count[b]++;count[c]++;}}ans.push(num);
}

六、效果展示

1、输入

1
7 3 4 5 6 5 12 13

2、输出

2

3、说明

3 4 5 一个直角三角形；

5 12 13一个直角三角形；

一共可以组成2个。

🏆下一篇：华为OD机试真题 JavaScript 实现【相对开音节】【2022Q4 100分】，附详细解题思路

🏆本文收录于，华为OD机试（JavaScript）真题（A卷+B卷）

每一题都有详细的答题思路、详细的代码注释、样例测试，订阅后，专栏内的文章都可看，可加入华为OD刷题群（私信即可），发现新题目，随时更新，全天CSDN在线答疑。