OR57 手套

简介: OR57 手套

练习题入口

问题描述

   在地下室里放着n种颜色的手套,手套分左右手,但是每种颜色的左右手手套个数不一定相同。A先生现在要出门,所以他要去地下室选手套。但是昏暗的灯光让他无法分辨手套的颜色,只能分辨出左右手。所以他会多拿一些手套,然后选出一双颜色相同的左右手手套。现在的问题是,他至少要拿多少只手套(左手加右手),才能保证一定能选出一双颜色相同的手套。

   给定颜色种数n(1≤n≤13),同时给定两个长度为n的数组left,right,分别代表每种颜色左右手手套的数量。数据保证左右的手套总数均不超过26,且一定存在至少一种合法方案。

测试样例:


52bfc07ec492161fd07e7ba2b1845cc5_06badf1acaf6411db1c10764c9fdf62f.png52bfc07ec492161fd07e7ba2b1845cc5_06badf1acaf6411db1c10764c9fdf62f.png52bfc07ec492161fd07e7ba2b1845cc5_06badf1acaf6411db1c10764c9fdf62f.png

解题分析

       解析这道题,我们可以分成两步:

第一步:怎样选取一定能保证配对一双手套

如上图,我们是不是可以把左手套全部取完,然后再在右手套中取一双,这样就能保证最少配对一双手套(反之把右手套取完)。

例如:把左手套取完 2+3+2+4 = 13

          右手套至少要有一只用来配对:1

总数:13+1=14

第二步:如何确保取出的手套是最少的

  我们可以对比左和右中的手套总数,然后分别减去其中最小的数量的手套数,最后加1

  那边算出的总数少就用哪边的。

为什么要减去数量最少的那一种手套?

     假设我们减去 left[1]位置的手套,也就是减3,然后再+1算出总数,+1的目的是想让减去那一种手套也留下一只。

      结果为 9 ,我们想要这9只的手套的数量分别为 2  1  2  4,此时就不能按照我们心中所想了,会有多种排列组合 例如 0  3  2  4   left[0]种类的手套直接没有!!!

   

     所以我们要减去数量最小的手套,我们再取的时候就只会有一种组合

第三步:解决某一种手套为0的情况

   当有一种手套为0时,我们再计算的结果就会超过手套总数,所以我们再算取出手套数时要先把为0放一边。

 这时,最下值也要变,从 0 变为 1

最后我们定义一个sum 把数量为0的手套的配对手套加起来,再与第二步算出的手套数相加

总步骤:      

代码实现

import java.util.*;
public class Gloves {
    public int findMinimum(int n, int[] left, int[] right) {
        // write code here
        int sumLeft = 0;
        int sumRight = 0;
        int minLeft = Integer.MAX_VALUE;
        int minRight = Integer.MAX_VALUE;
        int sum = 0;
        for(int i = 0;i < n;i++){
            if(left[i]*right[i] == 0){
                sum += left[i] + right[i];
            }else{
                sumLeft += left[i];
                sumRight += right[i];
                if(minLeft > left[i]){
                    minLeft = left[i];
                }
                if(minRight > right[i]){
                    minRight = right[i];
                }
            }
        }
        return Math.min(sumLeft - minLeft+1,sumRight - minRight +1)+1+sum;
    }
}
相关文章
|
5月前
|
人工智能 缓存 安全
刚刚 Claude Code 源码泄露!我扒出了 11 个隐藏秘密
大家好,我是程序员鱼皮 👨🏻‍💻。 堪称全球最强的 AI 编程工具 Claude Code 的 50 多万行源码泄露了!一家以 AI 安全著称的公司,自己却在代码发布环节翻了车。 针对这件事,我只想说两个字: 感谢! 这份源码对学技术的同学来说简直是宝藏资源啊,过年了过年了! 那 Claude Code 源码具体是怎么泄露的?源码里有哪些精妙的设计?为什么它能做到 AI 编程工具的天花板?
505 0
|
6月前
|
SQL 关系型数据库 MySQL
批量操作性能飙升:从30秒到1秒的三种实战方法
业务系统中经常需要批量导入或更新大量数据(如Excel上传、定时同步)。许多开发人员采用循环单条执行的方式,导致1万条数据耗时30秒以上,严重影响用户体验。本文从数据库IO、事务开销、锁竞争三个角度分析单条操作的性能瓶颈,并给出三种优化方案:批量INSERT、LOAD DATA文件导入、批量UPDATE用临时表。每种方案均附实测数据对比与适用场景说明,帮助读者在1万\~100万行级别批量操作中选择最优策略。
|
机器学习/深度学习 算法 测试技术
DeepSeek-R1-0528:小更新大升级
今天,DeepSeek R1 开源发布了其“小版本”升级——DeepSeek-R1-0528。
1746 23
DeepSeek-R1-0528:小更新大升级
|
机器学习/深度学习 5G
5G中的调制技术:从QPSK到256QAM,赋能高速率通信
5G中的调制技术:从QPSK到256QAM,赋能高速率通信
4658 5
|
缓存 异构计算 Docker
构建高性能LLM推理服务的完整方案:单GPU处理172个查询/秒、10万并发仅需15美元/小时
本文将通过系统性实验不同的优化技术来构建自定义LLaMA模型服务,目标是高效处理约102,000个并行查询请求,并通过对比分析确定最优解决方案。
1328 0
构建高性能LLM推理服务的完整方案:单GPU处理172个查询/秒、10万并发仅需15美元/小时
|
机器学习/深度学习 人工智能 自然语言处理
抖音封号一般封多久?
根据2023年9月更新的《抖音创作者权益保护指引》,平台将封号时长划分为四级响应机制:
|
缓存 数据处理 UED
【Uniapp 专栏】Uniapp 开发中的疑难问题解决与进阶策略
【5月更文挑战第17天】在 Uniapp 开发中,解决页面间数据传递、网络请求异常、屏幕适配及性能优化等问题至关重要。利用路由参数传递复杂数据,如`uni.navigateTo`和`JSON.stringify`;处理网络请求异常时,添加错误处理机制增强健壮性;使用响应式设计和缓存策略优化布局和性能。针对组件问题,需排查依赖和配置,而平台差异则需定制化处理。通过不断学习和实践,提升开发技能,确保项目成功实施。
588 2
【Uniapp 专栏】Uniapp 开发中的疑难问题解决与进阶策略
|
机器学习/深度学习 人工智能 缓存
SepLLM:开源大模型加速神器!400万Token长文本推理提速50%,告别OOM噩梦
SepLLM 是一个用于加速大语言模型的高效框架,通过压缩段落信息并消除冗余标记,显著提高了模型的推理速度和计算效率,适用于长文本处理和多场景部署。
799 7
SepLLM:开源大模型加速神器!400万Token长文本推理提速50%,告别OOM噩梦
|
缓存 网络协议 前端开发
Web 性能优化|了解 HTTP 协议后才能理解的预加载
本文旨在探讨和分享多种预加载技术及其在提升网站性能、优化用户体验方面的应用。
Web 性能优化|了解 HTTP 协议后才能理解的预加载
|
数据采集 监控 大数据
大数据项目管理:从规划到执行的全景指南
大数据项目管理:从规划到执行的全景指南
374 4