翻转卡片游戏

标签: 数组 哈希表

难度: Medium

在桌子上有 n 张卡片，每张卡片的正面和背面都写着一个正数（正面与背面上的数有可能不一样）。

我们可以先翻转任意张卡片，然后选择其中一张卡片。

如果选中的那张卡片背面的数字 x 与任意一张卡片的正面的数字都不同，那么这个数字是我们想要的数字。

哪个数是这些想要的数字中最小的数（找到这些数中的最小值）呢？如果没有一个数字符合要求的，输出 0 。

其中, fronts[i] 和 backs[i] 分别代表第 i 张卡片的正面和背面的数字。

如果我们通过翻转卡片来交换正面与背面上的数，那么当初在正面的数就变成背面的数，背面的数就变成正面的数。

示例 1：

输入：fronts = [1,2,4,4,7], backs = [1,3,4,1,3]
输出：2
解释：假设我们翻转第二张卡片，那么在正面的数变成了 [1,3,4,4,7] ， 背面的数变成了 [1,2,4,1,3]。
接着我们选择第二张卡片，因为现在该卡片的背面的数是 2，2 与任意卡片上正面的数都不同，所以 2 就是我们想要的数字。

示例 2：

输入：fronts = [1], backs = [1]
输出：0
解释：
无论如何翻转都无法得到想要的数字，所以返回 0 。

提示：

  • n == fronts.length == backs.length
  • 1 <= n <= 1000
  • 1 <= fronts[i], backs[i] <= 2000

Submission

运行时间: 32 ms

内存: 16.7 MB

class Solution:
    def flipgame(self, fronts: List[int], backs: List[int]) -> int:
        n=len(fronts)
        same=set()
        for i in range(n):
            if fronts[i]==backs[i]:
                same.add(fronts[i])
        res=3000
        for a in fronts:
            if a<res and a not in same:
                res=a
        for a in backs:
            if a<res and a not in same:
                res=a
        return res if res<3000 else 0

Explain

这个题解的思路是先遍历一遍卡片正反面数字，将正反面数字相同的数存入一个集合 same 中。然后再分别遍历正面和反面的数字，找出不在 same 集合中的最小数字作为答案。如果最终没有找到符合条件的数字，就返回 0。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def flipgame(self, fronts: List[int], backs: List[int]) -> int:
        n = len(fronts)
        same = set()  # 存储正反面数字相同的卡片数字
        for i in range(n):
            if fronts[i] == backs[i]:
                same.add(fronts[i])
        
        res = 3000  # 初始化最小数字为一个大于可能的最大数字的值
        
        # 遍历正面数字，找最小值
        for a in fronts:
            if a < res and a not in same:
                res = a
        
        # 遍历反面数字，找最小值
        for a in backs:
            if a < res and a not in same:
                res = a
        
        # 如果找到了符合条件的数字，返回最小值；否则返回 0
        return res if res < 3000 else 0

Explore

在这个算法中，选择3000作为初始的最小值是基于一个假设：卡片上的数字范围不会超过此值。这个值应该大于卡片数字的可能的最大值，以确保在比较过程中任何小于此初始值且不在`same`集合中的数字都能被正确识别为更小值。此选择通常是基于问题描述中给定的数字范围。如果问题没有明确说明，这可能是一个不安全的假设，因此在实际应用中，这个值应该根据实际数字范围来确定。

是的，算法确实考虑了所有卡片的正反面数字都在`same`集合中的边界情况。在这种情况下，没有任何数字可以作为翻转后的最小值，因此所有的数字都会被`same`集合排除。在两次遍历结束后，如果没有找到任何不在`same`中的更小值，`res`将保持为3000，最后通过`res < 3000`的条件检查，算法将返回0。这意味着所有卡片正反面数字都相同，没有可行的翻转。

算法中分别遍历正面和反面数字的原因在于简化逻辑和避免创建额外的数据结构。虽然合并正面和反面数字后进行一次遍历可以达到同样的效果，但这需要额外的空间来存储合并后的列表，并且可能增加合并操作的时间开销。分开遍历可以直接在原始数组上操作，减少了空间和时间复杂度。此外，分别遍历也使得代码逻辑更清晰，易于理解和维护。

如果输入的数字范围超过了3000，当前算法中使用的3000作为初始最小值将不再安全，可能导致算法无法正确返回最小值。在这种情况下，初始值`res`应该设置为大于所有可能的卡片数字的一个值，例如，可以设置为输入数字范围的最大值加1。此外，最好是在问题或输入数据中明确指定数字的上限，以便于正确设置这个初始值。如果没有明确的上限，应该从输入数据中动态确定最大值，以确保算法的正确性和安全性。