结论
结论 : 所有正反面不相同的卡片都是可能的候选解,在里面找一个和所有正反面相同的卡片的值都不相等的最小值就好了
逻辑 : 去掉所有正反面相同的卡片以后,剩下得卡堆里面选择任意一张作为基准牌 ,卡堆里面正面和基准牌相同的卡片背面一定和他不同,背面和基准牌相同的卡片正面一定和他不同
下面都可以不用看了
证明 :
去掉所有正反面相同的卡片以后,剩余卡片里面任意一张的正面记为 $a_i$ 背面记为 $b_i$ 满足:
$$a_i != b_i$$
在里面选择第 $i$ 张卡片的任意一面 $a_i$ 作为基准,其他所有的卡片满足下面的情况 :
如果另一张卡片的正面和 $a_i$ 相等 ,那么一定有
$$a_j == a_i$$
又因为另一张卡片的正面和背面不相等 $a_j != b_j$ , 那么一定有
$$b_j != a_i$$
所以,选择任意一张卡片的任意一面作为基准面,和他相等记为 $1$ 不等记为 $0$ 那么剩下的所有的卡片可以表示成下面 的三种情况:
正面和基准牌相同的卡片背面一定和他不同,背面和基准牌相同的卡片正面一定和他不同
这种牌随便翻翻 一定赢
总的来说 就是不玩这种卡片:
最后考虑到包含相同卡片的全体集合 只需要选择的基准牌和任意一张相同卡片的值都不同即可:
class Solution {
public int flipgame(int[] a, int[] b) {
int n = a.length;
HashSet<Integer> s = new HashSet<Integer>();
for(int i = 0 ; i < n ; i++){
if(a[i] == b[i]){
s.add(a[i]);
}
}
int res = Integer.MAX_VALUE;
for(int i = 0 ; i < n ; i++){
if(!s.contains(a[i])){
res =Math.min(res,a[i]);
}
}
for(int i = 0 ; i < n ; i++){
if(!s.contains(b[i])){
res =Math.min(res,b[i]);
}
}
if(res == Integer.MAX_VALUE) return 0;
return res;
}
}