字节青训-寻找最大葫芦

问题描述

在一场经典的德州扑克游戏中，有一种牌型叫做“葫芦”。“葫芦”由五张牌组成，其中包括三张相同牌面值的牌 aa 和另外两张相同牌面值的牌 bb。如果两个人同时拥有“葫芦”，我们会优先比较牌 aa 的大小，若牌 aa 相同则再比较牌 bb 的大小。

在这个问题中，我们对“葫芦”增加了一个限制：组成“葫芦”的五张牌牌面值之和不能超过给定的最大值 maxmax。牌面值的大小规则为：A > K > Q > J > 10 > 9 > ... > 2，其中 A 的牌面值为1，K 为13，依此类推。

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

测试样例

样例1：

输入：n = 9, max = 34, array = [6, 6, 6, 8, 8, 8, 5, 5, 1]
输出：[8, 5]

样例2：

输入：n = 9, max = 37, array = [9, 9, 9, 9, 6, 6, 6, 6, 13]
输出：[6, 9]

样例3：

输入：n = 9, max = 40, array = [1, 11, 13, 12, 7, 8, 11, 5, 6]
输出：[0, 0]

 

 解题思路：

问题理解

我们需要找到一组牌中符合“葫芦”规则的最大组合。具体来说，“葫芦”由三张相同牌面值的牌和两张相同牌面值的牌组成，并且这五张牌的牌面值之和不能超过给定的最大值 max。

数据结构选择

1. 牌面值的映射：由于牌面值的大小规则是 A > K > Q > J > 10 > 9 > ... > 2，我们可以使用一个映射来表示这些牌面值，例如：

   unordered_map<int, int> cardValue = {{1, 14},  // A{13, 13}, // K{12, 12}, // Q{11, 11}, // J{10, 10}, // 10{9, 9},   // 9{8, 8},   // 8{7, 7},   // 7{6, 6},   // 6{5, 5},   // 5{4, 4},   // 4{3, 3},   // 3{2, 2}    // 2
   };

   这样我们可以方便地比较牌面值的大小。

2. 牌的计数：我们可以使用一个 std::unordered_map<int, int> 来统计每种牌面值的出现次数。

算法步骤

1. 统计每种牌面值的出现次数：遍历输入的牌数组，统计每种牌面值的出现次数。
2. 寻找符合条件的“葫芦”：
   • 遍历统计结果，找到所有出现次数大于等于3的牌面值，记为 a。
   • 对于每个 a，再遍历统计结果，找到所有出现次数大于等于2的牌面值，记为 b。
   • 计算 a 和 b 的牌面值之和，如果不超过 max，则记录这个组合。
3. 选择最大的“葫芦”：在所有符合条件的组合中，选择牌面值最大的 a 和 b。

转换成python的最终代码：

from collections import defaultdictdef solution(n, max_sum, array):# 牌面值的映射card_value = {1: 14,  # A13: 13, # K12: 12, # Q11: 11, # J10: 10, # 109: 9,   # 98: 8,   # 87: 7,   # 76: 6,   # 65: 5,   # 54: 4,   # 43: 3,   # 32: 2    # 2}# 统计每种牌面值的出现次数count = defaultdict(int)for card in array:count[card] += 1# 寻找符合条件的“葫芦”max_a = -1max_b = -1for a, count_a in count.items():if count_a >= 3:for b, count_b in count.items():if a != b and count_b >= 2:# 计算牌面值之和sum_value = card_value[a] * 3 + card_value[b] * 2if sum_value <= max_sum:# 更新最大组合if max_a == -1 or card_value[a] > card_value[max_a] or \(card_value[a] == card_value[max_a] and card_value[b] > card_value[max_b]):max_a = amax_b = b# 返回结果if max_a == -1 and max_b == -1:return [0, 0]else:return [max_a, max_b]# 测试用例
result1 = solution(9, 34, [6, 6, 6, 8, 8, 8, 5, 5, 1])
print(result1 == [8, 5])result2 = solution(9, 37, [9, 9, 9, 9, 6, 6, 6, 6, 13])
print(result2 == [6, 9])result3 = solution(9, 40, [1, 11, 13, 12, 7, 8, 11, 5, 6])
print(result3 == [0, 0])

到这里我以为就完了，谁知道！！！，这题面都还有坑 

一开始还以为是测试用例有问题呢，看了好一会才反应过来，A这张牌，它是所有牌中最大的，但是它的牌面却是最小的，nndx，我以为只是默认A是最大的牌呢，这题太害人了

找到问题就好办了，也就是说要特判一次，如果P[1]的数量是大于等于3的，那就直接用它当maxA，如果是小于3但是大于等于2的，直接用来当maxB；

AC代码：

from collections import defaultdictdef solution(n, max_sum, array):# 牌面值的映射card_value = {1: 14,  # A13: 13, # K12: 12, # Q11: 11, # J10: 10, # 109: 9,   # 98: 8,   # 87: 7,   # 76: 6,   # 65: 5,   # 54: 4,   # 43: 3,   # 32: 2    # 2}# 统计每种牌面值的出现次数count = defaultdict(int)for card in array:adjusted_card = card if card != 1 else 14count[adjusted_card] += 1# 寻找符合条件的“葫芦”num3 = 0num2 = 0current_sum = 0for key, value in count.items():if value >= 3:for other_key, other_value in count.items():if other_key != key and other_value >= 2:sum_value = calculate_sum(key if key != 14 else 1, other_key if other_key != 14 else 1)if sum_value <= max_sum:if key > num3 or (key == num3 and other_key > num2):num3 = keynum2 = other_keycurrent_sum = sum_value# 返回结果if current_sum > 0:return [num3 if num3 != 14 else 1, num2 if num2 != 14 else 1]else:return [0, 0]def calculate_sum(num1, num2):return num1 * 3 + num2 * 2# 测试用例
result1 = solution(9, 34, [6, 6, 6, 8, 8, 8, 5, 5, 1])
print(result1 == [8, 5])result2 = solution(9, 37, [9, 9, 9, 9, 6, 6, 6, 6, 13])
print(result2 == [6, 9])result3 = solution(9, 40, [1, 11, 13, 12, 7, 8, 11, 5, 6])
print(result3 == [0, 0])

运行结果：

舒服了