嘉兴公司的网站设计,wordpress怎样建站,网络推广优化服务,erp仓库管理系统样板问题描述
问题描述
在一场经典的德州扑克游戏中#xff0c;有一种牌型叫做“葫芦”。“葫芦”由五张牌组成#xff0c;其中包括三张相同牌面值的牌 #xfffd;a 和另外两张相同牌面值的牌 #xfffd;b。如果两个人同时拥有“葫芦”#xff0c;我们会优先比较牌 #…问题描述
问题描述
在一场经典的德州扑克游戏中有一种牌型叫做“葫芦”。“葫芦”由五张牌组成其中包括三张相同牌面值的牌 a 和另外两张相同牌面值的牌 b。如果两个人同时拥有“葫芦”我们会优先比较牌 a 的大小若牌 a 相同则再比较牌 b 的大小牌面值的大小规则为1 (A) K Q J 10 9 ... 2其中 1 (A) 的牌面值为1K 为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] 为了解决这个问题我们可以采用以下步骤
排序和计数首先对给定的牌进行排序并计算每种牌面值出现的次数。寻找可能的“葫芦”组合遍历排序后的数组尝试找到三张相同牌面值的牌a然后继续查找两张相同但不同于 a 的牌面值的牌b。检查总和是否满足条件对于每一个可能的“葫芦”组合检查其总和是否不超过 max。记录最优解如果当前“葫芦”组合是合法的并且比之前找到的更好即 a 更大或者 a 相同而 b 更大则更新最优解。返回结果遍历完成后返回最优解。如果没有找到任何合法的“葫芦”则返回 [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]) 解题过程
统计牌面值数量使用 Counter 统计每种牌面值的数量。遍历所有可能的牌面值组合通过双层循环遍历所有可能的牌面值组合 (x,y)其中 x 代表三张相同牌面值的牌y 代表两张相同牌面值的牌。检查条件对于每个组合 (x,y)检查是否满足以下条件 x×3y×2≤max五张牌的牌面值之和不超过最大值 max。c[x]≥3牌面值为 x 的牌数量至少为 3。c[y]≥2牌面值为 y 的牌数量至少为 2。xy三张相同牌面值的牌和两张相同牌面值的牌不能相同。返回结果如果找到符合条件的组合返回 [x,y]否则返回 [0,0]。
复杂度分析
时间复杂度O(nk2)其中 n 是牌的数量k 是牌面值的种类数本题中 k13。首先需要 O(n) 的时间统计每种牌面值的数量然后需要 O(k2) 的时间遍历所有可能的牌面值组合。空间复杂度O(k)主要用于存储每种牌面值的数量。
知识点扩展
哈希表在本题中使用 Counter 统计每种牌面值的数量这是一种典型的哈希表应用。哈希表可以在 O(1) 的时间复杂度内完成插入和查找操作非常适合用于统计和计数问题。双层循环通过双层循环遍历所有可能的牌面值组合这是一种常见的暴力枚举方法。虽然时间复杂度较高但在本题中由于牌面值种类数 k 较小因此是可行的。
