当前位置: 首页 > news >正文

华为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在线答疑。

在这里插入图片描述

相关文章:

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

一、题目描述 有 N 条线段&#xff0c;长度分别为 a[1]-a[n]。 现要求你计算这 N 条线段最多可以组合成几个直角三角形&#xff0c;每条线段只能使用一次&#xff0c;每个三角形包含三条线段。 二、输入描述 第一行输入一个正整数 T (1< T< 100) &#xff0c;表示有…...

vue3中的reactive、ref、toRef和toRefs

目录 reactivereactive的实现原理使用reactive的注意事项 refref的实现原理使用ref的注意事项 toRef和toRefsref和reactive的使用比较 reactive reactive用于创建响应式对象&#xff0c;它返回一个对象的响应式代理。即&#xff1a;它返回的对象以及其中嵌套的对象都会通过 Pr…...

数字图像处理与Python实现-图像增强经典算法汇总

图像增强经典算法汇总 文章目录 图像增强经典算法汇总1、像素变换2、图像逆变换3、幂律变换4、对数变换5、图像均衡化6、对比度受限自适应直方图均衡(CLAHE)7、对比度拉伸8、Sigmoid校正9、局部对比度归一化10、总结本文将对图像增强经典算法做一个简单的汇总。图像增强的经典…...

tag提示词总结

顺序的权重 越靠前的tag权重越大&#xff0c;越靠后的tag权重越小经验来讲&#xff0c;将图像质量相关的tag放在前面&#xff0c;例如masterpiece&#xff0c;best quality等&#xff1b;接着添加主体画风等&#xff1b;最后添加一些不太重要的细节 权重增减 (tag)&#xff1a…...

微信小程序原生开发功能合集二十:导航栏、tabbar自定义及分包功能介绍

本章实现导航栏及tabbar的自定义处理的相关方法介绍及效果展示。   另外还提供小程序开发基础知识讲解课程,包括小程序开发基础知识、组件封装、常用接口组件使用及常用功能实现等内容,具体如下:    1. CSDN课程: https://edu.csdn.net/course/detail/37977    2. 5…...

高通 Camera HAL3:项目开发技术点总结

做高通 Camera HAL3开发的一些技术点的总结、整理。 做个记录&#xff0c;方便后续查阅。 1.目录、so、配置文件 productName是项目名 out Target路径&#xff1a;\out\target\product\productName\chi-cdk&#xff1a;\vendor\qcom\proprietary\chi-cdk\ldc node&#xff1…...

chatgpt赋能python:Python怎么删除列表中的最大值和最小值

Python怎么删除列表中的最大值和最小值 在Python中&#xff0c;一个列表&#xff08;List&#xff09;是一种非常常见的数据结构&#xff0c;它允许我们以有序的方式存储和访问数据。但是&#xff0c;有时候我们需要从列表中删除最大或最小的值&#xff0c;以满足我们的特定需…...

简述Vue的生命周期以及每个阶段做的事情

03_简述Vue的生命周期以及每个阶段做的事情 思路 给出概念 列举出生命周期各个阶段 阐述整体流程 结合实际 扩展&#xff1a;vue3变化 回答范例 每个vue组件实例被创建后都会经过一系列步骤。比如它需要数据观测、模板编译、挂载实例到dom、以及数据变化的时候更新dom、…...

LeetCode-C#-0004.寻找两个正序数组的中位数

0.声明 该题目来源于LeetCode 如有侵权&#xff0c;立马删除。 解法不唯一&#xff0c;如有新解法可一同讨论。 1.题目 0004寻找两个正序数组的中位数 给定两个大小分别为m和n的正序&#xff08;从小到大&#xff09;数组nums1和nums2。 请你找出并返回着两个正序数组的中位…...

Vue.js 中的 $emit 和 $on 方法有什么区别?

Vue.js 中的 $emit 和 $on 方法有什么区别&#xff1f; 在 Vue.js 中&#xff0c;$emit 和 $on 方法是两个常用的方法&#xff0c;用于实现组件间的通信。它们可以让我们在一个组件中触发一个自定义事件&#xff0c;并在另一个组件中监听这个事件&#xff0c;从而实现组件间的…...

LAZADA平台的商品评论Python封装API接口接入文档和参数说明

LAZADA是一个位于东南亚的电商平台&#xff0c;成立于2012年。该平台覆盖的国家包括新加坡、马来西亚、印尼、菲律宾、泰国和越南等地。它提供了一个多样化的产品选择&#xff0c;包括时尚、美容、数码、母婴等商品&#xff0c;并且拥有许多知名品牌的官方旗舰店。同时&#xf…...

云原生Docker镜像管理

docker是什么&#xff1f; docker是一个go语言开发的应用容器引擎。 docker的作用&#xff1f; ①运行容器里的应用&#xff1b; ②docker是用来管理容器和镜像的一种工具。 #容器 与 虚拟机 的区别&#xff1f; 容器虚拟机所有容器共享宿主机内核每个虚拟机都有独立的操…...

ChatGPT+小红书的8种高级玩法

掌握了这套万能命令&#xff0c;让你快速做出小红书爆款文案! 一、用ChatGPT做定位 我是一个大龄的普通人&#xff0c;没有什么特殊的技能&#xff0c;接下来&#xff0c;请你作为一位小红书的账号定位专家&#xff0c;通过与我对话的方式&#xff0c;为我找到我的小红书账号定…...

shell脚本学习记录1(运算符)

Shell 传递参数 我们可以在执行 Shell 脚本时&#xff0c;向脚本传递参数&#xff0c;脚本内获取参数的格式为&#xff1a;$n。n 代表一个数字&#xff0c;1 为执行脚本的第一个参数&#xff0c;2 为执行脚本的第二个参数&#xff0c;以此类推…… 以下实例我们向脚本传递三个…...

vector 迭代器失效问题

vector 迭代器失效 迭代器的主要作用就是让算法能够不用关心底层数据结构&#xff0c;其底层实际就是一个指针&#xff0c;或者是对指针进行了封装&#xff0c;比如&#xff1a;vector的迭代器就是原生态指针T* 。因此迭代器失效&#xff0c;实际就是迭代器底层对应指针所指向…...

docker使用与服务器上的可视化(ROS rviz等)

1.安装docker 安装docker&#xff1a;官网教程&#xff0c;按照官网命令一步步来即可。 添加当前用户到docker用户组&#xff1a; 【docker】添加用户到docker组&#xff0c;这样后面运行docker的时候前面不需要加sudo命令&#xff0c;否则运行docker的时候一直需要在前面加su…...

最新版本Portraiture4.1中文版ps磨皮滤镜插件安装包

在Portraiture有非常强大的手动功能&#xff0c;可以为用户进行手动调整照片中的皮肤区域以达到更加完美的效果&#xff0c;软件还支持同时导入上千张照片&#xff0c;用户可以通过自动识别照片中的人脸从而依照自己的风格进行批量处理十分的方便快捷。 最新版本Portraiture 4…...

仓储WMS对接淘宝奇门详细说明【亲测可用】

文章目录 简介名词解释奇门对接方案前期准备系统调用流程代码实现思路关键点(个人观点)奇门对接关键代码可能遇到的问题 简介 淘宝奇门项目支持 ERP、WMS 之间的系统标准化对接&#xff0c;通过构建 ERP、WMS 系统之间标准通信协议来实现不同系统之间的打通&#xff1b;对商家…...

RFID软件:简介、功能和应用范围

在当今快节奏的商业环境中&#xff0c;RFID&#xff08;射频识别&#xff09;技术已经成为物流、供应链和库存管理等领域中不可或缺的工具。本文将向您介绍RFID软件的基本知识&#xff0c;探讨其功能和广泛应用的范围。 第一部分&#xff1a;RFID软件简介 RFID软件是一种应用…...

Android 逆向之安全防护基本策略

对抗反编译 混淆 使用混淆主要可以减小包的大小。混淆对于安全保护来说&#xff0c;只是增加了阅读难度而已。混淆不会把关键代码混淆掉&#xff0c;比如MainActivity&#xff0c;Application等&#xff0c;可以通过分析smali和阅读jar包定位代码。 资源混淆也是换汤不换药&…...

java_网络服务相关_gateway_nacos_feign区别联系

1. spring-cloud-starter-gateway 作用&#xff1a;作为微服务架构的网关&#xff0c;统一入口&#xff0c;处理所有外部请求。 核心能力&#xff1a; 路由转发&#xff08;基于路径、服务名等&#xff09;过滤器&#xff08;鉴权、限流、日志、Header 处理&#xff09;支持负…...

Leetcode 3576. Transform Array to All Equal Elements

Leetcode 3576. Transform Array to All Equal Elements 1. 解题思路2. 代码实现 题目链接&#xff1a;3576. Transform Array to All Equal Elements 1. 解题思路 这一题思路上就是分别考察一下是否能将其转化为全1或者全-1数组即可。 至于每一种情况是否可以达到&#xf…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个生活电费的缴纳和查询小程序

一、项目初始化与配置 1. 创建项目 ohpm init harmony/utility-payment-app 2. 配置权限 // module.json5 {"requestPermissions": [{"name": "ohos.permission.INTERNET"},{"name": "ohos.permission.GET_NETWORK_INFO"…...

LINUX 69 FTP 客服管理系统 man 5 /etc/vsftpd/vsftpd.conf

FTP 客服管理系统 实现kefu123登录&#xff0c;不允许匿名访问&#xff0c;kefu只能访问/data/kefu目录&#xff0c;不能查看其他目录 创建账号密码 useradd kefu echo 123|passwd -stdin kefu [rootcode caozx26420]# echo 123|passwd --stdin kefu 更改用户 kefu 的密码…...

【笔记】WSL 中 Rust 安装与测试完整记录

#工作记录 WSL 中 Rust 安装与测试完整记录 1. 运行环境 系统&#xff1a;Ubuntu 24.04 LTS (WSL2)架构&#xff1a;x86_64 (GNU/Linux)Rust 版本&#xff1a;rustc 1.87.0 (2025-05-09)Cargo 版本&#xff1a;cargo 1.87.0 (2025-05-06) 2. 安装 Rust 2.1 使用 Rust 官方安…...

Visual Studio Code 扩展

Visual Studio Code 扩展 change-case 大小写转换EmmyLua for VSCode 调试插件Bookmarks 书签 change-case 大小写转换 https://marketplace.visualstudio.com/items?itemNamewmaurer.change-case 选中单词后&#xff0c;命令 changeCase.commands 可预览转换效果 EmmyLua…...

命令行关闭Windows防火墙

命令行关闭Windows防火墙 引言一、防火墙:被低估的"智能安检员"二、优先尝试!90%问题无需关闭防火墙方案1:程序白名单(解决软件误拦截)方案2:开放特定端口(解决网游/开发端口不通)三、命令行极速关闭方案方法一:PowerShell(推荐Win10/11)​方法二:CMD命令…...

手动给中文分词和 直接用神经网络RNN做有什么区别

手动分词和基于神经网络&#xff08;如 RNN&#xff09;的自动分词在原理、实现方式和效果上有显著差异&#xff0c;以下是核心对比&#xff1a; 1. 实现原理对比 对比维度手动分词&#xff08;规则 / 词典驱动&#xff09;神经网络 RNN 分词&#xff08;数据驱动&#xff09…...

__VUE_PROD_HYDRATION_MISMATCH_DETAILS__ is not explicitly defined.

这个警告表明您在使用Vue的esm-bundler构建版本时&#xff0c;未明确定义编译时特性标志。以下是详细解释和解决方案&#xff1a; ‌问题原因‌&#xff1a; 该标志是Vue 3.4引入的编译时特性标志&#xff0c;用于控制生产环境下SSR水合不匹配错误的详细报告1使用esm-bundler…...

Vue 实例的数据对象详解

Vue 实例的数据对象详解 在 Vue 中,数据对象是响应式系统的核心,也是组件状态的载体。理解数据对象的原理和使用方式是成为 Vue 专家的关键一步。我将从多个维度深入剖析 Vue 实例的数据对象。 一、数据对象的定义方式 1. Options API 中的定义 在 Options API 中,使用 …...