5. 寻找最大的葫芦

刷题前请喊一遍我们的口号：

• 方法不对，刷题白费。
• 节省时间，精准刷题。

本题难度系数：⭐简单

问题描述

在一场经典的德州扑克游戏中，有一种牌型叫做“葫芦”。“葫芦”由五张牌组成，其中包括三张相同牌面值的牌 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. 理解问题：
   • 我们需要在给定的牌组中找到符合“葫芦”规则的组合，即三张相同牌面值的牌和另外两张相同牌面值的牌。
   • 这个组合的牌面值之和不能超过给定的最大值 max。
   • 如果存在多个符合条件的组合，我们需要找到其中最大的组合，即优先比较三张相同牌面值的牌，如果相同再比较两张相同牌面值的牌。
2. 数据结构选择：
   • 我们可以使用一个哈希表（或字典）来统计每种牌面值的出现次数。
   • 这样我们可以快速知道哪些牌面值出现了至少三次，哪些牌面值出现了至少两次。
3. 算法步骤：
   • 首先，统计每种牌面值的出现次数。
   • 然后，遍历所有可能的牌面值组合，找到符合“葫芦”规则的组合。
   • 对于每个符合条件的组合，计算其牌面值之和，并检查是否小于等于 max。
   • 最后，选择其中最大的组合并返回。
4. 优化思路：
   • 由于我们需要找到最大的组合，可以先对牌面值进行排序，从大到小遍历，这样可以尽早找到最大的组合，减少不必要的计算。

开始解题

function solution(n, max, array) {
    // 统计每个牌面值的出现次数
    const countMap = new Map();
    for (const num of array) {
        countMap.set(num, (countMap.get(num) || 0) + 1);
    }

    // 将牌面值按从大到小排序，方便后续优先选择较大的牌
    const sortedValues = Array.from(countMap.keys()).sort((a, b) => b - a);

    // 遍历所有可能的 a 和 b 组合
    for (let i = 0; i < sortedValues.length; i++) {
        const a = sortedValues[i];
        if (countMap.get(a) >= 3) { // 确保 a 的牌数至少为 3
            for (let j = 0; j < sortedValues.length; j++) {
                if (j === i) continue; // 确保 b 和 a 不同
                const b = sortedValues[j];
                if (countMap.get(b) >= 2) { // 确保 b 的牌数至少为 2
                    const sum = 3 * a + 2 * b; // 计算牌面值之和
                    if (sum <= max) { // 检查是否满足最大值限制
                        return [a, b]; // 返回符合条件的最大组合
                    }
                }
            }
        }
    }

    // 如果没有找到符合条件的组合，返回 [0, 0]
    return [0, 0];
}

function main() {
    // 测试用例
    console.log(JSON.stringify(solution(9, 34, [6, 6, 6, 8, 8, 8, 5, 5, 1])) === JSON.stringify([8, 5])); // true
    console.log(JSON.stringify(solution(9, 37, [9, 9, 9, 9, 6, 6, 6, 6, 13])) === JSON.stringify([6, 9])); // true
    console.log(JSON.stringify(solution(9, 40, [1, 11, 13, 12, 7, 8, 11, 5, 6])) === JSON.stringify([0, 0])); // true
}

main();

代码解释

1. 统计牌面值出现次数：使用 Map 来统计每个牌面值的出现次数。
2. 排序牌面值：将牌面值按从大到小排序，方便后续优先选择较大的牌。
3. 遍历组合：遍历所有可能的 a 和 b 组合，确保 a 的牌数至少为 3，b 的牌数至少为 2。
4. 计算牌面值之和：计算当前组合的牌面值之和，并检查是否满足最大值限制。
5. 返回结果：如果找到符合条件的组合，返回 [a, b]；否则返回 [0, 0]。

时间复杂度

• 统计牌面值出现次数的时间复杂度为 O(n)。
• 排序牌面值的时间复杂度为 O(m log m)，其中 m 是不同牌面值的数量。
• 遍历组合的时间复杂度为 O(m^2)，其中 m 是不同牌面值的数量。
• 总体时间复杂度为 O(n + m^2)，在大多数情况下是高效的。

希望这段代码的实现和注释能帮助你更好地理解问题并实现最优解！

以上关于5. 寻找最大的葫芦的文章就介绍到这了，更多相关内容请搜索码云笔记以前的文章或继续浏览下面的相关文章，希望大家以后多多支持码云笔记。