CardFlippingGame [source code]

public class CardFlippingGame {
static
/******************************************************************************/
class Solution {
    public int flipgame(int[] fronts, int[] backs) {
        int N = fronts.length;
        int[] total = new int[2 * N];
        Set<Integer> blocked = new HashSet<> ();
        for (int i = 0; i < N; i++) {
            total[i] = fronts[i];
            total[i + N] = backs[i];
            if (fronts[i] == backs[i])
                blocked.add (fronts[i]);
        }
        Arrays.sort (total);
        for (int i = 0; i < 2 * N; i++) {
            if (!blocked.contains (total[i]))
                return total[i];
        }
        return 0;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        CardFlippingGame.Solution tester = new CardFlippingGame.Solution();
    }
}

题目描述的很有问题, flip的次数不是给你的条件, 而是你自己选择的, 只要你最后能选择出来一个good number就行了;

大概思路很清晰, 不过因为是medium题目, 估计会卡复杂度; 所以能不能实现的更快一点;

说是flip, 其实就是每一个card选择一面;

不对, 思路其实不是很清晰;

再观察简化问题: 我选了一张卡, 然后选一个数字, 这个数字怎么才能good? 首先, 另外一张卡怎样可以跟我选的这张起冲突? 只要另外这张卡两面都是X, 那么我X肯定就不行了; 只要另外这张卡至少有一面不是X, 那么X就没有问题;

只要选择一个数字X, 保证他不可能跟任何一张卡片起冲突就行了; 有一个naive的做法, 写写看;

没想到这个思路是对的, 漂亮的一次AC;

所以观察的时候, 还是要想着用另外的描述方式去理解题目给的限制条件; 尤其是这个描述, 越finer-grained越好;

UNFINISHED

uwi:

class Solution {  
    public int flipgame(int[] fronts, int[] backs) {  
        int n = fronts.length;  
        outer:  
        for(int i = 1;i <= 2000;i++){  
            boolean ok = false;  
            for(int j = 0;j < n;j++){  
                if(fronts[j] == i){  
                    if(backs[j] == i)continue outer;  
                }  
                if(backs[j] == i || fronts[j] == i)ok = true;  
            }  
            if(ok)return i;  
        }  
        return 0;  
    }  
}

好像跟我思路差不多, 不过没有explicit的用我的那个set和大array的做法;

他用了6分钟;

Problem 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.

Difficulty:Medium
Total Accepted:867
Total Submissions:3.2K
Contributor:awice