【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)到这里还没有完,由于看测试用例，所以自己的思路潜移默化中受了测试用例的影响，所以也是跟着进去了，只考虑从左手拿一种颜色，而忘记了考虑可以先从右手拿出一种颜色的问题。因此导致结果迟迟不对。
实现代码
Read full article from 【Everyday】(1)拿手套问题 - Everyday - SegmentFault
No comments:
Post a Comment