新型城镇化建设网站,商城网站源码免费,用网站做邮箱,招聘室内设计文章目录 Card Flipping Game 翻转卡片游戏问题描述#xff1a;EN 分析代码 Tag Card Flipping Game 翻转卡片游戏
问题描述#xff1a;
在桌子上有 N 张卡片#xff0c;每张卡片的正面和背面都写着一个正数#xff08;正面与背面上的数有可能不一样#xff09;。
我们… 文章目录 Card Flipping Game 翻转卡片游戏问题描述EN 分析代码 Tag Card Flipping Game 翻转卡片游戏
问题描述
在桌子上有 N 张卡片每张卡片的正面和背面都写着一个正数正面与背面上的数有可能不一样。
我们可以先翻转任意张卡片然后选择其中一张卡片。
如果选中的那张卡片背面的数字 X 与任意一张卡片的正面的数字都不同那么这个数字是我们想要的数字。
哪个数是这些想要的数字中最小的数找到这些数中的最小值呢如果没有一个数字符合要求的输出 0。
其中, fronts[i] 和 backs[i] 分别代表第 i 张卡片的正面和背面的数字。
如果我们通过翻转卡片来交换正面与背面上的数那么当初在正面的数就变成背面的数背面的数就变成正面的数。
EN
You are given two 0-indexed integer arrays fronts and backs of length n, where the i t h i^{th} ith card has the positive integer fronts[i] printed on the front and backs[i] printed on the back. Initially, each card is placed on a table such that the front number is facing up and the other is facing down. You may flip over any number of cards (possibly zero).
After flipping the cards, an integer is considered good if it is facing down on some card and not facing up on any card.
Return the minimum possible good integer after flipping the cards. If there are no good integers, return 0. 1 f r o n t s . l e n g t h b a c k s . l e n g t h 1000 1 f r o n t s [ i ] 2000 1 b a c k s [ i ] 2000 1 fronts.length backs.length 1000\\ 1 fronts[i] 2000\\ 1 backs[i] 2000 1fronts.lengthbacks.length10001fronts[i]20001backs[i]2000
分析
看了半天没get到要点建议中英文都看一遍。
问题中有一套卡片卡片的正反都有数字一开始正面朝上反面朝下。
如果选择了一个卡片该卡片背面的数字x与此时任意正面的数字都不一样那么x就可以入选备选。 可以对任意卡片进行任意的反转找到最小的那个数字如果不存在这样的数字最后就是0。
所以问题就是找到一个策略来找出所有可能的备选数字然后排个序。 从问题中可以知道一种特殊的卡片即正反一样的数字这样的数字是不可能进入备选的基于这个条件可以进行初筛。
此外比较容易想到的就是如果front中没有出现过x而back中有x那么x一定可以是入选的。 如果在此基础进行扩展front出现了a个xback中出现了b个x那么x是否可以入选取决于这些x不能出现在同一个卡片上。如果这些卡片只是单面有x那么一定可以反转最后得到一面只有1个x。由于双面同值的已经被筛除所以在这个环节可以只讨论单面。
到此问题就变成先将双面同值的进行标记排除然后剩余的值都可以通过操作成为备选的number。
所以只需要在非双面同值的元素中找最小的时间复杂度 O ( N ) O(N) O(N),空间复杂度 O ( N ) O(N) O(N)
代码 public int flipgame(int[] fronts, int[] backs) {int[] set new int[2002];int INF 130;int n fronts.length,min INF;for(int i 0;in;i){if(fronts[i] backs[i]){set[fronts[i]];}}for(int i 0;in;i){if(fronts[i]minset[fronts[i]]0){min Math.min(min,fronts[i]);}if(backs[i]minset[backs[i]]0){min Math.min(min,backs[i]);}} return min INF?0:min;} 时间复杂度 O ( N ) O(N) O(N)
空间复杂度 O ( N ) O(N) O(N)
Tag
Array
Hash
