寻找最大葫芦

问题描述

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

在这个问题中，我们对葫芦增加了一个限制：组成葫芦的五张牌牌面值之和不能超过给定的最大值 max。牌面值的大小规则为：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]

解题思路

首先，我们需要统计每张牌出现的次数，然后遍历所有可能的牌面值组合，找到符合条件的最大的葫芦组合。

遍历所有可能的牌面值组合，对于每种牌面值，我们需要判断该牌面值是否可以组成葫芦，以及组合后的牌面值之和是否小于等于给定的最大值。

如果可以组成葫芦，则更新最大葫芦组合。

最后，返回最大葫芦组合。

代码实现

Cangjie

import std.collection.*

func solution(n: Int64, max: Int64, array: Array<Int64>) {
    let rankOrder = [1, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2]
    var cnts = HashMap<Int64,Int64>(13, {i => (rankOrder[i], 0)})
    for (num in array) { cnts[num] ++ }
    for (a in rankOrder) {
        if (cnts[a] >= 3) {
            for (b in rankOrder) {
                if (b == a) { continue }
                if (cnts[b] >= 2) {
                    let total = 3 * a + 2 * b;
                    if (total <= max) { return [a, b] }
                }
            } 
        }
    }
    [0, 0]
}

main() {
    println(solution(9, 34, [6, 6, 6, 8, 8, 8, 5, 5, 1]) == [8, 5])
    println(solution(9, 37, [9, 9, 9, 9, 6, 6, 6, 6, 13]) == [6, 9]);
    println(solution(9, 40, [1, 11, 13, 12, 7, 8, 11, 5, 6]) == [0, 0]);
}

Rust

use std::collections::HashMap;

fn solution(_n: usize, max: i32, array: &[i32]) -> Vec<i32> {
    let rank_order = vec![1, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2];
    let mut cnts = HashMap::new();
    for &num in array { *cnts.entry(num).or_insert(0) += 1 }
    for &a in &rank_order {
        if *cnts.get(&a).unwrap_or(&0) >= 3 {
            for &b in &rank_order {
                if b == a { continue }
                if *cnts.get(&b).unwrap_or(&0) >= 2 {
                    let total = 3 * a + 2 * b;
                    if total <= max { return vec![a, b] }
                }
            }
        }
    }
    vec![0, 0]
}

fn main() {
   println!("{:?}", solution(9, 34, &[6, 6, 6, 8, 8, 8, 5, 5, 1]) == vec![8, 5]);
   println!("{:?}", solution(9, 37, &[9, 9, 9, 9, 6, 6, 6, 6, 13]) == vec![6, 9]);
   println!("{:?}", solution(9, 40, &[1, 11, 13, 12, 7, 8, 11, 5, 6]) == vec![0, 0]);
}

Python

from collections import Counter

def solution(n, max, array):
    rank_order = [1, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2]
    cnts = Counter(array)
    for a in rank_order:
        if cnts.get(a, 0) >= 3:
            for b in rank_order:
                if b == a:
                    continue
                if cnts.get(b, 0) >= 2:
                    total = 3 * a + 2 * b
                    if total <= max:
                        return [a, b]
    return [0, 0]

print(solution(9, 34, [6, 6, 6, 8, 8, 8, 5, 5, 1]) == [8, 5])
print(solution(9, 37, [9, 9, 9, 9, 6, 6, 6, 6, 13]) == [6, 9])
print(solution(9, 40, [1, 11, 13, 12, 7, 8, 11, 5, 6]) == [0, 0])

JavaScript

function solution(n, max, array) {
    const rankOrder = [1, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2];
    const cnts = array.reduce((acc, val) => {
        acc[val] = (acc[val] || 0) + 1;
        return acc;
    }, {});

    for (let a of rankOrder) {
        if (cnts[a] >= 3) {
            for (let b of rankOrder) {
                if (b === a) continue;
                if (cnts[b] >= 2) {
                    const total = 3 * a + 2 * b;
                    if (total <= max) {
                        return [a, b];
                    }
                }
            }
        }
    }
    return [0, 0];
}

console.log(JSON.stringify(solution(9, 34, [6, 6, 6, 8, 8, 8, 5, 5, 1])) === JSON.stringify([8, 5]));
console.log(JSON.stringify(solution(9, 37, [9, 9, 9, 9, 6, 6, 6, 6, 13])) === JSON.stringify([6, 9]));
console.log(JSON.stringify(solution(9, 40, [1, 11, 13, 12, 7, 8, 11, 5, 6])) === JSON.stringify([0, 0]));

复杂度分析

时间复杂度：O(n^2)，其中 n 是牌的数量。我们需要遍历所有可能的牌面值组合，对于每种牌面值，我们需要遍历所有可能的牌面值组合。
空间复杂度：O(n)，其中 n 是牌的数量。我们需要使用一个哈希表来统计每张牌出现的次数。

仓颉编程语言