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]

---

实现代码：

function solution(n: number, max: number, array: number[]): number[] {
  const NumberMap: { [key: number]: number } = {};
  // 对所有数进行记数
  for (const num of array) {
    if (NumberMap[num]) {
      NumberMap[num]++;
    } else {
      NumberMap[num] = 1;
    }
  }
  const arr3 = [];
  const arr2 = [];
  // 寻找符合的组合
  for (const key in NumberMap) {
    if (Object.prototype.hasOwnProperty.call(NumberMap, key)) {
      const count = NumberMap[key];
      if (count >= 3) {
        arr3.push(Number(key));
      }
      if (count >= 2) {
        arr2.push(Number(key));
      }
    }
  }
  // 这里的排序方式是重点
  arr2.sort((a, b) => {
    if (a === 1) return -1;
    if (b === 1) return 1;
    return b - a;
  });
  arr3.sort((a, b) => {
    if (a === 1) return -1;
    if (b === 1) return 1;
    return b - a;
  });

  // 遍历所有可能的组合，找到符合条件的最大组合
  for (const a of arr3) {
    for (const b of arr2) {
      if (a === b) continue;
      if (a !== b && 3 * a + 2 * b <= max) {
        return [a, b];
      }
    }
  }
  return [0, 0];
}

function main() {
  // Add your test cases here
  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])
  );
  console.log(
    JSON.stringify(solution(6, 50, [13, 13, 13, 1, 1, 1])) ===
      JSON.stringify([1, 13])
  );
}

main();

尝试使用了很多 AI 工具都无法很好的处理这个 (A)1 > 13 的问题，deepseek 的 R1 模型确实有点东西，以下是 deepseek 的代码实现：

function findMaxGourd(
  n: number,
  max: number,
  array: number[]
): [number, number] {
  const countMap: { [key: number]: number } = {};
  for (const num of array) {
    countMap[num] = (countMap[num] || 0) + 1;
  }

  // Generate a candidates: count >=3, sorted with 1 first, then others in descending order
  const aCandidates = Object.keys(countMap)
    .map(Number)
    .filter((num) => countMap[num] >= 3)
    .sort((a, b) => {
      if (a === 1) return -1;
      if (b === 1) return 1;
      return b - a; // descending order for others
    });

  // Generate b candidates: count >=2, sorted similarly
  const bCandidates = Object.keys(countMap)
    .map(Number)
    .filter((num) => countMap[num] >= 2)
    .sort((a, b) => {
      if (a === 1) return -1;
      if (b === 1) return 1;
      return b - a;
    });

  let bestA = 0;
  let bestB = 0;

  const isBetter = (
    newA: number,
    newB: number,
    oldA: number,
    oldB: number
  ): boolean => {
    if (newA !== oldA) {
      if (newA === 1) return true;
      if (oldA === 1) return false;
      return newA > oldA;
    } else {
      if (newB === 1) return true;
      if (oldB === 1) return false;
      return newB > oldB;
    }
  };

  for (const a of aCandidates) {
    for (const b of bCandidates) {
      if (b === a) continue;
      const sum = 3 * a + 2 * b;
      if (sum > max) continue;

      if (isBetter(a, b, bestA, bestB)) {
        bestA = a;
        bestB = b;
      }
      // Break after first valid b since subsequent b's are smaller
      break;
    }
  }

  return bestA === 0 ? [0, 0] : [bestA, bestB];
}

// Test cases
console.log(findMaxGourd(9, 34, [6, 6, 6, 8, 8, 8, 5, 5, 1])); // [8,5]
console.log(findMaxGourd(9, 37, [9, 9, 9, 9, 6, 6, 6, 6, 13])); // [6,9]
console.log(findMaxGourd(9, 40, [1, 11, 13, 12, 7, 8, 11, 5, 6])); // [0,0]
console.log(findMaxGourd(6, 50, [13, 13, 13, 1, 1, 1])); // [1,13]