个人中心
gpt4 book ai didi

822. Card Flipping Game 翻转卡片游戏

转载 作者：大佬之路 更新时间：2024-01-31 14:16:39 25 4
gpt4 key购买 nike

题目地址：https://leetcode.com/problems/card-flipping-game/description/

题目描述：

Ona table are N cards, with a positive integer printed on the front and back of each card (possibly different).

Weflip any number of cards, and after we choose one card.

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

Aflip 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、 1<=fronts.length==backs.length<=1000.；
2、 1<=fronts[i]<=2000.；
3、 1<=backs[i]<=2000.；

题目大意

有一些正反面都有数字的牌，我们可以做很多次翻转操作，每次翻转时如果这个牌背面的数字没有在这群牌的正面出现过，那么就可以把这个牌翻转过来。求翻转哪个牌可以之后，可以使得所有牌正面中的最小值最小。

解题方法

这个题的英文描述不清，我尽量翻译的清楚了。

所以，如果一个牌正反面相等，那么翻转不翻转没什么意义。否则可以翻转，求翻哪些之后会得到最小，就是如果不翻转的最小值和翻转了之后的最小值的最小值。使用set保存一下正反面相等的数字，这些是一定不能在正面出现的，然后找出不在这个set里面的正反面的最小值即可。

怎么理解？首先正反面相同的翻转没有意义，然后找在正反面的最小值把它翻转到正面来。那么有人会想，如果翻转这个牌和其他的正面的牌有冲突怎么办？其实，如果和set里面的牌有冲突没有意义，如果和不在set里面的正面的牌有冲突就把这个冲突的牌也翻转即可。所以，不用考虑这么多。。

时间复杂度是O(N)，空间复杂度最坏是O(N).

代码如下：

class Solution:
    def flipgame(self, fronts, backs):
        """
        :type fronts: List[int]
        :type backs: List[int]
        :rtype: int
        """
        s = set()
        res = float('inf')
        for f, b in zip(fronts, backs):
            if f == b:
                s.add(f)
        for f in fronts:
            if f not in s:
                res = min(res, f)
        for b in backs:
            if b not in s:
                res = min(res, b)
        return 0 if res == float('inf') else res

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

参考资料：

https://zxi.mytechroad.com/blog/hashtable/leetcode-822-card-flipping-game/

DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有

本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发

25 4 0
文章推荐： 842. Split Array into Fibonacci Sequence 将数组拆分成斐波那契序列
文章推荐： 800. Similar RGB Color 相似 RGB 颜色
文章推荐： 806. Number of Lines To Write String 写字符串需要的行数
文章推荐： 814. Binary Tree Pruning 二叉树剪枝
大佬之路
个人简介

我是一名优秀的程序员,十分优秀！

滴滴打车优惠券免费领取
滴滴打车优惠券
全站热门文章
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com