Java代码题m个小朋友分糖果,巧解“博弈”型算法题:分糖果问题

2023-11-10 08:59

本文主要是介绍Java代码题m个小朋友分糖果,巧解“博弈”型算法题:分糖果问题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

问题导入

【题目:】 给定一个偶数长度的数组,其中不同的数字代表着不同种类的糖果,每一个数字代表一个糖果。你需要把这些糖果平均分给一个弟弟和一个妹妹。返回妹妹可以获得的最大糖果的种类数。

示例 1:

输入: candies = [1,1,2,2,3,3]

输出: 3

解析: 一共有三种种类的糖果,每一种都有两个。

最优分配方案:妹妹获得[1,2,3],弟弟也获得[1,2,3]。这样使妹妹获得糖果的种类数最多。

示例 2 :

输入: candies = [1,1,2,3]

输出: 2

解析: 妹妹获得糖果[2,3],弟弟获得糖果[1,1],妹妹有两种不同的糖果,弟弟只有一种。这样使得妹妹可以获得的糖果种类数最多。

注意:

数组的长度为[2, 10,000],并且确定为偶数。数组中数字的大小在范围[-100,000, 100,000]内。

题目解析

总共有 n 个糖,平均分给两个人,每人得到 n/2 块糖,那么 能拿到的最大的糖的种类数也就是 n/2 种 ,不可能更多,只可能更少。

所以只需要统计出糖的种类数,如果糖的种类数小于 n/2,说明拿不到 n/2种糖,最多能拿到的种类数就是当前糖的总种类数。最后,看(数量的一半)和(所有的种类)哪个先达到,取两者中较小的值即可。

举个例子:

极端情况1:所有糖都不重样,这种情况妹妹也只能拿到一半的糖果。

极端情况2:只有一种糖,这种情况妹妹只能得到一种糖果。

平均情况:每个糖都有两个,这种情况妹妹可以拿到所有种类,数量与 极端情况1 一样。

观察前面的 示例2 ,我们发现,题目并不简单:由博弈的思想,可以发现,我们必须尽可能的避免姐弟两人分得糖果种类可能一样的情况发生。

如上,姐姐拿[1,3]或[1,4],弟弟可以拿[1,4]或[1,3],这时姐弟两人所得糖果种类相等,但我们要避免,所以,姐姐只能拿[3,4]。

由此可知,求糖果的种类数使用 hash 即可。(同样,利用hashset不保存相同值的特点)

如下:

e23fc95800a513a8c16fdd78c3ae54e3.png

代码展示:

class Solution {

public int distributeCandies(int[] candies) {

Set nums = new HashSet<>();

for (int i = 0; i < candies.length; i++) {

nums.add(candies[i]);

}

int numNums = nums.size();

int numTarget = candies.length / 2;

return numNums >= numTarget ? numTarget : numNums;

}

}

(所用为java代码)

本文同步分享在 博客“行舟客”(CSDN)。

如有侵权,请联系 support@oschina.cn 删除。

本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。

这篇关于Java代码题m个小朋友分糖果,巧解“博弈”型算法题:分糖果问题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

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