华为OD机试-最多组合直角三角形个数-2022Q4 A卷-Py/Java/JS

题目描述

有N条线段，长度分别为a[1]-a[n]。
现要求你计算这N条线段最多可以组合成几个直角三角形。
每条线段只能使用一次，每个三角形包含三条线段。

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

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

示例1：输入输出示例仅供调试，后台判题数据一般不包含示例
输入

1

7 3 4 5 6 5 12 13 
输出

2

Java 代码

import java.util.Scanner;
import java.util.*;
import java.util.stream.Collectors;
import java.math.BigInteger;
import java.util.stream.Stream;class Main {public static ArrayList<Integer> result = new ArrayList<>();public static ArrayList<Integer[]> paths = new ArrayList<>();public static void main(String[] args) {// 处理输入Scanner in = new Scanner(System.in);// 处理输入int T = in.nextInt();for (int i=0;i<T;i++) {int N = in.nextInt();int[] nums = new int[N];for (int j = 0; j < N; j++) {nums[j] = in.nextInt();}Arrays.sort(nums);System.out.println(dfs(nums,0));}}public static int dfs(int[] lines, int index) {int maxVal = 0;int a, b, c;for (int i = index; i < lines.length-2; i++) {a = lines[i];if (a == 0) {continue;}for (int j = i+1; j < lines.length-1; j++) {b = lines[j];if (b == 0) {continue;}for (int k = j+1; k < lines.length; k++) {c = lines[k];if (c == 0) {continue;}if ((a*a + b*b) == c*c) {lines[i]=0;lines[j]=0;lines[k]=0;maxVal = Math.max(maxVal, dfs(lines,i+1) +1);lines[i]=a;lines[j]=b;lines[k]=c;};}}}return maxVal;}}

Python代码

import functools
import collections
import math
from itertools import combinations
from re import matchclass TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = right#并查集模板
class UF:def __init__(self, n=0):self.count = nself.item = [0 for x in range(n+1)]for i in range(n):self.item[i] = idef find(self, x):if (x != self.item[x]):self.item[x] = self.find(self.item[x])return 0return xdef union_connect(self, x, y):x_item = self.find(x)y_item = self.find(y)if (x_item != y_item):self.item[y_item] = x_itemself.count-=1def dfs( lines, index):maxVal = 0a=0b=0c=0for i in range(index, len(lines)-2) :a = lines[i]if (a == 0):continuefor j in range(i+1, len(lines)-1) :b = lines[j]if (b == 0):continuefor k in range(j+1, len(lines)) :c = lines[k]if (c == 0):continueif ((a*a + b*b) == c*c):lines[i]=0lines[j]=0lines[k]=0maxVal = max(maxVal, dfs(lines,i+1) +1)lines[i]=alines[j]=blines[k]=creturn maxVal# 处理输入
n = int(input())
for i in range(n):#先进行去重params = [int(x) for x in input().split(" ")]N = params[0]nums = params[1:]nums.sort()print(dfs(nums, 0))

JS代码

function dfs(lines, index) {let maxVal = 0;let a, b, c;for (let i = index; i < lines.length-2; i++) {a = lines[i];if (a == 0) {continue;}for (let j = i+1; j < lines.length-1; j++) {b = lines[j];if (b == 0) {continue;}for (let k = j+1; k < lines.length; k++) {c = lines[k];if (c == 0) {continue;}if ((a*a + b*b) == c*c) {lines[i]=0;lines[j]=0;lines[k]=0;maxVal = Math.max(maxVal, dfs(lines,i+1) +1);lines[i]=a;lines[j]=b;lines[k]=c;};}}}return maxVal;
}
function main(params) {N = params[0]let nums = []for (let i=1;i<params.length;i++) {nums.push(params[i])}nums.sort(function(a, b) {return a-b})console.log(dfs(nums, 0))
}main([7, 3, 4, 5, 6, 5, 12, 13])