【华为OD题库-031】比赛的冠亚季军-java

news/2024/11/27 1:24:06/

题目

有N(3<=N<10000)个运动员,他们的id为0到N-1,他们的实力由一组整数表示。他们之间进行比赛,需要决出冠亚军。比赛的规则是0号和1号比赛,2号和3号比赛,以此类推,每一轮,相邻的运动员进行比赛,获胜的进入下轮;实力值大的获胜,实力值相等的情况,id小的情况下获胜:轮空的直接进入下一轮.
输入描述:
输入一行N个数字代表N的运动员的实力值(0<=实力值<=10000000000).
输出描述:
输出冠亚季军的id,用空格隔开.
示例1
输入:
2 3 4 5
输出:
3 1 2
说明:
第一轮比赛,id为0实力值为2的运动员和id为1实力值为3的运动员比赛,1号胜出进入下一轮争夺冠亚军,id为2的运动员和id为3的运动员比赛,3号胜出进入下一轮争夺冠亚军;
冠亚军比赛,3号胜1号:故冠军为3号,亚军为1号。
2号和0号,比赛进行季军的争夺,2号实力值为4,0号实力值2,故2号胜出,得季军。
冠亚季军为3 1 2。

思路

每轮相邻的运动员分入一组比赛,每轮结束后,数组的长度由len变为(len+1)/2,加一的原因为轮空的直接进入下一轮。具体来讲:
假设len为偶数8,那么每轮len的变化过程为:8>4>2>1,长度为2时,争夺冠亚,长度为1时,得到冠军,长度为4时,可以得到4强,季军为4强中非冠亚的较大值。
假设len为基数9,那么每轮len的变化过程为:9>5>3>2>1,长度为2时,争夺冠亚,长度为1时得到冠军,长度为3时,3个运动员中减去冠亚就得到季军。
所以当数组长度降低为3或4时,最终的冠亚季军都在这个数组中,可以先保存数组的值。然后继续下一轮,当进行到最后一轮时(len=1),得到了冠军,再反推回来,就可以分别得到亚军和季军。
考虑到实力分值范围最大值为10000000000,超过了Integer,所以实力分值应该用long表示

题解

package hwod;import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
import java.util.stream.Collectors;public class Competition2 {public static void main(String[] args) {Scanner sc = new Scanner(System.in);long[] nums = Arrays.stream(sc.nextLine().split(" ")).mapToLong(Long::parseLong).toArray();int[] res = competition(nums);for (int i = 0; i < res.length; i++) {if (i != 0) System.out.print(" ");System.out.print(res[i]);}}private static int[] competition(long[] nums) {int[] res = new int[3];//存储最终的冠亚季军idint[] indexs = new int[nums.length];//记录每个人的id,每轮淘汰时,淘汰id即可for (int i = 0; i < nums.length; i++) {indexs[i] = i;}List<Integer> lst4 = new ArrayList<>();//存储4强while (indexs.length > 1) {if (indexs.length == 4 || indexs.length == 3) {lst4 = Arrays.stream(indexs).boxed().collect(Collectors.toList());}int[] newIndexs = new int[(indexs.length + 1) / 2]; //每轮淘汰一半的人数for (int i = 0; i < indexs.length; i += 2) {if (i + 1 < indexs.length && nums[indexs[i]] < nums[indexs[i + 1]]) {newIndexs[i / 2] = indexs[i + 1];} else {newIndexs[i / 2] = indexs[i];}}if (newIndexs.length == 1) {//得出冠军res[0] = newIndexs[0];//得到亚军,此时indexs长度必为2,排除冠军就是亚军了res[1] = indexs[0] == res[0] ? indexs[1] : indexs[0];}indexs = newIndexs;}Integer[] lst4new = lst4.stream().filter(x -> x != res[0] && x != res[1]).toArray(Integer[]::new);//从4强里排除冠亚军,如果剩余1个,那么那一个就是季军,如果剩余2个,那么其中的较大值是季军。if (lst4new.length == 1 || lst4new[0] >= lst4new[1]) {res[2] = lst4new[0];} else {res[2] = lst4new[1];}return res;}
}

使用indexs来记录运动员的编号可能不太直观,可以考虑直接使用自定义对象来进行排序。如下:

package hwod;import java.util.*;
import java.util.stream.Collectors;public class Competition2 {private static List<CPlayer> wins = new ArrayList<>();public static void main(String[] args) {Scanner sc = new Scanner(System.in);int[] nums = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();int[] res = competition(nums);for (int i = 0; i < res.length; i++) {if (i != 0) System.out.print(" ");System.out.print(res[i]);}}private static int[] competition(int[] nums) {int[] res = new int[3];for (int i = 0; i < nums.length; i++) {wins.add(new CPlayer(i, nums[i]));}List<CPlayer> lst4=new ArrayList<>();while (wins.size() > 2) {if (wins.size()==4||wins.size()==3) {lst4 = wins;}List<CPlayer> tmpList = new ArrayList<>();for (int i = 0; i < wins.size(); i += 2) {//>0,说明按照排序规则i该排在i+1后面,即i+1晋级if (i + 1 < wins.size() && wins.get(i).compareTo(wins.get(i + 1)) > 0) {tmpList.add(wins.get(i + 1));} else {tmpList.add(wins.get(i));}}wins = tmpList;}//最后剩下的wins一定是两个长度,产生冠亚军List<CPlayer> loser = lst4.stream().filter(x -> !wins.contains(x)).collect(Collectors.toList());Collections.sort(wins);Collections.sort(loser);res[0] = wins.get(0).getId();res[1] = wins.get(1).getId();res[2] = loser.get(0).getId();return res;}class CPlayer implements Comparable<CPlayer> {private int id;private long score;public int getId() {return id;}public void setId(int id) {this.id = id;}public long getScore() {return score;}public void setScore(long score) {this.score = score;}public CPlayer(int id, long score) {this.id = id;this.score = score;}@Overridepublic int compareTo(CPlayer o) {if (this.score == o.score) return this.id - o.id;return Long.compare(o.score, this.score);}
}

推荐

如果你对本系列的其他题目感兴趣,可以参考华为OD机试真题及题解(JAVA),查看当前专栏更新的所有题目。


http://www.ppmy.cn/news/1236527.html

相关文章

使用Pytorch从零开始构建DCGAN

在本文中&#xff0c;我们将深入研究生成建模的世界&#xff0c;并使用流行的 PyTorch 框架探索 DCGAN&#xff08;生成对抗网络 (GAN) 的一种变体&#xff09;的实现。具体来说&#xff0c;我们将使用 CelebA 数据集&#xff08;名人面部图像的集合&#xff09;来生成逼真的合…

迪文科技工业串口屏(DMG10600C070-03WTC)更新程序烧录刷机

迪文科技工业串口屏(DMG10600C070-03WTC)更新程序烧录刷机 问题 使用SD卡上电烧录&#xff0c;SD卡文件路径如下&#xff1a; 烧录时&#xff0c;无法写入&#xff0c;成功烧录文件数为0 解决方法 格式化读卡器 格式化脚本 echo off %1 %2 ver|find "5.">…

全网最详细的安装pytorch GPU方法,一次安装成功!!包括安装失败后的处理方法!

文章目录 前提---查看是否有NVIDIV英伟达显卡【笑哭】一、查看电脑的显卡驱动版本方法一&#xff1a;在cmd命令窗口中输入nvidia-smi&#xff0c;可以发现版本为12.2方法2&#xff1a;点击NVIDIA控制面板→系统信息 二、安装CUDA方法1&#xff1a; 在pytorch官网https://pytorc…

成为独立开发者有多难

首先自我介绍&#xff1a;我是一名前端开发工程师&#xff0c;7年的前端开发经验。CSDN 九段刀客_js,vue,ReactNative-CSDN博客,80多万的访问量&#xff0c;1万多的粉丝。 相信80%的程序员的终极梦想都是成为一名独立开发者&#xff0c;不用找工作有自己的产品可以有睡后收入。…

从零开始的搭建指南:开发高效的抖音预约服务小程序

预约服务小程序提高了效率&#xff0c;节省了用户时间。下文&#xff0c;小编将与大家一同探讨如何从零开始打造预约服务小程序。 第一步&#xff1a;明确需求和目标 确定你的小程序主要服务领域是什么&#xff1f;是医疗预约、美容美发、餐厅预订还是其他行业&#xff1f;明…

YOLOv8训练自己的目标检测数据集

YOLOv8训练自己的目标检测数据集 目录标题 源码下载环境配置安装包训练自己的数据集数据集文件格式数据集文件配置超参数文件配置训练数据集命令行训练脚本.py文件训练 进行detect显示detect的效果 源码下载 YOLOv8官方的GitHub代码&#xff0c;同时上面也有基础环境的配置要…

深度学习之四(循环神经网络Recurrent Neural Networks,RNNs)

概念 循环神经网络(Recurrent Neural Networks,RNNs)是一类专门用于处理序列数据的神经网络,它在处理时考虑了序列数据的顺序和上下文信息。RNNs 在自然语言处理、时间序列分析、语音识别等领域得到广泛应用。 1. 基本结构: RNN 的基本结构包含一个或多个循环单元,每个…

批量插入SQL 错误 [933] [42000]: ORA-00933: SQL 命令未正确结束

使用DBeaver向【oracle数据库】插入大量数据 INSERT INTO Student(name,sex,age,address,birthday) VALUES(Nike,男,18,北京,2000-01-01) ,(Nike,男,18,北京,2000-01-01) ,(Nike,女,18,北京,2000-01-01) ,(Nike,女,18,北京,2000-01-01) ,(Nike,男,18,北京,2000-01-01) ,(Nike…