字节青训Marscode_5：寻找最大葫芦——最新题解

步骤1：问题定义与分析

1. 输入条件：

   • 整数n：牌的数量
   • 整数max：葫芦牌面值之和的上限
   • 数组array：n张牌的牌面值

2. 输出条件：

   • 两个整数组成的数组[a,b]：
     • a表示三张相同牌的牌面值
     • b表示两张相同牌的牌面值
   • 如果不存在符合条件的葫芦，返回[0,0]

3. 限制条件：

   • 牌面值规则：A(1) < 2 < 3 < ... < 10 < J(11) < Q(12) < K(13)
   • 3×a + 2×b ≤ max
   • 需要找到最大的有效组合（先比较三张牌的大小，再比较两张牌的大小）

4. 边界条件：

   • 输入数组中没有足够的相同牌组成葫芦
   • 所有可能的组合都超过max值
   • 输入数组为空或长度不足

步骤2：算法设计与分析

最优解决方案：贪心算法

1. 统计每个牌面值出现的次数
2. 分别找出可以作为三张牌和两张牌的候选值
3. 对候选值排序后，采用贪心策略寻找最优解

时间复杂度分析：

• 统计频次：O(n)
• 排序候选值：O(k log k)，其中k为不同牌面值的数量
• 寻找最优解：O(k²) 总体时间复杂度：O(n + k² + k log k)，其中k ≤ 13

空间复杂度：O(k)，用于存储频次统计和候选值

#include <algorithm>
#include <iostream>
#include <unordered_map>
#include <vector>// 用于比较牌面大小的辅助函数
int getCompareValue(int card) {// A牌（值为1）在比较时应该是最大的return card == 1 ? 14 : card;
}// 用于计算和的辅助函数
int getSumValue(int card) {// 计算和时使用原始值return card;
}
std::vector<int> solution(int n, int max, const std::vector<int>& array) {// 特殊情况处理if (n < 5) return {0, 0};// 统计频次std::unordered_map<int, int> countMap;for (int card : array) {countMap[card]++;}// 收集候选值std::vector<int> triples, pairs;for (const auto& [card, count] : countMap) {// 注意：一个牌面值如果出现4次，既可以用作triple也可以用作pairif (count >= 3) {triples.push_back(card);}if (count >= 2) {pairs.push_back(card);}}// 验证是否有足够的候选值if (triples.empty() || pairs.empty()) {return {0, 0};}// 对候选值进行排序（考虑A牌的特殊性）auto compareCards = [](int a, int b) {int valueA = (a == 1) ? 14 : a;  // A牌特殊处理int valueB = (b == 1) ? 14 : b;return valueA > valueB;};std::sort(triples.begin(), triples.end(), compareCards);std::sort(pairs.begin(), pairs.end(), compareCards);// 寻找最优组合int bestTriple = 0, bestPair = 0;for (int triple : triples) {for (int pair : pairs) {// 跳过使用同一个牌面值的情况if (triple == pair) continue;// 检查是否满足最大值限制int sum = 3 * triple + 2 * pair;if (sum <= max) {// 找到一个有效组合bestTriple = triple;bestPair = pair;goto found;  // 由于已排序，第一个找到的就是最优解}}}found:return bestTriple > 0 ? std::vector<int>{bestTriple, bestPair} : std::vector<int>{0, 0};
}

步骤4：解题启发

1. 值的二元性处理：

   • 分离比较逻辑和计算逻辑
   • 使用辅助函数明确区分不同场景下的值处理

2. 排序策略的灵活运用：

   • 自定义比较函数处理特殊规则
   • 保持原始值用于计算约束

3. 优化空间的发现：

   • A牌的特殊性质提供了独特的优化机会
   • 在满足约束的同时最大化结果

1. 金融交易系统:

   struct Transaction {double nominalValue;     // 面值double tradingValue;     // 交易值double getValueForRisk() {// 风险计算使用面值return nominalValue;}double getValueForTrading() {// 交易使用交易值return tradingValue;}
   };

2. 商品定价系统:

   class Product {double costPrice;        // 成本价double marketPrice;      // 市场价double getPriceForInventory() {// 库存估值使用成本价return costPrice;}double getPriceForSale() {// 销售使用市场价return marketPrice;}
   };