【Everyday】(1)拿手套问题 - Everyday - SegmentFault
在地下室里放着n种颜色的手套,手套分左右手,但是每种颜色的左右手手套个数不一定相同。A先生现在要出门,所以他要去地下室选手套。但是昏暗的灯光让他无法分辨手套的颜色,只能分辨出左右手。所以他会多拿一些手套,然后选出一双颜色相同的左右手手套。现在的问题是,他至少要拿多少只手套(左手加右手),才能保证一定能选出一双颜色相同的手套。
给定颜色种数n(1≤n≤13),同时给定两个长度为n的数组left,right,分别代表每种颜色左右手手套的数量。数据保证左右的手套总数均不超过26,且一定存在至少一种合法方案。
Read full article from 【Everyday】(1)拿手套问题 - Everyday - SegmentFault
在地下室里放着n种颜色的手套,手套分左右手,但是每种颜色的左右手手套个数不一定相同。A先生现在要出门,所以他要去地下室选手套。但是昏暗的灯光让他无法分辨手套的颜色,只能分辨出左右手。所以他会多拿一些手套,然后选出一双颜色相同的左右手手套。现在的问题是,他至少要拿多少只手套(左手加右手),才能保证一定能选出一双颜色相同的手套。
给定颜色种数n(1≤n≤13),同时给定两个长度为n的数组left,right,分别代表每种颜色左右手手套的数量。数据保证左右的手套总数均不超过26,且一定存在至少一种合法方案。
测试样例
4,[0,7,1,6],[1,5,0,6]
返回10(解释:可以左手手套取2只,右手手套取8只)
解决这个问题的时候,根据测试样例的提示找到了思路,(1)从一只手中取出一种颜色,然后在另一种手中取出所有颜色,那么这个时候,就可以保证一定会出现满足条件的情况,大致思路理清了,然后考虑具体算法实现,(2)找出一种颜色,在给定的数组中找出一种颜色,从中选取一个不就可以了,但是这个时候要考虑的问题是,在另外一只手中,你索取的颜色,可能并没有对应,考虑到最坏情况,当我们在一只手中,取一个颜色手套的时候,我们要将另一只手中对应颜色为0的所有颜色取尽,然后在多取一个,才可以保证去取出一个可以和另一只手对应。(3)接下来是如何在另一只手中将所有可能的颜色都取出来呢?这个问题首先考虑到的是将所有的全部拿一遍就好了呀,但是这样并不是最优的,考虑如果右手是4,4,3,我们其实是只需要取9个就可以了,就可以将所有的颜色取一遍,规律是在所有的数目进行排序后,对于最小的数字,我们只需要取1个就好了,因此我们可以在对其进行一个最小值标记,最后判断最小值是否为大于1,大于1的话,就要减去其超出1的部分。还有对于这个最小值的选取,是不可以选取对应数组的值为0的,如果有该值被选取了,实际上是可以的,因为我们要确保的是找出所有的颜色种类,这对我们的选取是没有任何影响的。(4)到这里还没有完,由于看测试用例,所以自己的思路潜移默化中受了测试用例的影响,所以也是跟着进去了,只考虑从左手拿一种颜色,而忘记了考虑可以先从右手拿出一种颜色的问题。因此导致结果迟迟不对。
public static int findOneColorCost(int[] array1,int[] array2){
int cost = 0;
for(int i=0; i<array1.length; i++)
if(array2[i]==0)
cost += array1[i];
return ++cost;
}
public static int getAllColorCost(int[] array1,int[] array2){
int min = -1;
int cost = 0;
for(int j=0; j<array1.length; j++){
if(min==-1&&array2[j]!=0)
min = array2[j];
else if(min!=-1&&array2[j]<min&&array2[j]!=0)
min = array2[j];
cost += array2[j];
}
if(min>1)
cost = cost - min + 1;
return cost;
}
public static void main(String[] args){
int [] left = {1,2,0,1,3,1};
int [] right= {0,0,0,2,0,1};
System.out.println(findMinimum(6,left,right));
}
}
优化发散
不均等配对问题,择其1,另一配对中选择所有从而达成能够组成一对。测试用例引导带来一个误区,考虑问题要全面。