LeetCode第104场周赛题解

914. 卡牌分组

题目难度Easy

给定一副牌，每张牌上都写着一个整数。

此时，你需要选定一个数字 X，使我们可以将整副牌按下述规则分成 1 组或更多组：

每组都有 X 张牌。
组内所有的牌上都写着相同的整数。

仅当你可选的 X >= 2 时返回 true。

示例 1：

输入：[1,2,3,4,4,3,2,1]
输出：true
解释：可行的分组是 [1,1]，[2,2]，[3,3]，[4,4]

示例 2：

输入：[1,1,1,2,2,2,3,3]
输出：false
解释：没有满足要求的分组。

示例 3：

输入：[1]
输出：false
解释：没有满足要求的分组。

示例 4：

输入：[1,1]
输出：true
解释：可行的分组是 [1,1]

示例 5：

输入：[1,1,2,2,2,2]
输出：true
解释：可行的分组是 [1,1]，[2,2]，[2,2]

提示：

1 <= deck.length <= 10000
0 <= deck[i] < 10000

思路：

统计每个元素在deck中出现的次数，然后求这些次数的最大公约数，如果最大公约数为1，则返回False，否则返回True。

时间复杂度 $O(Nlog^2N)$

空间复杂度 $O(N)$

代码：

class Solution:
    def hasGroupsSizeX(self, deck):
        """
        :type deck: List[int]
        :rtype: bool
        """
        from collections import Counter
        import math
        d = Counter(deck)
        cnt = d.values()
        if min(cnt) == 1:
            return False
        cnt = list(cnt)
        ans = cnt[0]
        for i in range(1, len(cnt)):
            ans =  math.gcd(ans, cnt[i])
            if ans == 1:
                return False
        return True

915. 分割数组

题目难度Medium

给定一个数组 A，将其划分为两个不相交（没有公共元素）的连续子数组 left 和 right，使得：

left 中的每个元素都小于或等于 right 中的每个元素。
left 和 right 都是非空的。
left 要尽可能小。

在完成这样的分组后返回 left 的长度。可以保证存在这样的划分方法。

示例 1：

输入：[5,0,3,8,6]
输出：3
解释：left = [5,0,3]，right = [8,6]

示例 2：

输入：[1,1,1,0,6,12]
输出：4
解释：left = [1,1,1,0]，right = [6,12]

提示：

2 <= A.length <= 30000
0 <= A[i] <= 10^6
可以保证至少有一种方法能够按题目所描述的那样对 A 进行划分。

思路：

用left[i]来表示i左边的最大值（包括i），用right[i]来表示i右边的最小值（包括i），那么我们只需要寻找一个最小的i，使得left[i]<=right[i+1]。也有更简单的方法，用一次遍历，遍历到i时，当前答案为ans，则ans初始值为1。当我们从第二个元素开始遍历到第i个元素时，我们可以记录[0,ans-1]中最大元素为leftMax，记录[ans, i]中最大元素为rightMax，当A[i]<leftMax时，证明之前的分割不合理，需要更新分割为ans = i + 1。

时间复杂度 $O(N)$

空间复杂度 $O(N)$

代码：

两次遍历

class Solution:
    def partitionDisjoint(self, A):
        """
        :type A: List[int]
        :rtype: int
        """
        l = len(A)
        left = [A[0]] * l
        right = [[A[l - 1]]] * l
        left_max = 0
        right_min = 1000000
        for i in range(l):
            left_max = max(left_max, A[i])
            left[i] = left_max
            right_min = min(right_min, A[l - i - 1])
            right[l - i - 1] = right_min
        for i in range(l - 1):
            if left[i] <= right[i + 1]:
                return i + 1

一次遍历

class Solution:
    def partitionDisjoint(self, A):
        """
        :type A: List[int]
        :rtype: int
        """

        leftMax, rightMax = A[0], A[0]
        ans, n = 1, len(A)

        for i in range(1, n-1):
            if A[i] < leftMax:  
                ans = i + 1  # 更新分割线
                if rightMax > leftMax:
                    leftMax = rightMax
            elif A[i] > rightMax:
                rightMax = A[i]

        return ans

916. 单词子集

题目难度Medium

我们给出两个单词数组 A 和 B。每个单词都是一串小写字母。

现在，如果 b 中的每个字母都出现在 a 中，包括重复出现的字母，那么称单词 b 是单词 a 的子集。例如，“wrr” 是 “warrior” 的子集，但不是 “world” 的子集。

如果对 B 中的每一个单词 b，b 都是 a 的子集，那么我们称 A 中的单词 a 是通用的。

你可以按任意顺序以列表形式返回 A 中所有的通用单词。

示例 1：

输入：A = ["amazon","apple","facebook","google","leetcode"], B = ["e","o"]
输出：["facebook","google","leetcode"]

示例 2：

输入：A = ["amazon","apple","facebook","google","leetcode"], B = ["l","e"]
输出：["apple","google","leetcode"]

示例 3：

输入：A = ["amazon","apple","facebook","google","leetcode"], B = ["e","oo"]
输出：["facebook","google"]

示例 4：

输入：A = ["amazon","apple","facebook","google","leetcode"], B = ["lo","eo"]
输出：["google","leetcode"]

示例 5：

输入：A = ["amazon","apple","facebook","google","leetcode"], B = ["ec","oc","ceo"]
输出：["facebook","leetcode"]

提示：

1 <= A.length, B.length <= 10000
1 <= A[i].length, B[i].length <= 10
A[i] 和 B[i] 只由小写字母组成。
A[i] 中所有的单词都是独一无二的，也就是说不存在 i != j 使得 A[i] == A[j]。

思路：

对B中的每个单词统计字母出现次数，然后建一个counter来统计每个字母在B中出现次数的最大值（相当于取并集，也就是下面第二个写法里每次计算差集再相加）。最后判断A中的每个单词是否满足counter即可。

代码：

class Solution:
    def wordSubsets(self, A, B):
        """
        :type A: List[str]
        :type B: List[str]
        :rtype: List[str]
        """
        # make dict
        dict_A = []
        dict_B = []
        for s in A:
            d = dict()
            for c in s:
                if c in d:
                    d[c] += 1
                else:
                    d[c] = 1
            dict_A.append(d)
        for s in B:
            d = dict()
            for c in s:
                if c in d:
                    d[c] += 1
                else:
                    d[c] = 1
            dict_B.append(d)
        # union dict_B
        judger = dict()
        for d in dict_B:
            for c in d:
                if c not in judger or judger[c] < d[c]:
                    judger[c] = d[c]
                    
        # judge if d1 is subset of d2
        def isSub(d1, d2):
            for k in d1:
                if k not in d2 or d1[k] > d2[k]:
                    return False
            return True
        
        # cal ans
        ans = []
        for i in range(len(A)):
            if isSub(judger, dict_A[i]):
                ans.append(A[i])
        return ans

更简单的写法

class Solution:
    def wordSubsets(self, A, B):
        """
        :type A: List[str]
        :type B: List[str]
        :rtype: List[str]
        """
        
        union_B = []
        ans = []
        for b in B:
            dict_B = union_B.copy()
            for i in b:
                if i in dict_B:
                    dict_B.remove(i)
                else:
                    union_B.append(i)
                    
        for a in A:
            ok = True
            i = list(a)
            for j in union_B:
                if j in i:
                    i.remove(j)
                else:
                    ok = False
                    break
            if ok:
                ans.append(a)
        return ans

913. 猫和老鼠

题目难度Hard

两个玩家分别扮演猫（Cat）和老鼠（Mouse）在无向图上进行游戏，他们轮流行动。

该图按下述规则给出：graph[a] 是所有结点 b 的列表，使得 ab 是图的一条边。

老鼠从结点 1 开始并率先出发，猫从结点 2 开始且随后出发，在结点 0 处有一个洞。

在每个玩家的回合中，他们必须沿着与他们所在位置相吻合的图的一条边移动。例如，如果老鼠位于结点 1，那么它只能移动到 graph[1] 中的（任何）结点去。

此外，猫无法移动到洞（结点 0）里。

然后，游戏在出现以下三种情形之一时结束：

如果猫和老鼠占据相同的结点，猫获胜。
如果老鼠躲入洞里，老鼠获胜。
如果某一位置重复出现（即，玩家们的位置和移动顺序都与上一个回合相同），游戏平局。

给定 graph，并假设两个玩家都以最佳状态参与游戏，如果老鼠获胜，则返回 1；如果猫获胜，则返回 2；如果平局，则返回 0。

示例：

输入：[[2,5],[3],[0,4,5],[1,4,5],[2,3],[0,2,3]]
输出：0
解释：
4---3---1
|   |
2---5
 \ /
  0

提示：

3 <= graph.length <= 200
保证 graph[1] 非空。
保证 graph[2] 包含非零元素。

思路：

极小极大算法

游戏的状态可以表示为 (m, c, t) 其中m 代表老鼠的位置，c 代表猫的位置，t 为 1 轮到老鼠，为2时轮到猫。然后我们可以把每个状态看做是一张有向图里的结点。其中有些结点已经有了结果，如果老鼠进了洞 (m = 0)，则老鼠赢；如果猫抓到老鼠 (c = m)，则猫赢。然后让我们对图的结点进行染色，结点存在三种状态，要么老鼠赢，要么猫赢，要么平局，我们先把未解出的结点全都标记为平局。在极小极大算法里，老鼠会优先选择自己赢得结点，其次是平局，最后才是猫赢；而猫的策略正好相反。

我们对未解出的平局结点 node 进行染色，应遵守以下规则。（我们假设该结点 node 是老鼠的回合 node.turn = Mouse，猫的回合同理）

直接染色：如果一个结点的儿子中，有一个被标记为老鼠赢，那么该结点就标记为老鼠赢；
最终染色：如果一个结点的所有儿子都是猫赢，那么这个结点就标记为猫赢。

我们重复执行上述规则对这个有向图进行染色，直到没有结点符合以上染色规则为止。为了提高染色效率，我们采用一个队列来实现这个自底向上的过程。

将所有已解出的结点加入队列（老鼠在洞里或者猫抓住老鼠的情况）
对队列中的每个结点 node 枚举它们的父结点 parent ：
- 如果可能，对父结点 parent 进行直接染色，例如node为老鼠赢，而它的一个父结点parent刚好是老鼠回合，那么这个parent就直接标记为老鼠赢，并加入队列中；
- 如果不能，例如node为猫赢，它的一个父节点parent是老鼠回合，那么我们就将这个父结点的出度减1，那么如果一个结点的出度降为0，那么也就说明了，这个结点所有子结点都是输，这样就可以对这个结点进行最终染色，标记为输，并加入队列中。

class Solution:
    def catMouseGame(self, graph):
        """
        :type graph: List[List[int]]
        :rtype: int
        """
        N = len(graph)

        # What nodes could play their turn to
        # arrive at node (m, c, t) ?
        def parents(m, c, t):
            if t == 2:
                for m2 in graph[m]:
                    yield m2, c, 3-t
            else:
                for c2 in graph[c]:
                    if c2:
                        yield m, c2, 3-t

        DRAW, MOUSE, CAT = 0, 1, 2
        color = collections.defaultdict(int)

        # degree[node] : the number of neutral children of this node
        degree = {}
        for m in range(N):
            for c in range(N):
                degree[m,c,1] = len(graph[m])
                degree[m,c,2] = len(graph[c]) - (0 in graph[c])

        # enqueued : all nodes that are colored
        queue = collections.deque([])
        for i in range(N):
            for t in range(1, 3):
                color[0, i, t] = MOUSE
                queue.append((0, i, t, MOUSE))
                if i > 0:
                    color[i, i, t] = CAT
                    queue.append((i, i, t, CAT))

        # percolate
        while queue:
            # for nodes that are colored :
            i, j, t, c = queue.popleft()
            # for every parent of this node i, j, t :
            for i2, j2, t2 in parents(i, j, t):
                # if this parent is not colored :
                if color[i2, j2, t2] is DRAW:
                    # if the parent can make a winning move (ie. mouse to MOUSE), do so
                    if t2 == c: # winning move
                        color[i2, j2, t2] = c
                        queue.append((i2, j2, t2, c))
                    # else, this parent has degree[parent]--, and enqueue if all children
                    # of this parent are colored as losing moves
                    else:
                        degree[i2, j2, t2] -= 1
                        if degree[i2, j2, t2] == 0:
                            color[i2, j2, t2] = 3 - t2
                            queue.append((i2, j2, t2, 3 - t2))

        return color[1, 2, 1]