华为OD机试 - 最优结果的a数组数量 - 贪心思维(Java 2024 E卷 100分)

2024-09-06 09:28

本文主要是介绍华为OD机试 - 最优结果的a数组数量 - 贪心思维(Java 2024 E卷 100分),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

在这里插入图片描述

华为OD机试 2024E卷题库疯狂收录中,刷题点这里

专栏导读

本专栏收录于《华为OD机试(JAVA)真题(E卷+D卷+A卷+B卷+C卷)》。

刷的越多,抽中的概率越大,私信哪吒,备注华为OD,加入华为OD刷题交流群,每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景,发现新题目,随时更新,全天CSDN在线答疑。

一、题目描述

给定两个只包含数字的数组a、b,调整数组b里面数字的排列顺序,使得尽可能多的a[i] > b[i]。数组a和b中的数字各不相同。

输出所有可以达到最优结果的a数组组数量

二、输入描述

输入的第一行是数组a中的数字,其中只包含数字,每两个数字之间相隔一个空格,a数组大小不超过10。

输入的第一行是数组b中的数字,其中只包含数字,每两个数字之间相隔一个空格,b数组大小不超过10。

三、输出描述

输出所有可以达到最优结果的a数组数量

四、测试用例

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

测试用例1

1、输入

11 8 20
10 13 7

2、输出

1

3、说明

最优结果只有一个,a = [11, 20, 8],故输出1

测试用例2

1、输入

11 12 20
10 13 7

2、输出

2

3、说明

有两个a数组的排列可以达到最优结果,[12, 20, 11]和[11, 20, 12],故输出2

五、解题思路

我们需要对数组 b 进行排列,使得尽可能多的 a[i] > b[i]。可以对数组 a 进行排序,然后对 b 的所有排列进行逐个比较,判断哪些排列能满足 a[i] > b[i]。

暴力解法:对数组 b 求所有排列,并与排序后的 a 逐一比较,统计能够满足条件的情况。

详细步骤:

  1. 将数组 a 升序排序。
  2. 求出数组 b 的所有可能排列。
  3. 对于每一种排列,统计满足 a[i] > b[i] 的情况。
  4. 返回满足 a[i] > b[i] 条件的最优数量排列的个数。

六、Java算法源码

public class OdTest01 {// 计算数组b的所有排列并返回所有的排列结果public static List<List<Integer>> permute(List<Integer> nums) {List<List<Integer>> results = new ArrayList<>();permuteHelper(nums, 0, results);return results;}// 递归函数,求数组的全排列private static void permuteHelper(List<Integer> nums, int start, List<List<Integer>> results) {if (start == nums.size() - 1) {results.add(new ArrayList<>(nums));return;}for (int i = start; i < nums.size(); i++) {Collections.swap(nums, i, start);  // 交换permuteHelper(nums, start + 1, results);  // 递归调用Collections.swap(nums, i, start);  // 还原}}public static void main(String[] args) {Scanner sc = new Scanner(System.in);// 输入a数组List<Integer> a = new ArrayList<>();for (String num : sc.nextLine().split(" ")) {a.add(Integer.parseInt(num));}// 输入b数组List<Integer> b = new ArrayList<>();for (String num : sc.nextLine().split(" ")) {b.add(Integer.parseInt(num));}// 将a数组升序排序Collections.sort(a);// 求b数组的所有排列List<List<Integer>> permutations = permute(b);// 记录可以达到最优结果的个数int maxCount = 0;int optimalCount = 0;// 遍历每一个b的排列,和a数组进行比较for (List<Integer> perm : permutations) {int count = 0;// 统计a[i] > b[i]的数量for (int i = 0; i < a.size(); i++) {if (a.get(i) > perm.get(i)) {count++;}}// 更新最优结果if (count > maxCount) {maxCount = count;optimalCount = 1;  // 更新为新的最优情况} else if (count == maxCount) {optimalCount++;  // 多个排列可以达到相同的最优结果}}// 输出可以达到最优结果的排列个数System.out.println(optimalCount);}
}

七、效果展示

测试用例3

1、输入

1 2 3
4 5 6

2、输出

6

3、说明

a无论如何都会全输,故a任意排列都行,输出所有a数组的排列,6种排列。在这里插入图片描述


🏆下一篇:华为OD机试 - 简易内存池 - 逻辑分析(Java 2024 E卷 200分)

🏆本文收录于,华为OD机试(JAVA)真题(E卷+D卷+A卷+B卷+C卷)

刷的越多,抽中的概率越大,私信哪吒,备注华为OD,加入华为OD刷题交流群,每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景,发现新题目,随时更新,全天CSDN在线答疑。

在这里插入图片描述

这篇关于华为OD机试 - 最优结果的a数组数量 - 贪心思维(Java 2024 E卷 100分)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1141639

相关文章

Java中StopWatch的使用示例详解

《Java中StopWatch的使用示例详解》stopWatch是org.springframework.util包下的一个工具类,使用它可直观的输出代码执行耗时,以及执行时间百分比,这篇文章主要介绍... 目录stopWatch 是org.springframework.util 包下的一个工具类,使用它

Java进行文件格式校验的方案详解

《Java进行文件格式校验的方案详解》这篇文章主要为大家详细介绍了Java中进行文件格式校验的相关方案,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、背景异常现象原因排查用户的无心之过二、解决方案Magandroidic Number判断主流检测库对比Tika的使用区分zip

Java实现时间与字符串互相转换详解

《Java实现时间与字符串互相转换详解》这篇文章主要为大家详细介绍了Java中实现时间与字符串互相转换的相关方法,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、日期格式化为字符串(一)使用预定义格式(二)自定义格式二、字符串解析为日期(一)解析ISO格式字符串(二)解析自定义

Java使用Curator进行ZooKeeper操作的详细教程

《Java使用Curator进行ZooKeeper操作的详细教程》ApacheCurator是一个基于ZooKeeper的Java客户端库,它极大地简化了使用ZooKeeper的开发工作,在分布式系统... 目录1、简述2、核心功能2.1 CuratorFramework2.2 Recipes3、示例实践3

Springboot处理跨域的实现方式(附Demo)

《Springboot处理跨域的实现方式(附Demo)》:本文主要介绍Springboot处理跨域的实现方式(附Demo),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不... 目录Springboot处理跨域的方式1. 基本知识2. @CrossOrigin3. 全局跨域设置4.

springboot security使用jwt认证方式

《springbootsecurity使用jwt认证方式》:本文主要介绍springbootsecurity使用jwt认证方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地... 目录前言代码示例依赖定义mapper定义用户信息的实体beansecurity相关的类提供登录接口测试提供一

Spring Boot 3.4.3 基于 Spring WebFlux 实现 SSE 功能(代码示例)

《SpringBoot3.4.3基于SpringWebFlux实现SSE功能(代码示例)》SpringBoot3.4.3结合SpringWebFlux实现SSE功能,为实时数据推送提供... 目录1. SSE 简介1.1 什么是 SSE?1.2 SSE 的优点1.3 适用场景2. Spring WebFlu

基于SpringBoot实现文件秒传功能

《基于SpringBoot实现文件秒传功能》在开发Web应用时,文件上传是一个常见需求,然而,当用户需要上传大文件或相同文件多次时,会造成带宽浪费和服务器存储冗余,此时可以使用文件秒传技术通过识别重复... 目录前言文件秒传原理代码实现1. 创建项目基础结构2. 创建上传存储代码3. 创建Result类4.

Java利用JSONPath操作JSON数据的技术指南

《Java利用JSONPath操作JSON数据的技术指南》JSONPath是一种强大的工具,用于查询和操作JSON数据,类似于SQL的语法,它为处理复杂的JSON数据结构提供了简单且高效... 目录1、简述2、什么是 jsONPath?3、Java 示例3.1 基本查询3.2 过滤查询3.3 递归搜索3.4

Tomcat版本与Java版本的关系及说明

《Tomcat版本与Java版本的关系及说明》:本文主要介绍Tomcat版本与Java版本的关系及说明,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Tomcat版本与Java版本的关系Tomcat历史版本对应的Java版本Tomcat支持哪些版本的pythonJ