Leetcode 822 Card Flipping Game

发表于 |

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.

分析：
如果我们从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的方案是可行的

思路：
我们将fronts和backs里面出现的数对应的另一面的数字记录下来，比如对于1这个数字，记录他对应着1，4着两个数，然后从小到大遍历，第一个没出现相同对应数字的数就是答案

总结：
这道题稍微想一下并不难，但是在leetcode上踩的人有丶多，说明大家对单纯的逻辑题的解法还是不太熟。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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

time: O(n)
space: O(n)
difficulty: medium
169 / 169 test cases passed
runtime: 85 ms