找到最大“葫芦”组合

在经典德州扑克中，“葫芦”是一种较强的牌型。它由五张牌组成，其中三张牌面值相同，另外两张牌面值也相同。本文将探讨一个有趣的变形问题：在限定总牌面值的情况下，如何找到符合规则的最大“葫芦”组合。

问题描述

我们需要从给定的一组牌中找到一个满足以下条件的“葫芦”组合：

1. 该组合由三张相同牌面值的牌 (a) 和两张相同牌面值的牌 (b) 组成；
2. 牌面值的总和不能超过指定的最大值 max；
3. 在多个可能组合中，优先选择牌面值 (a) 较大的组合，若 (a) 相同则选择 (b) 较大的组合。

牌面值遵循德州扑克的大小规则，即 A（1）> K（13）> Q（12）> J（11）> 10 > 9 > … > 2。

解题思路分析

1. 数据预处理

首先，我们需要统计输入牌组中每张牌的数量。这样做可以快速识别哪些牌出现了三次及以上（用于构成牌 (a)），哪些牌出现了两次及以上（用于构成牌 (b)）。通过一个哈希映射（HashMap）来实现统计，能够保证在 (O(n)) 时间复杂度内完成遍历和计数。

2. 特殊情况处理

根据题目中的描述，A牌（1）具有特殊的地位。为了最大化组合的大小，我们需优先考虑是否能使用A作为三张牌或两张牌的一部分，并在满足条件的情况下更新“葫芦”组合的值。

1. 若 A 出现了三次或更多：则A可能作为三张牌中的 (a)。在这种情况下，我们需要在其他牌中找到数量至少为2的牌 (b)，并确保该组合的牌面和在最大值 max 之内。
2. 若 A 出现了两次：则A可能作为两张牌中的 (b)。在这种情况下，我们需要在其他牌中找到数量至少为3的牌 (a)，并判断该组合是否符合最大值要求。

3. 普通情况计算

当 A 不能参与组合或未能找到符合条件的组合时，我们可以在其他牌中寻找“葫芦”：

• 从具有三张相同牌面值的牌中选择最大的作为 (a)；
• 从具有两张相同牌面值的牌中选择最大的作为 (b)；
• 比较多个组合的总和，以确保不会超过最大值 max。

4. 结果输出

在所有符合条件的“葫芦”组合中，我们输出最大牌面值的 (a) 和 (b) 值，若没有符合条件的组合则输出 [0, 0]。

Java代码实现

以下是完整的 Java 实现代码：

import java.util.HashMap;
import java.util.Map;public class bigestHulu {public static int[] solution(int n, int max, int[] array) {// 由于最大A的牌面值为1，所以要特殊考虑// 1. 首先用map记录array中每个元素出现的次数Map<Integer, Integer> map = new HashMap<>();// 为了后面特殊考虑map.put(1,0);for (int card : array) {map.put(card, map.getOrDefault(card, 0) + 1);}int x = 0; // 三张相同的牌面值int y = 0; // 两张相同的牌面值// 2.1 A出现3次以上if (map.get(1) >= 3){// 遍历map，找到最大的bfor (Integer b : map.keySet()) {if (b != 1 && map.get(b) >= 2){// 没有爆牌if (1 * 3 + b * 2 <= max){if (b > y){x = 1;y = b;}}}}return new int[]{x, y};}// 2.2 A出现2次if (map.get(1) == 2){// 遍历map，找到最大的bfor (Integer b : map.keySet()) {if (b != 1 && map.get(b) >= 3){// 没有爆牌if (1 * 2 + b * 3 <= max){if (b > y){x = b;y = 1;}}}}return new int[]{x, y};}// 3. A不被选择的情况for (Integer a : map.keySet()) {if (map.get(a) >= 3){for (Integer b : map.keySet()) {if (b != a && map.get(b) >= 2){// 没有爆牌if (a * 3 + b * 2 <= max){// 规则是优先比较牌a的大小，若牌a相同则再比较牌b的大小if (a > x || (a == x && b > y)){x = a;y = b;}}}}}}if (x == 0 && y == 0){return new int[]{0, 0};}else {return new int[]{x, y};}}public static void main(String[] args) {// Add your test cases hereSystem.out.println(java.util.Arrays.equals(solution(9, 34, new int[]{6, 6, 6, 8, 8, 8, 5, 5, 1}), new int[]{8, 5}));System.out.println(java.util.Arrays.equals(solution(9, 37, new int[]{9, 9, 9, 9, 6, 6, 6, 6, 13}), new int[]{6, 9}));System.out.println(java.util.Arrays.equals(solution(9, 40, new int[]{1, 11, 13, 12, 7, 8, 11, 5, 6}), new int[]{0, 0}));}}

复杂度分析与优化

1. 时间复杂度：主循环遍历了牌组中的元素并将其计数，复杂度为 (O(n))。随后对计数结果进行两重嵌套的选择（在所有可能的三张和两张牌中查找最大组合），这部分复杂度约为 (O(k^2))，其中 (k) 是去重后牌面值的数量。
2. 空间复杂度：使用了一个 HashMap 来存储牌的计数，空间复杂度为 (O(k))。

外链：找到最大“葫芦”组合