python解题之寻找最大的葫芦

问题描述

问题描述

在一场经典的德州扑克游戏中，有一种牌型叫做“葫芦”。“葫芦”由五张牌组成，其中包括三张相同牌面值的牌 �a 和另外两张相同牌面值的牌 �b。如果两个人同时拥有“葫芦”，我们会优先比较牌 �a 的大小，若牌 �a 相同则再比较牌 �b 的大小，牌面值的大小规则为：1 (A) > K > Q > J > 10 > 9 > ... > 2，其中 1 (A) 的牌面值为1，K 为13，依此类推。

在这个问题中，我们对“葫芦”增加了一个限制：组成“葫芦”的五张牌牌面值之和不能超过给定的最大值 ���max。

给定一组牌，你需要找到符合规则的最大的“葫芦”组合，并输出其中三张相同的牌面和两张相同的牌面。如果找不到符合条件的“葫芦”，则输出 “0, 0”。

---

测试样例

样例1：

输入：n = 9, max = 34, array = [6, 6, 6, 8, 8, 8, 5, 5, 1]
输出：[8, 5]
说明：array数组中可组成4个葫芦，分别为[6,6,6,8,8],[6,6,6,5,5],[8,8,8,6,6],[8,8,8,5,5]。其中[8,8,8,6,6]的牌面值为36，大于34不符合要求。剩下的3个葫芦的大小关系为[8,8,8,5,5]>[6,6,6,8,8]>[6,6,6,5,5],故返回[8,5]

样例2：

输入：n = 9, max = 37, array = [9, 9, 9, 9, 6, 6, 6, 6, 13]
输出：[6, 9]
说明：可组成2个葫芦，分别为[9,9,9,6,6]和[6,6,6,9,9],由于[9,9,9,6,6]的牌面值为39，大于37，故返回[6,9]

样例3：

输入：n = 9, max = 40, array = [1, 11, 13, 12, 7, 8, 11, 5, 6]
输出：[0, 0]
说明：无法组成任何葫芦，故返回[0,0]

样例4：

输入：n = 6, max = 50, array = [13, 13, 13, 1, 1, 1]
输出：[1, 13]
说明：可组成两个葫芦，分别为[A,A,A,K,K]和[K,K,K,A,A],两者牌面值都小于50，故都合法。因为三张相同牌面值的A > K,故[A,A,A,K,K]比[K,K,K,A,A]要大，返回[1,13]

为了解决这个问题，我们可以采用以下步骤：

1. 排序和计数：首先对给定的牌进行排序，并计算每种牌面值出现的次数。
2. 寻找可能的“葫芦”组合：遍历排序后的数组，尝试找到三张相同牌面值的牌（a），然后继续查找两张相同但不同于 a 的牌面值的牌（b）。
3. 检查总和是否满足条件：对于每一个可能的“葫芦”组合，检查其总和是否不超过 max。
4. 记录最优解：如果当前“葫芦”组合是合法的，并且比之前找到的更好（即 a 更大，或者 a 相同而 b 更大），则更新最优解。
5. 返回结果：遍历完成后，返回最优解。如果没有找到任何合法的“葫芦”，则返回 [0, 0]。

下面是 Python 实现代码：

def solution(n: int, max: int, array: list) -> list:assert n == len(array)from collections import Counterc = Counter(array)vals = [1, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2]for x in vals:for y in vals:if x * 3 + y * 2 <= max and c[x] >= 3 and c[y] >= 2 and x != y:return [x, y]return [0, 0]if __name__ == '__main__':print(solution(n = 9, max = 34, array = [6, 6, 6, 8, 8, 8, 5, 5, 1]) == [8, 5])print(solution(n = 9, max = 37, array = [9, 9, 9, 9, 6, 6, 6, 6, 13]) == [6, 9])print(solution(n = 9, max = 40, array = [1, 11, 13, 12, 7, 8, 11, 5, 6]) == [0, 0])

解题过程

1. 统计牌面值数量：使用 Counter 统计每种牌面值的数量。
2. 遍历所有可能的牌面值组合：通过双层循环遍历所有可能的牌面值组合 (x,y)，其中 x 代表三张相同牌面值的牌，y 代表两张相同牌面值的牌。
3. 检查条件：对于每个组合 (x,y)，检查是否满足以下条件：
   • x×3+y×2≤max：五张牌的牌面值之和不超过最大值 max。
   • c[x]≥3：牌面值为 x 的牌数量至少为 3。
   • c[y]≥2：牌面值为 y 的牌数量至少为 2。
   • x=y：三张相同牌面值的牌和两张相同牌面值的牌不能相同。
4. 返回结果：如果找到符合条件的组合，返回 [x,y]；否则返回 [0,0]。

复杂度分析

• 时间复杂度：O(n+k2)，其中 n 是牌的数量，k 是牌面值的种类数（本题中 k=13）。首先需要 O(n) 的时间统计每种牌面值的数量，然后需要 O(k2) 的时间遍历所有可能的牌面值组合。
• 空间复杂度：O(k)，主要用于存储每种牌面值的数量。

知识点扩展

• 哈希表：在本题中，使用 Counter 统计每种牌面值的数量，这是一种典型的哈希表应用。哈希表可以在 O(1) 的时间复杂度内完成插入和查找操作，非常适合用于统计和计数问题。
• 双层循环：通过双层循环遍历所有可能的牌面值组合，这是一种常见的暴力枚举方法。虽然时间复杂度较高，但在本题中由于牌面值种类数 k 较小，因此是可行的。