{"id":2779,"date":"2018-04-29T03:35:08","date_gmt":"2018-04-29T10:35:08","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=2779"},"modified":"2018-04-30T00:32:27","modified_gmt":"2018-04-30T07:32:27","slug":"leetcode-822-card-flipping-game","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/greedy\/leetcode-822-card-flipping-game\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 822. Card Flipping Game"},"content":{"rendered":"

Problem<\/h1>\n

\u9898\u76ee\u5927\u610f\uff1a\u6bcf\u5f20\u724c\u7684\u6b63\u53cd\u9762\u5404\u5370\u7740\u4e00\u4e2a\u6570\uff0c\u4f60\u53ef\u4ee5\u968f\u4fbf\u7ffb\u724c\u3002\u627e\u51fa\u4e00\u4e2a\u6700\u5c0f\u7684\u6570\u4f7f\u5f97\u5176\u4ed6\u724c\u5f53\u524d\u6b63\u9762\u7684\u6570\u503c\u90fd\u4e0d\u548c\u5b83\u76f8\u7b49\u3002<\/p>\n

On a table are\u00a0N<\/code>\u00a0cards, with a positive integer printed on the front and back of each card (possibly different).<\/p>\n

We flip any number of cards, and after we choose one\u00a0card.<\/p>\n

If the number\u00a0X<\/code>\u00a0on the back of the chosen\u00a0card is not on the front of any card, then this number X is good.<\/p>\n

What is the smallest number that is good?\u00a0 If no number is good, output\u00a00<\/code>.<\/p>\n

Here,\u00a0fronts[i]<\/code>\u00a0and\u00a0backs[i]<\/code>\u00a0represent the number on the front and back of card\u00a0i<\/code>.<\/p>\n

A\u00a0flip swaps the front and back numbers, so the value on the front is now on the back and vice versa.<\/p>\n

Example:<\/strong><\/p>\n

Input:<\/strong> fronts = [1,2,4,4,7], backs = [1,3,4,1,3]\r\nOutput:<\/strong> 2\r\nExplanation:<\/strong> If we flip the second card, the fronts are [1,3,4,4,7]<\/code> and the backs are [1,2,4,1,3]<\/code>. We choose the second card, which has number 2 on the back, and it isn't on the front of any card, so 2<\/code> is good.<\/pre>\n
Note:<\/strong><\/p>\n
    \n
  1. 1 <= fronts.length == backs.length\u00a0<=\u00a01000.<\/code><\/li>\n
  2. 1 <=\u00a0fronts[i]\u00a0<= 2000<\/code>.<\/li>\n
  3. 1 <= backs[i]\u00a0<= 2000<\/code>.<\/li>\n<\/ol>\n
    Solution: Hashset<\/strong><\/h1>\n
    C++<\/p>\n
    \/\/ Author: Huahua\r\n\/\/ Running time: 23 ms\r\nclass Solution {\r\npublic:\r\n  int flipgame(vector<int>& fronts, vector<int>& backs) {\r\n    unordered_set<int> same;\r\n    for (int i = 0; i < fronts.size(); ++i)\r\n      if (fronts[i] == backs[i])\r\n        same.insert(fronts[i]);\r\n    \r\n    int ans = INT_MAX;\r\n    for (int v : fronts)\r\n      if (v < ans && !same.count(v)) ans = v;\r\n    \r\n    for (int v : backs)\r\n      if (v < ans && !same.count(v)) ans = v;\r\n    \r\n    return ans == INT_MAX ? 0 : ans;\r\n  }\r\n};<\/pre>\n
     <\/p>\n","protected":false},"excerpt":{"rendered":"
    Problem \u9898\u76ee\u5927\u610f\uff1a\u6bcf\u5f20\u724c\u7684\u6b63\u53cd\u9762\u5404\u5370\u7740\u4e00\u4e2a\u6570\uff0c\u4f60\u53ef\u4ee5\u968f\u4fbf\u7ffb\u724c\u3002\u627e\u51fa\u4e00\u4e2a\u6700\u5c0f\u7684\u6570\u4f7f\u5f97\u5176\u4ed6\u724c\u5f53\u524d\u6b63\u9762\u7684\u6570\u503c\u90fd\u4e0d\u548c\u5b83\u76f8\u7b49\u3002 On a table are\u00a0N\u00a0cards, with a positive integer printed on the front and back of each card (possibly different). We flip any number…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[51,70],"tags":[88,82,177],"class_list":["post-2779","post","type-post","status-publish","format-standard","hentry","category-greedy","category-hashtable","tag-greedy","tag-hashtable","tag-medium","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/2779","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=2779"}],"version-history":[{"count":4,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/2779\/revisions"}],"predecessor-version":[{"id":2791,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/2779\/revisions\/2791"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=2779"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=2779"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=2779"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}