Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/822.html
822. Card Flipping Game
Level
Medium
Description
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: 2
Explanation: 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, so 2 is good.
Note:
1 <= fronts.length == backs.length <= 1000.1 <= fronts[i] <= 2000.1 <= backs[i] <= 2000.
Solution
If a card has the same number on both sides, then the number on the card is not good, since the number will always be on the front of the card, no matter whether the card is flipped.
Use two tree sets to store all the numbers on the cards and to store the numbers that are repeated, respectively. Here “repeated” means that there exists at least one card such that the number is on both sides of the card. The elements in both tree sets are sorted in ascending order.
If both tree sets have the same size, then all the numbers are repeated, so no number is good and return 0. Otherwise, loop over both tree sets and find the smallest number that is in the set of all the numbers but not in the set of repeated numbers, and return the number.
-
class Solution { public int flipgame(int[] fronts, int[] backs) { TreeSet<Integer> completeSet = new TreeSet<Integer>(); TreeSet<Integer> repeatSet = new TreeSet<Integer>(); int length = fronts.length; for (int i = 0; i < length; i++) { completeSet.add(fronts[i]); completeSet.add(backs[i]); if (fronts[i] == backs[i]) repeatSet.add(fronts[i]); } int size1 = completeSet.size(), size2 = repeatSet.size(); if (size1 == size2) return 0; if (size2 == 0) return completeSet.first(); int index2 = 0; while (index2 < size2) { int num = completeSet.pollFirst(); int repeat = repeatSet.pollFirst(); if (num < repeat) return num; index2++; } return completeSet.first(); } } -
// OJ: https://leetcode.com/problems/card-flipping-game/ // Time: O(N) // Space: O(N) class Solution { public: int flipgame(vector<int>& F, vector<int>& B) { unordered_set<int> same; int N = F.size(), mn = INT_MAX; for (int i = 0; i < N; ++i) { if (F[i] == B[i]) same.insert(F[i]); } for (int i = 0; i < N; ++i) { if (same.count(F[i]) == 0) mn = min(mn, F[i]); if (same.count(B[i]) == 0) mn = min(mn, B[i]); } return mn == INT_MAX ? 0 : mn; } }; -
class Solution: def flipgame(self, fronts: List[int], backs: List[int]) -> int: same = {a for a, b in zip(fronts, backs) if a == b} ans = 9999 for x in chain(fronts, backs): if x not in same: ans = min(ans, x) return ans % 9999 ############ class Solution: def flipgame(self, fronts, backs): """ :type fronts: List[int] :type backs: List[int] :rtype: int """ s = set() res = float('inf') for f, b in zip(fronts, backs): if f == b: s.add(f) for f in fronts: if f not in s: res = min(res, f) for b in backs: if b not in s: res = min(res, b) return 0 if res == float('inf') else res -
func flipgame(fronts []int, backs []int) int { s := map[int]bool{} for i, v := range fronts { if v == backs[i] { s[v] = true } } ans := 9999 for _, v := range fronts { if !s[v] { ans = min(ans, v) } } for _, v := range backs { if !s[v] { ans = min(ans, v) } } return ans % 9999 } func min(a, b int) int { if a < b { return a } return b }