https://leetcode.com/problems/card-flipping-game/
https://zxi.mytechroad.com/blog/greedy/leetcode-822-card-flipping-game/
题目大意：每张牌的正反面各印着一个数，你可以随便翻牌。找出一个最小的数使得其他牌当前正面的数值都不和它相等。
所以，如果一个牌正反面相等，那么翻转不翻转没什么意义。否则可以翻转，求翻哪些之后会得到最小，就是如果不翻转的最小值和翻转了之后的最小值的最小值。使用set保存一下正反面相等的数字，这些是一定不能在正面出现的，然后找出不在这个set里面的正反面的最小值即可。
怎么理解？首先正反面相同的翻转没有意义，然后找在正反面的最小值把它翻转到正面来。那么有人会想，如果翻转这个牌和其他的正面的牌有冲突怎么办？其实，如果和set里面的牌有冲突没有意义，如果和不在set里面的正面的牌有冲突就把这个冲突的牌也翻转即可。所以，不用考虑这么多。。
时间复杂度是O(N)，空间复杂度最坏是O(N).
https://leetcode.com/problems/card-flipping-game/discuss/125810/Java-solution-using-HashSet-(The-description-in-the-problem-really-confuses-me...)
https://leetcode.com/articles/card-flipping-game/
我们将fronts和backs里面出现的数对应的另一面的数字记录下来，比如对于1这个数字，记录他对应着1，4着两个数，然后从小到大遍历，第一个没出现相同对应数字的数就是答案
https://blog.csdn.net/birdreamer/article/details/80041204
def flipgame(self, fronts, backs):
"""
:type fronts: List[int]
:type backs: List[int]
:rtype: int
"""
all_cards = set(fronts + backs)
a = {fronts[i] for i in range(len(fronts)) if fronts[i]==backs[i]}
all_cards = all_cards - a
return min(all_cards) if all_cards else 0
On a table are
N cards, with a positive integer printed on the front and back of each card (possibly different).
We flip any number of cards, and after we choose one card.
If the number
X on the back of the chosen card is not on the front of any card, then this number X is good.
What is the smallest number that is good? If no number is good, output
0.
Here,
fronts[i] and backs[i] represent the number on the front and back of card i.
A flip swaps the front and back numbers, so the value on the front is now on the back and vice versa.
Example:
Input: fronts = [1,2,4,4,7], backs = [1,3,4,1,3] Output:2Explanation: If we flip the second card, the fronts are[1,3,4,4,7]and the backs are[1,2,4,1,3]. We choose the second card, which has number 2 on the back, and it isn't on the front of any card, so2is good.
Note:
1 <= fronts.length == backs.length <= 1000.1 <= fronts[i] <= 2000.1 <= backs[i] <= 2000.
题目大意：每张牌的正反面各印着一个数，你可以随便翻牌。找出一个最小的数使得其他牌当前正面的数值都不和它相等。
int flipgame(vector<int>& fronts, vector<int>& backs) {
unordered_set<int> same;
for (int i = 0; i < fronts.size(); ++i)
if (fronts[i] == backs[i])
same.insert(fronts[i]);
int ans = INT_MAX;
for (int v : fronts)
if (v < ans && !same.count(v)) ans = v;
for (int v : backs)
if (v < ans && !same.count(v)) ans = v;
return ans == INT_MAX ? 0 : ans;
}
https://buptwc.com/2018/05/11/Leetcode-822-Card-Flipping-Game/
如果我们从fronts和backs中最小的数开始考虑，在example中就是1,那么1对应着两张卡，分别是 1，1 和 1，4，对于1，1我们无论如何翻转1都会在正面出现，所以1不可能是good number；对于2来说，2对应着2，3一张卡，那么只要将3朝上，fronts中就没了2,(关键就是只要一个数不是同时出现在一张卡的正反两面，我们通过一定的翻转就一定可以使这个数成为good number)，因为我们是从小到大遍历，所以此时2就是最后答案。注意数据长度不超过1000，数据值不超过2000，说明n^2的方案是可行的
所以，如果一个牌正反面相等，那么翻转不翻转没什么意义。否则可以翻转，求翻哪些之后会得到最小，就是如果不翻转的最小值和翻转了之后的最小值的最小值。使用set保存一下正反面相等的数字，这些是一定不能在正面出现的，然后找出不在这个set里面的正反面的最小值即可。
怎么理解？首先正反面相同的翻转没有意义，然后找在正反面的最小值把它翻转到正面来。那么有人会想，如果翻转这个牌和其他的正面的牌有冲突怎么办？其实，如果和set里面的牌有冲突没有意义，如果和不在set里面的正面的牌有冲突就把这个冲突的牌也翻转即可。所以，不用考虑这么多。。
时间复杂度是O(N)，空间复杂度最坏是O(N).
https://leetcode.com/problems/card-flipping-game/discuss/125810/Java-solution-using-HashSet-(The-description-in-the-problem-really-confuses-me...)
The intuition behind my solution is: If a card has the same number both on the front side and the back side, then this number is fixed, which means this number will never be a good number. On the other hand, for other numbers which are not fixed, after several flips, we could always find a way to flip this number to the front when currently this number is not showing.
The problem's meaning is if you could find a way to flip it up when currently this number is not showing on any of the card(including the chosen one), then this number could be considered as a good number.
The problem's meaning is if you could find a way to flip it up when currently this number is not showing on any of the card(including the chosen one), then this number could be considered as a good number.
We check whether the number is in the hashset because if a number is in the hashset, this number will always face to us. Make sense?
Consider an example:
After we build up our hashset, we check the fronts number and backs number one by one. When we encounter
However, for other numbers, which are not presented in the hashset, we could always find a way to filp it up as a good number. i.e. for number
fronts = [1,2,2,4,2], backs = [1,3,4,1,3], in this case, hashset will only contains a number 1.After we build up our hashset, we check the fronts number and backs number one by one. When we encounter
1, it has been in the hashset, which means it will never be a good number because there will always be a 1 faces to us.However, for other numbers, which are not presented in the hashset, we could always find a way to filp it up as a good number. i.e. for number
2, firstly we flip the second, third, fifth card so that all the 2s are in the back side. Now the cards become [1, 3, 4, 4, 3] and [1, 2, 2, 1, 2] Then we flip any of second, third, fifth. At this time, 2 will be considered as a good number. Since the 2 is the minimum valid good number. It will be the result.class Solution {
public int flipgame(int[] fronts, int[] backs) {
Set<Integer> set = new HashSet<>();
int n = fronts.length;
for (int i = 0; i < n; i++) {
if (fronts[i] == backs[i]) {
set.add(fronts[i]);
}
}
int min = Integer.MAX_VALUE;
for (int i = 0; i < n; i++) {
if (!set.contains(backs[i])) {
min = Math.min(min, backs[i]);
}
if (!set.contains(fronts[i])) {
min = Math.min(min, fronts[i]);
}
}
return min == Integer.MAX_VALUE ? 0 : min;
}
If
In case that
fronts[i] == backs[i], it means that fronts[i] is sure to appear on the table, no matter how we flap this card.In case that
fronts[i] and backs[i] are same, fronts[i] become impossible to be good number, so I add it to a set same.
If
fronts[i] != backs[i], we can always hide either number by flapping it to back.
Then loop on all numbers and return the minimum.
https://leetcode.com/articles/card-flipping-game/
If a card has the same value
x on the front and back, it is impossible to win with x. Otherwise, it has two different values, and if we win with x, we can put x face down on the rest of the cards.
Remember all values
same that occur twice on a single card. Then for every value x on any card that isn't in same, x is a candidate answer. If we have no candidate answers, the final answer is zero.
public int flipgame(int[] fronts, int[] backs) {
Set<Integer> same = new HashSet();
for (int i = 0; i < fronts.length; ++i)
if (fronts[i] == backs[i])
same.add(fronts[i]);
int ans = 9999;
for (int x : fronts)
if (!same.contains(x))
ans = Math.min(ans, x);
for (int x : backs)
if (!same.contains(x))
ans = Math.min(ans, x);
return ans % 9999;
}
我们将fronts和backs里面出现的数对应的另一面的数字记录下来，比如对于1这个数字，记录他对应着1，4着两个数，然后从小到大遍历，第一个没出现相同对应数字的数就是答案
def flipgame(fronts, backs): import collections n = len(fronts) d = collections.defaultdict(list) for i in xrange(n): d[fronts[i]].append(backs[i]) d[backs[i]].append(fronts[i]) rec = fronts + backs rec.sort() for e in rec: if e not in d[e]: return e return 0
https://blog.csdn.net/birdreamer/article/details/80041204
def flipgame(self, fronts, backs):
"""
:type fronts: List[int]
:type backs: List[int]
:rtype: int
"""
all_cards = set(fronts + backs)
a = {fronts[i] for i in range(len(fronts)) if fronts[i]==backs[i]}
all_cards = all_cards - a
return min(all_cards) if all_cards else 0
