在自己的电脑做网站空间,丁香花影视大全,云主机怎样做网站,访问国外网站dns以下为力扣官方题解#xff0c;及本人代码 822. 翻转卡片游戏 题目题意示例 1示例 2提示 官方题解哈希集算法总结复杂度 本人代码Java提交结果#xff1a;通过 题目
题意 在桌子上有 n n n 张卡片#xff0c;每张卡片的正面和背面都写着一个正数#xff08;正面与背面上…以下为力扣官方题解及本人代码 822. 翻转卡片游戏 题目题意示例 1示例 2提示 官方题解哈希集算法总结复杂度 本人代码Java提交结果通过 题目
题意 在桌子上有 n n n 张卡片每张卡片的正面和背面都写着一个正数正面与背面上的数有可能不一样。 我们可以先翻转任意张卡片然后选择其中一张卡片。 如果选中的那张卡片背面的数字 x x x 与任意一张卡片的正面的数字都不同那么这个数字是我们想要的数字。 哪个数是这些想要的数字中最小的数找到这些数中的最小值呢如果没有一个数字符合要求的输出 0 0 0 。 其中, f r o n t s [ i ] fronts[i] fronts[i] 和 b a c k s [ i ] backs[i] backs[i] 分别代表第 i i i 张卡片的正面和背面的数字。 如果我们通过翻转卡片来交换正面与背面上的数那么当初在正面的数就变成背面的数背面的数就变成正面的数。 示例 1 输入 f r o n t s [ 1 , 2 , 4 , 4 , 7 ] , b a c k s [ 1 , 3 , 4 , 1 , 3 ] fronts [1,2,4,4,7], backs [1,3,4,1,3] fronts[1,2,4,4,7],backs[1,3,4,1,3] 输出 2 2 2 解释假设我们翻转第二张卡片那么在正面的数变成了 [ 1 , 3 , 4 , 4 , 7 ] [1,3,4,4,7] [1,3,4,4,7] 背面的数变成了 [ 1 , 2 , 4 , 1 , 3 ] [1,2,4,1,3] [1,2,4,1,3]。 接着我们选择第二张卡片因为现在该卡片的背面的数是 2 2 2 2 2 2 与任意卡片上正面的数都不同所以 2 2 2 就是我们想要的数字。 示例 2 输入 f r o n t s [ 1 ] , b a c k s [ 1 ] fronts [1], backs [1] fronts[1],backs[1] 输出 0 0 0 解释无论如何翻转都无法得到想要的数字所以返回 0 0 0 。 提示 n f r o n t s . l e n g t h b a c k s . l e n g t h n fronts.length backs.length nfronts.lengthbacks.length 1 n 1000 1 n 1000 1n1000 1 f r o n t s [ i ] , b a c k s [ i ] 2000 1 fronts[i], backs[i] 2000 1fronts[i],backs[i]2000
官方题解
哈希集
算法总结
如果一张卡片正反两面有相同的数字那么这张卡片无论怎么翻转正面都是这个数字这个数字即不能是最后所选的数字 x x x 。 按照这个思路我们首先遍历所有卡片如果卡片上的两个数字相同则加入哈希集合 s a m e same same 中除此集合外的所有数字都可以被选做 x x x 我们只需要再次遍历所有数字找到最小值即可。最后我们返回找到的最小值如果没有则返回 0 0 0 。
复杂度
时间复杂度 O ( n ) O(n) O(n)其中 n n n 是卡片个数。空间复杂度 O ( n ) O(n) O(n)其中 n n n 是卡片个数。
本人代码
Java
class Solution {public int flipgame(int[] fronts, int[] backs) {SetInteger same new HashSet();for (int i 0; i fronts.length; i) {if (fronts[i] backs[i]) {same.add(fronts[i]);}}//牌正反面的数字最大为 2000所以可以将答案初始化为 3000//如果找不到符合的牌面res%3000 即是返回 0int res 3000;for (int i : fronts) {if (i res !same.contains(i)) {res i;}}for (int i : backs) {if (i res !same.contains(i)) {res i;}}return res % 3000;}
}提交结果通过
执行用时: 3 m s 3ms 3ms内存消耗: 42.6 M B 42.6MB 42.6MB
