题解 | #手套#

手套

https://www.nowcoder.com/practice/365d5722fff640a0b6684391153e58d8

import java.util.*;

public class Gloves {
    public int findMinimum(int n, int[] left, int[] right) {
        int count=0;//定义出现0的情况先.需要先拿几只手套,来简化问题
        int leftSum=0;//左右手手套数量的和
        int rightSum=0;
        int leftMin=Integer.MAX_VALUE;;//左右手手套数量的最小值,一定要定义最大的,这样才能更新得到数组中的最小值,定义为0的话,直接不用比较了,最后的最小值一定是0
        int rightMin=Integer.MAX_VALUE;;
        for(int i=0;i<n;i++){
            if(left[i]*right[i]==0){//出现颜色为0的情况
            count+=left[i]+right[i];//因为不知道是那一只手为0,所以全部加,反正为0,只加另一只手
            }else{//这里处理的是所有的非0的颜色的情况(越过了包含0的下标,不算进去)-->正常情况的,简化了的
            leftSum+=left[i];
            if(leftMin>left[i]){
                leftMin=left[i];//更新最小值
            }
            rightSum+=right[i];
            if(rightMin>right[i]){
                rightMin=right[i];//更新最小值
            }
            }
        }
        //得到了左边的sum,及min及要先拿走的属于0的颜色(右边也一样)
        int minNum=Math.min(leftSum-leftMin+1,rightSum-rightMin+1)+1;//得到简化后的正常所情况需拿的手套数量,拿完,加一
        return count+minNum;//最后的数量是简化后的加上提前拿走的
    }
}

一定能凑出,而且还要最少:所有的最坏的情况发生,然后在最坏情况发生后,只要拿到一次满足条件的手套即可,不再多拿

--->正常情况:没有空白手套的情况:即所有的手套都至少要一只对应(左右手)

--->怎么样才能保证一定能凑出一双手套?

--->发生最坏的情况:左手的拿了4+3+2+1=10只-->所有的颜色(最少的拿种颜色拿一只即可,最坏的情况是把数量多的全部拿了,最后才轮到数量最少的)

--->然后右手随便拿一只即可-->1

--->一共11只必然凑出一双

--->又或者:右手拿了5+3+2+1=11只--->拿到了所有的颜色

--->左手随便拿一只-->1

一共12只必然凑出一双

--->比较左/右手拿完的两种情况最小值,结果取最小即可

---->怎么才能得出某一只手需要几只手套才能一定凑出所有的颜色:所有的手套数量求和,然后减去最小的数量,然后加一(减去最小的,代表现在只剩最小数量的那种颜色没有拿了,+1代表拿了最小数量的那种颜色的手套)

---->2+3+2+4-1+1=10

--->不正常情况:

左右手出现了单独的手套,即某种颜色只有0只的情况

--->我们首先得把0只手套的手对应的另外一只手的颜色全部拿完

--->如:左手0右手1,把1拿了,右手0左手1,把1拿了--->所以先提前拿了2

--->然后就可以简化题目了

--->因为拿了单独手套的颜色的话,它是一定不能凑出一对的,所以这是坏的情况,把它拿了就去掉坏的情况了

--->有0的那只手,即便你拿了所有的颜色,另外一只手只要拿0对应的颜色,就永远凑不出一对,所以必须得先把0对应的颜色拿完,再拿其他颜色才能凑出

---->简化后左右手都只剩两种颜色了,按照正常情况求出要拿多少只即可

--->最后把2加上剩下的正常情况的即可:2+8=10只

全部评论
import java.util.*; public class Gloves { public int findMinimum(int n, int[] left, int[] right) { int ret = 0; for (int i = 0; i < left.length; i++) { if (left[i] == 0) { //处理异常情况 ret += right[i]; right[i] = 0; } if (right[i] == 0) { ret += left[i]; left[i] = 0; } } int leftMin = Arrays.stream(left).filter(num -> num != 0) .min().orElse(0);//找不到最小值返回0 int rightMin = Arrays.stream(right).filter(num -> num != 0) .min().orElse(0); int leftSum = Arrays.stream(left).sum(); int rightSum = Arrays.stream(right).sum(); if (leftSum < rightSum) { return leftSum - leftMin + 2 + ret; } else { return rightSum - rightMin + 2 + ret; } } }
点赞 回复 分享
发布于 2023-10-18 20:27 陕西
老铁,你真牛,点赞
点赞 回复 分享
发布于 2023-10-18 00:22 广东

相关推荐

不愿透露姓名的神秘牛友
今天 12:31
以前小时候我最痛恨出轨、偷情的人,无论男女,为什么会出轨?现在我成了自己最讨厌的人,没想到分享的东西在牛客会被这么多人看,大家的评价都很中肯,我也认同,想过一一回复,但我还是收声了,我想我应该说说这件事,这件事一直压在我心里,是个很大的心结,上面说了人为什么出轨,我大概能明白了。我们大一下半年开始恋爱,开始恋爱,我给出了我铭记3年的承诺,我对她好一辈子,我永远不会背叛,我责任心太重,我觉得跟了我,我就要照顾她一辈子,我们在一起3年我都没有碰过她,她说往东我就往东,她说什么我做什么,她要我干什么,我就干什么!在学校很美好,中途也出过一些小插曲,比如男闺蜜、男闺蜜2号等等等。但我都强迫她改掉了,我...
牛客刘北:两个缺爱的人是没有办法好好在一起的,但世界上哪有什么是非对错?你后悔你们在一起了,但是刚刚在一起的美好也是真的呀,因为其他人的出现,你开始想要了最开始的自己,你的确对不起自己,21岁的你望高物远,你完全可以不谈恋爱,去过你想要的生活,你向往自由,在一起之后,你要想的不是一个人,而是两个人,你不是变心了,就像你说的,你受够了,你不想包容了,冷静几天是你最优的选择,爱人先爱己。
社会教会你的第一课
点赞 评论 收藏
分享
牛客38347925...:9,2学生暑期实习失利开始投小厂,给这群人整自信了
点赞 评论 收藏
分享
06-02 15:17
门头沟学院 Java
心爱的idea:怎么会呢 应该是打招呼有问题 问就说实习6个月全国可飞随时到岗
点赞 评论 收藏
分享
评论
2
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务