问题描述
在一场经典的德州扑克游戏中，有一种牌型叫做“葫芦”。“葫芦”由五张牌组成，其中包括三张相同牌面值的牌 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。
数据结构选择
-
牌面值的映射：由于牌面值的大小规则是 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 };这样我们可以方便地比较牌面值的大小。
-
牌的计数：我们可以使用一个
std::unordered_map<int, int>来统计每种牌面值的出现次数。
算法步骤
- 统计每种牌面值的出现次数：遍历输入的牌数组，统计每种牌面值的出现次数。
- 寻找符合条件的“葫芦”：
- 遍历统计结果，找到所有出现次数大于等于3的牌面值，记为
a。 - 对于每个
a，再遍历统计结果，找到所有出现次数大于等于2的牌面值，记为b。 - 计算
a和b的牌面值之和，如果不超过max，则记录这个组合。
- 遍历统计结果，找到所有出现次数大于等于3的牌面值，记为
- 选择最大的“葫芦”：在所有符合条件的组合中，选择牌面值最大的
a和b。
转换成python的最终代码：
from collections import defaultdict
def solution(n, max_sum, array):
# 牌面值的映射
card_value = {
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
}
# 统计每种牌面值的出现次数
count = defaultdict(int)
for card in array:
count[card] += 1
# 寻找符合条件的“葫芦”
max_a = -1
max_b = -1
for 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] * 2
if 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 = a
max_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 defaultdict
def solution(n, max_sum, array):
# 牌面值的映射
card_value = {
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
}
# 统计每种牌面值的出现次数
count = defaultdict(int)
for card in array:
adjusted_card = card if card != 1 else 14
count[adjusted_card] += 1
# 寻找符合条件的“葫芦”
num3 = 0
num2 = 0
current_sum = 0
for 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 = key
num2 = other_key
current_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])运行结果：
舒服了
