当前位置：网站首页>详解牛客----手套

详解牛客----手套

2022-04-23 16:37:00 【长大Leslie】

原题链接：手套__牛客网

解题思路：

1. 首先考虑两边手套都不出现0的情况

以取左边的为例子：把左边所有的手套数量减去数量最小的颜色的数量然后+1， 对应上图就是取17-2+1=16只，也就是说，左边取16只手套，肯定把所有颜色都取出，现在只要往另一只手中取一只就能匹配了。假设取15只手套，那么可能存在这么一种情况：取了4只黄色，5只绿色，6只蓝色；那么橙色的就可能取不到，所以取15只手套不能100%的把所有可能出现的颜色都取出。同样的操作把右边的走一遍，判断左边和右边所取的数量哪一种更小，然后最后的值+1就能匹配了。

2. 存在两边可能出现 0 的情况

最终代码实现：

 

class Gloves {
public:
    int findMinimum(int n, vector<int> left, vector<int> right) {
        // write code here
        int sum=0;
        int left_min=INT_MAX;
        int right_min=INT_MAX;
        int left_sum=0,right_sum=0;
        for(int i=0;i<n;i++)
        {
            if(left[i]*right[i]==0)
            sum+=left[i]+right[i];//如果存在一个为0，就要把这种情况求出
            else
            {
                left_sum+=left[i];
                left_min=left[i]<left_min?left[i]:left_min;
                 right_sum+=right[i];
                right_min=right[i]<right_min?right[i]:right_min;
            }
        }
        return sum+=(left_sum>right_sum?(right_sum-right_min+1):(left_sum-left_min+1))+1;
    }
};

版权声明
本文为[长大Leslie]所创，转载请带上原文链接，感谢
https://blog.csdn.net/m0_56695823/article/details/124317478

边栏推荐

猜你喜欢

随机推荐